3 ms·
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
by tomp 12y ago
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).
- rayiner 12y agoR_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 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.
- mnemonik 12y agoI 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.