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

Bruce Hoult bruce at hoult.org
Sun Dec 18 06:55:51 PST 2011

On Sun, Dec 18, 2011 at 11:21 PM, Jan Wielemaker <J.Wielemaker at vu.nl> wrote:
> Hi,
> I've got the following problem. I must store a multi-way linked list
> (i.e., each cell has a (fixed) array of `next' pointers). This list is
> huge. My current tests are with about 10 million objects, but we want to
> be able to use several 100 millions. The app is multi-threaded and I want to
> be able to have writers that throw cell out and readers that
> concurrently walk over the data without locking.

Parallel marking is unlikely to help unless you can start different
threads in very different parts of the list, or they diverge quickly.

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.

You can't change an object from uncollectable to collectable. They are
stored in completely different pools. There are never collectable
objects on the same memory page as uncollectable ones.  The same is
true of atomic and non-atomic.

More information about the Gc mailing list