Comment by rayiner | Hacker News Reader

Comment by rayiner | Hacker News Reader

Parent Full thread

The overhead of GC is independent of heap size. Take the following variables:

    L = total size of live objects in heap
    H = maximum size of heap
    P = time between collections
    R_a = rate of allocation
    R_s = rate of heap scanning

It's easy to define P and R_s (assume a mark-sweep collector so we can ignore copy reserve):

    P = (H - L) / R_a
    R_s = L / P

Substitute and simplify:

    R_s = L / ((H - L) / R_a)
    R_s = L / (H - L) * R_a

In other words, it doesn't matter how big your heap is. If you make your heap twice the live size, the amount of heap scanning you do will always be equal to your allocation rate times some constant. If H = 2L, that constant is 1.

So the way to improve performance is to cut down on that allocation rate. If you use RAII for most objects, and GC only occasionally, your allocation rate, net of non-GC allocations, will be very low, which means your scanning rate will be very low. You'll have to traverse all live objects every GC cycle, but you'll rarely have to do a GC cycle.

I followed your math, but not your conclusion!

Say we use your example of H = 2L. Then we have R_s = L / (2L - L) * R_a, or R_s = R_a. Sure.

Now say we double the heap: H = 4L. Then we have R_s = L / (4L - L) * R_a, or R_s = R_a/3. For a fixed allocation rate, increasing the heap makes the scan rate go down, i.e. we scan less often.

It seems like you're assuming that the live set is a fixed fraction of the heap size, but that doesn't make sense to me. The size of the live set is a function of what the program does, not its heap size.

The calculation assumes the program is in equillibrium (no net growth of L). Many GCs, such as Boehms, maintain a fixed ratio of L and H.

Are you sure about this? The main overhead of a mark-and-sweep GC isn't the marking phase, it's the sweeping phase - you need to find and free all dead objects (to mark them as free/add them to the free list), and since you don't know where they are (by definition, since they are dead, they have no references pointing at them) you have to scan the whole heap (or at least all the pages that were objects were allocated/live on since the last GC cycle).

R_s for a naive mark-sweep looks like this:

    R_s = (L + H) / (H - L) * R_a

For a copying collector:

    R_s = L / (H - 2L) * R_a

If H is a constant multiple of L, then your scan rate will be a constant multiple of your allocation rate, independent of heap size.

In practice, you won't sweep the whole heap after each GC cycle, but will do it lazily: http://www.hboehm.info/gc/complexity.html. The point in that article about marking time dominating allocation/sweep is even more true today. Allocation and sweep access memory linearly and are easily parallelized. Meanwhile, marking accesses memory randomly, and the maximum concurrency is dependent on the shape of the live object graph.

I don't think that is generally true. Sweeping has much better cache locality than marking, which is following pointers all over who-knows-where in the heap.

Sure, but since any object could have a reference to a GC object, you still have to eat the latency of scanning the entire heap (not just the GC'd objects) every so often. That seems like a pretty big performance cliff.

Reply on news.ycombinator.com