GC question

Paul Rubin <phr-2007@nightsong.com>
27 Jul 2007 03:34:55 -0700

          From comp.compilers

Related articles
GC question phr-2007@nightsong.com (Paul Rubin) (2007-07-27)
Re: GC question etxuwig@cbe.ericsson.se (Ulf Wiger) (2007-07-27)
Re: GC question gene.ressler@gmail.com (Gene) (2007-07-28)
Re: GC question bear@sonic.net (Ray Dillinger) (2007-07-28)
Re: GC question @iecc.com <phr-2007@nightsong.com (Paul@iecc.com, Rubin) (2007-07-30)
Re: GC question torbenm@app-2.diku.dk (2007-08-13)
| List of all articles for this month |

From: Paul Rubin <phr-2007@nightsong.com>
Newsgroups: comp.compilers,comp.lang.functional
Date: 27 Jul 2007 03:34:55 -0700
Organization: Nightsong/Fort GNOX
Keywords: GC, performance, question
Posted-Date: 27 Jul 2007 09:29:57 EDT

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.


Post a followup to this message

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