From: "Mauricio Fernández" Date: 2002-08-22T07:47:28+09:00 Subject: Re: Amortized cost of garbage collection On Thu, Aug 22, 2002 at 05:33:34AM +0900, William Djaja Tjokroaminata wrote: > The idea of amortized cost of garbage collection is very interesting, but > probably our metric of interest for execution speed is only the total cost > itself: > > cost = c * R + d * H = O(R) > > (One question: why sweeping is O(H) and not O(R)? Is the assumption > checking the marking bit is much cheaper than freeing the memory itself?) The sweep must check _all_ the objects to find which ones haven't been marked. H is the set of all objects (both alive and dead == garbage), whereas the objects in R are only those that are live. Thus one part of the cost is proportional to the number of live objects (marking) and the other to the total number of objects (sweeping). It seems I didn't state it clearly and you took R for H. The way Ruby is implemented, the memory in use by the process (heap) is that of the total number of objects, but not more, ie, there isn't an arena of free memory. (see below for some notes on Ruby's GC implementation) d could be made smaller than c (which involves recursion or pointer reversal) if you didn't care about memory fragmentation (it would only involve updating a linked list), but as Ruby uses malloc instead of managing its own arena, freeing the memory will probably be costlier on the average. In fact in the book I mostly took this from, they gave c = 10 ins. and d = 3 for "some computer", but without taking care of memory fragmentation. (R and H given in words) Anyway it isn't very fair to consider the cost of free() as you'd have to do it if you sticked to malloc()/free(). This is another area where being able to define Ruby's behavior would be great for some tasks, going even further in the mem/speed tradeoff than malloc... Ruby's GC ========= (I've spent some time reading gc.c to write this) Ruby's heap is in fact an array (named heaps) of RVALUEs (well, actually an array of RVALUEs arrays :) on which all the GC is performed. There's a list of free positions in heaps, and its grows as needed exponentially (increment *= 1.8 each time it's full). Each RVALUE takes about 20bytes. The RVALUEs point to the "real" data of the object, which is allocated with malloc and free()'d when done. (talking about objects made with Data_*_Struct) THIS IS WHAT WOULD NORMALLY BE CALLED HEAP taken care of by Ruby, allocated with malloc heaps can be larger than the only as much as needed number of objects and there's to hold the total num of objects a list of free RVALUEs. there's no free mem available | here, it must be allocated each | time there's a new object with | malloc ___________________________ ___________________________ RVALUE* heaps[] heaps[1] points to 1 RVALUE --> data for heaps[1][0] 2 RVALUE --> data for heaps[1][1] 3 RVALUE --> this one is free, so there's no memory associated ... heaps[2] 1 RVALUE --> data for heaps[2][0] 2 RVALUE --> FREE 3 RVALUE --> FREE -- _ _ | |__ __ _| |_ ___ _ __ ___ __ _ _ __ | '_ \ / _` | __/ __| '_ ` _ \ / _` | '_ \ | |_) | (_| | |_\__ \ | | | | | (_| | | | | |_.__/ \__,_|\__|___/_| |_| |_|\__,_|_| |_| Running Debian GNU/Linux Sid (unstable) batsman dot geo at yahoo dot com /* * Buddy system. Hairy. You really aren't expected to understand this * */ -- From /usr/src/linux/mm/page_alloc.cA