News for hackers. Stuff that matters.
Re:Linus Torvalds on Garbage Collection (2002) by rayiner on Friday April 22, 2011 @12:36PM (#2474570)
There is not a fundamental conflict between GC and cache generally. The conflict is with how caches are implemented in most CPUs.

Consider a simple generational collector with a nursery of N cache lines. The allocator will bump allocate into LINE_0, LINE_1... until LINE_N, and then copy all survivors into the mature generation. When it starts allocating again, it will start at LINE_0. Ie: it will touch at least N cache lines before ever coming back to any given cache line. If N > the size of the cache, each allocation will involve a cache miss. Each time the allocator allocates into a cache line, it will have been evicted already, and will need to be brought into the cache before it is written to.

The key observation here is that you're dealing with an artificial W-W dependency, not a real R-W dependency. When the allocator allocates into a cache line, it doesn't care what the data already in that cache line is! The cache line doesn't need to be brought in from memory because it is garbage and will be overwritten completely.

There are lots of solutions to the problem. At every allocation the allocator could simply issue a prefetch for the next line, because it knows it will need it soon. Or, you could have an instruction that simply blows away a cache line, marking it cached+dirty in the coherence protocol without generating a main memory access.

In fact, I'm not sure that modern CPUs don't detect this condition in their write buffers already. Something like Bulldozer's write coalescing cache could certainly do this.

Aside from this issue, generational GC's are very cache friendly. Collection inherently compacts memory, and the order of collecting tends to bring objects onto the same pages and sometimes the same cache lines as the objects that refer to them.

As an aside, the other big cache-thrashing process, marking, can also be made cache friendly on modern architectures. If your CPU has SMT, you can run the marker in a concurrent thread. It can sit there take advantage of the available memory parallelism that most programs leave on the table.

There are no comments on this comment yet.