What interesting alternatives are there for constructing an arbitrarily large static array from smaller scattered blocks of fixed-sized non-contiguous blocks of memory?
This is similar to the problem solved by hardware MMU pagetable mappings from virtual memory to physical memory, but in this particular case the scale is different, and it needs to be implemented in software, with virtual memory, and also in userland.
To clarify a bit, I'm using baker's treadmill as my GC, but it only supports fixed sized allocations (the current chunk size is 128 bytes, but I have some slight flexibility in re-defining it). The language I'm implementing requires arbitrary sized vectors with something close to O(1) access/write.
Currently I'm just building a pyramid of chunks, which gives something like log12(n) lookups, but the memory overhead sucks. Are there any interesting hashing solutions for mapping monotone index ranges to pointers?
What about run-time generation of a minimal perfect hash function? It seems they require at minimum 1.44 bits per key. If we bump the allocation block size to 512, we can support vectors with up to 1454080 elements, since we only need to map block numbers and not vector indices.
See the paper "Z-rays: divide arrays and conquer speed and flexibility" (http://dl.acm.org/citation.cfm?id=1806596.1806649&coll=DL&dl=GUIDE) for more information regarding optimization of this array format:
These scattered blocks are sometimes called arraylets and are used by other GC algorithms: https://www.ibm.com/developerworks/websphere/techjournal/1108_sciampacone/1108_sciampacone.html
Also related: the Staccato GC: http://researcher.watson.ibm.com/researcher/files/us-groved/rc24504.pdf