[Gc] Newbie: how to deal with a giant linked list?

Bruce Hoult bruce at hoult.org
Sun Dec 18 11:44:26 PST 2011

On Mon, Dec 19, 2011 at 8:00 AM, Jan Wielemaker <J.Wielemaker at vu.nl> wrote:
>> Can you actually scan through the list faster than the GC time? You
>> could well be running into cache and/or TLB thrashing if the Next
>> links don't usually point to items on the same memory page and each
>> page is visited many times.
> I don't know the answer to that question. Bottom line is that I do not
> care. As long as cells are part of the structure, I don't need to
> have GC dealing with them.

Then you don't want a general purpose GC, as scanning the entire
structure is exactly what has to happen.

> I want GC starting to deal with them from the
> moment I disconnect them from the global structure because they might be
> involved in some operation by some other thread (i.e., I'm mostly
> interested in references from registers or the stacks of other
> threads).

It seems to me that what you need is not GC, but a register of objects
needing deleting and a way to determine that every thread has made
progress to at least the next node. That could be as simple as a
boolean per thread that is set by the thread when it moves to the next
node (usually with no effect), and is cleared by the task that wants
to clear out the deleted objects pool. Or they could be condition

> In other words, I'm trying to find out whether
>   (a) There is a much better plan to my problem, being ...
>   (b) Changing object types is feasible, deemed useful and a patch
>       that allows for this will be accepted into the main source
>       (provided ...).  Note that I might need some guidance, but I'm
>       perfectly willing to do the dirty work myself.

There is no possible patch that could change a single object (of less
than GC page size, normally 4 KB), from one object type to another.
You would have to copy it somewhere else, therefore changing its
address, therefore making registers and stacks and other objects not
point to it any more.

More information about the Gc mailing list