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