# Representing non-contiguous memory regions as a standard vector with O(1) access

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.

Edit:

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

A simple approach is to have a one-level lookup table that maps each block of the array to where it is stored. In other words, for a logical array $A[0\dots n-1]$ containing $n$ bytes, we have a lookup table $T[0\dots \frac{n}{128}-1]$ containing $n/128$ pointers; the bytes $A[128k \dots 128k+127]$ are stored at the physical address $T[k]$. To look up $A[i]$, we compute $p = T[i \gg 7]$ (where $\gg$ indicates logical right shift), then read the byte at address $p + (i \bmod 128)$.
This does require a single contiguous region large enough to store $n/128$ pointers (e.g., holding $n/32$ or $n/16$ bytes, depending on whether you're on a 32-bit or 64-bit system). Given that, array operations become fast: you basically have one extra table lookup and indirection.
Rather than looking for a better data structure to handle this kind of arbitrarily-bad fragmentation, a cleaner solution is probably to design your memory management system to avoid creating worst-case memory fragmentation in the first place. One architecture that can help deal with this is a buddy allocator. The entire memory address space can be divided into 128-bit chunks, but we then impose a binary tree structure on it: the 128-byte chunk at address $256k$ is the sibling/buddy of the 128-byte chunk at address $256k+128$. Those two chunks, if they're both available, can be coalesced into a (fused) 256-byte chunk. Each 256-byte chunk has a buddy, and if they're both available, they too can be merged to obtain a 512-byte chunk. And so on. This allows you flexibility to deal with small 128-byte chunks when you need them, but also provides a way to build up larger chunks of contiguous memory and try to avoid arbitrarily-bad fragmentation.