memory managment

[acken@informatik.uni-kl.de]

Some musings on efficient storage allocation for small records:

Most applications store lots of small records on the heap.  For a
compiler living under a `foreign' OS this usually means to ask the OS
to allocate some memory for every single record.  Every record lugs
around it's own type tag plus (optionally) additional data to simplify
memory managment or garbage collecting, which e.g. sums up to 8 byte
per record.  The OS's allocator usually only handles block sizes that
are multiple of 16, adding its own padding to every allocated block.
So for a small record of e.g. 12 bytes the compiler adds 8 bytes and
the allocator rounds it up to 32 bytes, resulting in additional 20
bytes allocated holding no data.  Allocating 330 of these objects
would use up more than 10K of memory.

This overhead can be reduced by grouping together lots of small
objects of the same type onto a single page of 2^n bytes allocated on
a 2^n boundary, without any padding between them and with just a
single type tag for the whole page.  Example: n=12, 4K per page,
object size is 12.  Even with (e.g.) 128 bytes used for bookkeeping of
the whole page, 330 objects can be stored in 4K of memory--in contrast
to the >10K needed above.  If the type tag is stored at the very
beginning of the page, then an object's tag can be located by masking
out the lower n bytes of its address.

Needless to say, this allocation scheme works best for small objects.
Its benefit varies with the size of the objects and the overhead
introduced by the compiler and the OS.

Advantages 
- makes optimal use of memory for small objects (the common case)
- fewer calls to the OS memory allocation functions, possibly saving
  lots of execution time (especially during garbage collection)
- less fragmentation, most allocations call for blocks of page size

Disadvantages
- can't deal with large objects, especially large arrays; these have
  to be treated differently  
- a single object may keep its whole page alive; this isn't too bad if
  large numbers of similar objects are allocated shortly afterwards
- additional complexity for the garbage collector 


Any comments on this?

-- mva