GC question

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.


I never realized this before. Is it a well-known phenemonon? Is the
main answer something like generation scavenging?


This relates to a real situation that came up on comp.lang.python
yesterday.

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