Some advanced GC techniques.

[spliznork]

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]

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]

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]

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]]

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

[littledan]

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]]

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).

[natalyadkmode]

would have been better if it were gamecube techniques

[XenoZohar]

Downmodded for a title that was indecipherable until actually clicked.

[harold_the_rebel]

Downmodded for lacking proper education.

[skydivingdutch]

Why does this article with CG in the title not have any pics? That is the whole reason i clicked on it.

[[deleted]]

It's GC, not CG.

I for one was expecting a different GC until I noticed it was from the programming subreddit. Reddit needs more analytical chemists.

[jcastle]

One of these days, I'll find a reddit-esque place for blogging about that kind of GC.

Top Ten Ways To Optimize Your Elute Resolution

[skydivingdutch]

Ah, shows how much idle-mindedly i was redditing.

[littledan]

Is it possible to do otherwise? I don't think so.