Re: GC question

Paul Rubin <phr-2007@nightsong.com> writes:


> Suppose you build a big list of cons cells, say a billion of them
> (you're on a large machine). This is in a runtime with traditional
> marking or copying gc, no generation scavenging or region inference or
> anything like that. The collector runs every N bytes of allocation
> for some fixed N. Yes I know that's a dumb way to write an allocator
> for a big-system implementation but it's fairly common for small ones.
>
> It seems to me that the running time to allocate N cells is O(N**2)
> because you run the collector O(N) times during the allocation, and
> each collection costs O(N) on average.


That depends on the percentage of live cells at GC time. A copying GC
will GC when one space is full. It then copies all live data over to
the other space. The cost is proportional to the size of the live
data, and the time until the next GC is proportional to the size of
the dead (reclaimed) data. If the heap (one space) has S cells and x%
of the heap is live at GC, the cost of one GC is S*x/100 and the
number of allocations until next GC is (100-x)*S/100. So to allocate
N cells (where N>>S), you need N/((100-x)*S/100) = 100*N/(100-x)/S GCs
each at a cost of S*x/100, so the total cost is 100*N/(100-x)/S *
S*x/100 = N*x/(100-x). So the cost is O(N) for any fixed live
percentage. But the price increases dramatically with the percentage
of live data at GC time. This is why most allocators increase the
heap size if a GC reclaims less than, say, 50% of the heap.


If the percentage of live data is not constant, you can get quadratic
allocation cost. But the calculation is not as simple as you indicate
above.


                Torben

Return to the comp.compilers page.
Search the comp.compilers archives again.