I’d love to write more about this and discuss in in depth but for now I can only provide a link to the heap.zig file of a Lisp interpreter I wrote years ago, which I think has quite an interesting & novel memory layout, thoroughly inspired by that very talk on data-oriented design: wisp/core/heap.zig at master · mbrock/wisp · GitHub
The idea is that we use 32 bit tagged pointers for all values. Half of those are just immediate 31 bit numbers. Some other tags are also used for smaller immediate values:
pub const Tag = enum(u5) {
int = 0x00, // 31-bit fixnum
sys = 0x11, // static constant value
chr = 0x12, // unicode codepoint
jet = 0x13, // builtin operator
pin = 0x1f, // gc-pinned value
duo = 0x15, // cons pair pointer
sym = 0x16, // symbol pointer
fun = 0x17, // closure pointer
mac = 0x18, // macro pointer
v32 = 0x19, // word vector pointer
v08 = 0x1a, // byte vector pointer
pkg = 0x1b, // package pointer
run = 0x1c, // evaluation state
ktx = 0x1d, // evaluation context
ext = 0x1e, // external object
};
The first five types are immediates; the rest are pointers.
pub const Ptr = packed struct {
pub const Idx = u26;
era: Era,
idx: Idx,
tag: Tag,
pub fn make(tag: Tag, idx: Idx, era: Era) Ptr {
return .{ .era = era, .idx = idx, .tag = tag };
}
pub fn from(x: u32) Ptr {
return @as(Ptr, @bitCast(x));
}
pub fn word(ptr: Ptr) u32 {
return @as(u32, @bitCast(ptr));
}
};
Each pointer type has its own storage: cons cells in one bucket, closures in another, and so on. This layout lets me have ~64 million entries for each pointer type—which ought to be enough for anyone, and if not, the whole scheme can be upgraded to use 64 bit words without much difficulty.
Now those buckets could easily just be ArrayLists, so
conses: ArrayList(struct { car: u32, cdr: u32 })
and so on, but instead, each object type has a MultiArrayList.
This means that the fields of each object type are contiguous arrays. So every cdr in the heap is in one array. The object type columns are like this:
/// Each pointer type has a set of columns.
pub fn ColEnum(comptime t: Tag) type {
return switch (t) {
.int, .sys, .chr, .jet, .pin => void,
.duo => enum { car, cdr },
.sym => enum { str, pkg, val, fun, dyn },
.fun => enum { env, par, exp, sym, cnt },
.mac => enum { env, par, exp, sym, cnt },
.v08 => enum { idx, len },
.v32 => enum { idx, len },
.pkg => enum { nam, sym, use },
.ktx => enum { hop, env, fun, acc, arg },
.run => enum { exp, val, err, env, way },
.ext => enum { idx, val },
};
}
All the fields are just 32 bit words. So the heap ultimately consists of 36 arrays of 32-bit tagged pointer words. Zig’s SoA MultiArrayList in fact keeps the field arrays contiguous with each other, so it’s really only 10 allocations. That’s for the structures; a separate ArrayList(u8) keeps string bytes, and an ArrayList(u32) keeps arbitrary-length vector data, as backing stores for the v08 and v32 values.
Then there’s the garbage collector keeping the heap tidy. wisp/core/tidy.zig at master · mbrock/wisp · GitHub
It’s a Cheney-style copying two-space collector that essentially runs a breadth-first scan of the live values, moving everything into a fresh set of MultiArrayLists. This discards garbage in time proportional only to the live data—and simultaneously compacts the data. Right after the GC is done, the cdr array will be packed with only live pointers—in traversal order, so if the root set references a certain long linked list, the whole tail of that list will likely be a contiguous sequence.
A major benefit of this heap structure is that there are no pointers anywhere. The whole thing can be trivially serialized to disk with a single syscall—just gather up the slices into iovecs and hand them all to a writev. Loading the heap from disk is two syscalls: first read the header to know how much to allocate per slice, then do a single readv. This also works in WebAssembly, etc—the Lisp system can instantly save itself to local storage in the middle of an execution.
(The one-bit era field of the packed pointer structure is needed for the two-space collector logic to know, as it’s traversing, whether any given pointer is already in the new arena or not. It flips between 0 and 1 with every collection cycle. Since this metadata is also serialized, we can dump and load at any state, though usually you’d want to dump right after a GC to avoid saving dead data.)
Is it the best heap layout in general? Probably not! Have I benchmarked it to verify the performance benefits? Not at all! Is it kind of cool? I really think so!
Of course this doesn’t even really begin to address your actual questions! Your interpreter, I guess, would have most of its data in what I call the v32 blob, and in my scheme that means you’d also have separate handle values allocated in the v32 object table. If my Lisp interpreter is used in a way that relies heavily on such “vectors” or “structs”, it’d also entail a lot of indirection.
I think one way to cope with that would be to design a way for the heap to have a bunch of different vector blobs, corresponding to the lengths of small vectors—like, say, each vector size between 3 and 8 gets its own pointer tag and its own blob in the heap—so the index is immediately in the handle word, not indirectly in idx+len table.