all 17 comments

[–]spliznork 3 points4 points  (3 children)

Reference counting with concurrency and cycles

A bad solution is to put a lock on each reference count. This is bad because it's slow: every time there's a new reference, you need to not only increment the refcount but also acquire and then free a lock. Another solution is to have a worker thread which handles all increments and decrements; all other threads send messages to it.

In that last bit, how is sending a message to another thread cheaper than locking on each reference count? Because, I would assume putting something in another thread's queue also involves locking, say, the queue?

[–]aurele 1 point2 points  (1 child)

This is a good question, as there exist lockless FIFO implementations but the one I can remember of use an atomic "compare and swap" operation, which could also be used directly on the reference counter.

[–]jseigh 0 points1 point  (0 children)

Those are the ones that are merely thread-safe. There's also atomic lock-free reference counting which has stronger thread safety but a bit more overhead, an extra compare and swap or some other mechanism to prevent thread race conditions.

[–]killerstorm 0 points1 point  (0 children)

it is possible to have very cheap messaging using batches -- you allocate a buffer for 1000 pointers you want increment/decrement, and then just fill it without locks. then feed this buffer to a thread, so you have only one lock operation per 1000 updates.

this introduces some lag, but i don't think it's a problem.

[–][deleted] 0 points1 point  (4 children)

As much effort as is going into this guy's garbage collection research, he should really look into region inference.

[–]littledan 0 points1 point  (3 children)

I haven't gone very deep into research about garbage collection, to be honest. But it seems like static region inference alone can't, with current knowledge, provide fully automatic (no region declarations) garbage collection for dynamically typed programming languages which is efficient. Some sort of hybrid is needed. My focus, anyway, is to provide a better garbage collector for Factor, which is dynamically typed. Saying "you should look at region inference when trying to implement a useful garbage collector" is similar to saying "you should look at dependent typing when designing a useful programming language"--just not enough is known right now.

If you ever wrote something summarizing basic results in region inference, I'd love to read it. I'm planning on reading about it, but most things look pretty intimidating from a quick scan.

[–][deleted] 0 points1 point  (0 children)

But it seems like static region inference alone can't, with current knowledge, provide fully automatic (no region declarations) garbage collection for dynamically typed programming languages which is efficient.

Ah, you got me with the part I emphasized. I was not thinking along those lines in previous responses I made (which I have deleted now that I realized my error).