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

[Jan Wielemaker]

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.

That is why I started considering Boehm-GC: I can make this work by
locking the writers and by being careful about the ordering of the
memory operations readers can do their work unlocked. Using Boehm-GC, I
can leave the actual destruction of cells to the collector.

Unfortunately, this doesn't scale. GC time on 10M cells is 1 sec (on 8
cores; 7.5 sec CPU time). Is there a way to solve this?

One line I was thinking along is this: alloc the cells using
GC_MALLOC_ATOMIC_UNCOLLECTABLE(). That works just fine (GC time is about
0.01 sec.) Now, before removing a cell, I would like to be *modify* the
state of the cell to what GC_MALLOC() would have created. I glanced
through the source. This looks hard. (Im-)possible?

Opinions?

	Thanks --- Jan