Re: memory managment

[Mike Griebling <grieblm@trt.allied.com>]

I think there are other ways of dealing with small objects (as is current
practice in the Oberon systems).  They typically allocate just one huge
chunk of memory from the host OS and then subdivide this chunk as necessary
to satisfy requests for memory.

Each of these smaller chunks is kept in a linked list of similarly-sized
blocks from which allocated blocks are removed.  The heads of the linked
lists are kept in a global array which is indexed by the block size.
This makes allocations very fast.

Using the above technique means that the OS's tags aren't a concern since
only one tag is associated with the entire chunk of memory.  Of course,
blocks still have their type types but we have complete control over
padding concerns since the Oberon allocator can choose blocks at
boundaries which are multiples of 8 (to support double-word alignment).
If we pass special tags to the allocator we could probably even align
blocks to just require multiples of 4 (if no double-word alignments).

So, for your example of a block of 12 bytes we still have 8 bytes for
type-tag, link ptr. but we can now allocate a block which is exactly 20 bytes
in size (assuming no double-word alignments).  With 330 of these blocks
the overhead would be just the 8 bytes or 2640 bytes.  All 330 objects
would be stored in about 6.4K (not too far off your 4K).  We also don't have
any hassles with one unused block holding an entire page at ransom.  Another
gain is that we can use existing ETH garbage collection algorithms.

Larger blocks can be dealt with in the same manner except they require
individual calls to the host OS and will have more overhead during allocation
but they are kept in the same sort of linked list with all the large blocks
kept in the last list of the global array.

Advantages
- reasonably good use of memory for small objects
- a single call to the OS memory allocation functions
- fragmentation is not a concern since garbage collection will
  automatically compact memory and reslice it.
- can use the ETH standard garbage collection algorithms
- don't keep entire pages occupied just for one dirty block
- same algorithm can be used with larger objects (as ETH currently does)

Disadvantages
- still some overhead although not as much as with the original "worst
  case" allocator

Note: All the above is documented in the ETH reports (I don't recall the
actual number but can find out if anyone is interested).  I do have the
complete code for the above Allocator/Collector in Oberon-2 if anyone
would like to do some experiments.

Michael G.