Mon, 13 Aug 2007 15:36:33 +0200

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) |

From: | torbenm@app-2.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen) |

Newsgroups: | comp.compilers,comp.lang.functional |

Date: | Mon, 13 Aug 2007 15:36:33 +0200 |

Organization: | Department of Computer Science, University of Copenhagen |

References: | 07-07-098 |

Keywords: | GC |

Posted-Date: | 15 Aug 2007 11:41:19 EDT |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.