a comment on small objects

[Godmar Back]

Currently, Kaffe allocates small objects in larger gc_blocks, usually
one page large.  A gc_block has a header, tables that store per object
state, and the array of objects itself.

The sizes for small objects are computed by an algorithm that tries
to stick in 1, 2, 4, 8, and so on objects in a gc_block, and then computes
what the size of each object would be.

For i386's 4K pages and pointer sizes, the solution produced by this
algorithm is this:

8 	24 	56 	120 	240 	496 	1000 	2016

The minimum object size is 8 bytes (only header, no data), and
we assume 8 byte alignment.

On an allocation of anything but these sizes we incur internal fragmentation:
for instance, 56 bytes are reserved for an object of size 25, wasting 
a slack of 31 bytes.

I instrumented Kaffe to print the slack per object allocation and
ran two programs (javac on a subdirectory and a discrete event simulator 
I had written).

The average slack per object was for both programs ca. 16 bytes.
For the javac cases, there were ca. 80,000 live objects (which survived
the gc.), about 10,000 in the other case.  Therefore, the total slack
is ca. 1.2 MBytes or ca. 160 KBytes.  Note that I assume that the
distribution of slack is the same among all allocated objects and those
surviving garbage collections.  While this doesn't have to be the case,
I believe it's okay -- and it's a back of the envelope calculation anyway.

I wrote a program that printed the total amount of slack for these allocation
traces depending on a distribution of allocation sizes.