Current Status

[Godmar Back]

> >
> Actually, with a compacting collector you'd normally save alot more
> RAM than single reference word would cost.  This is because memory
> in conservative non-copying collectors is allocated in blocks of discrete units
> each having a given size.  Hence wastage comes in three forms:
> 
>   1) Memory in conservative non-copying collectors gets allocated in blocks
>       (often 4Kb or so) and chopped up into as many blocks of a given size
>        that will fit.  Thus, a 4K block contains 256 16-byte blocks.  If you're
>       only using 128 16-byte blocks, the remainder is wasted and cannot
>       be used for other size allocations.
>
>   2) Memory blocks only get allocated in certain discrete allocation quantities.
>       Thus, if the collector only supports 64 and 96 byte allocations, and you
>       allocate 65 bytes, the remaining 31 bytes are wasted.

In Kaffe, we use 19 freelists (i.e., 19 sizes) at this time, so the worst 
case overhead is less than 76K on a 4K ppage architecture such as the x86
for wastage of type 1.

I picked the number 19 empirically from peeking at an allocation size 
histogram.  Clearly, the more freelists you have, the higher is wastage 1.
But if you tailor the sizes to fit the allocation pattern of your application,
you can reduce the slack per object, i.e., wastage 2.  In Kaffe, it used to 
be 8 different sizes (< 32Kbytes wastage 1), but this resulted in 16 bytes 
per object slack (wastage 2) for some applications!
For a javac run, this would mean appr. 720KBytes more in wastage of type 2,
for a best-case savings of 76-32 = 44KBytes of wastage of type 1.

If you compile Kaffe with AM_CPPFLAGS=-DDEBUG, you can use the 
-vmdebug SLACKANAL option to print the slack of wastage 2 for newly allocated
objects.  After picking my 19 sizes from an allocation histogram, I measured 
a 6.6 byte per object slack for applications such as javac.  This seems to 
confirm your statement that it's more than one word you'd save, even after
applying some off-the-cuff optimizations like I tried to do.

Kaffe allows you to tailor the size of the tiles in which a small object page
is subdivided to fit a particular application's allocation pattern.
At this point, this is done at compile-time via a table, but it would be easy 
to make it do that at run-time, for instance by reading the values from a
file.

	- Godmar