From 3437809126d05845bf7eea84497d8d22ad03eb84 Mon Sep 17 00:00:00 2001 From: Taylan Kammer Date: Fri, 26 Jun 2026 21:46:46 +0200 Subject: Add a note. --- notes/260626-fastcons5.md | 93 +++++++++++++++++++++++++++++++++++++++++++++++ notes/index.md | 1 + 2 files changed, 94 insertions(+) create mode 100644 notes/260626-fastcons5.md diff --git a/notes/260626-fastcons5.md b/notes/260626-fastcons5.md new file mode 100644 index 0000000..b76f4ec --- /dev/null +++ b/notes/260626-fastcons5.md @@ -0,0 +1,93 @@ +# List array optimization + +_2026 June_ + +Currently, I use pointers with a 3-bit tag to denote lists of up to 7 +elements, with the value 0 meaning it instead has a terminator at the +end. + +This requires a small complication in the interpreter, where it needs +to check if the tag value is 0 or not, and branch based off of that. + +It also makes lists of 8+ elements waste 8 bytes of memory for the +termination marker, and makes checking the length require a linear +scan through memory. + +Here's an idea for the future: + +* Map a 32 GiB virtual memory region for list arrays. + +* When the high 16 bits of a NaN-packed value say "list pointer" then + the next 16 bits are a length, and the low 32 bits an "address" or + index into the list array memory region. + +* A memory access like `base + index*8` is equally as cheap as just + `base + offset` on modern CPUs, so we lose no performance to the + fact that we use the address as an index. + +* Maximum list length is 65535 elements, which is good enough. + +* Length 0 with a canonical null address can denote `()` aka `nil` as + the empty list singleton; no need for a separate singleton value + making type checks and such awkward. + +This is very clean and consistent, and should offer a slight boost to +interpreter performance, thanks to less branching, no wasted 64-bit +slots in the list array pool, and so on. + +I've said for the future, but this idea seems so attractive that I'm +thinking of implementing it right away. I just haven't touched mmap +so far and don't know how to do it in Zig but it should be easy. + +## For the regular heap as well? + +So far I've held steadfast to the idea that I want to support a full +48-bit address range for regular heap pointers, but it's honestly not +necessary. + +If I ever implement a modern and advanced GC algorithm like ZGC, I'll +probably need to sacrifice some bits to that anyway. + +A 32-bit index value can support a 64 GiB heap by taking advantage of +the fact that heap objects are 16-byte aligned. Higher alignment may +increase that further; for example, align to entire cache lines (64 +bytes) and you can support a 256 GiB heap. This could be a setting, +to accommodate for different needs. + +This time we can't make use of the fact that modern CPUs allow direct +index value multiplication, because those only go up to 8. However, +since we use exactly the lower 32 bits of a register, no masking or +"shifting back and forth" is needed on x86-64, since we can use the +virtual register feature to extract the low half directly. I think +there's similar tricks available on AArch64. Then you just multiply +by a multiple of 8, which is just a left-shift instruction. + +This gives us 16 bits for the heap type tag and GC-related metadata. +Even Generational ZGC, the most bit-hungry GC design, only uses 9 in +total (despite having 17 more in reserve) so all is well. Note: I've +not fact-checked this; it comes straight out of Google Gemini. But I +know that it uses 4 bits for coloring, and "a few more" for the newer +generational algorithm. Documentation doesn't specify how many and I +don't want to dive into the code; in any case, I'm sure that the 16 +bits I have will be more than enough, using e.g. 4 bits for the heap +type tag, and up to 12 bits for GC metadata. + +Heck, having heap type tags directly on pointers really isn't that +important, because in almost all cases you will actually access the +heap value after ensuring it's the correct type, and a type mismatch +leading to an exception is a cold branch anyway. So having the type +tags on the heap object itself works well enough, meaning I could use +all 16 bits for GC metadata if I really needed that for some reason. + +Anyway, I'm getting ahead of myself. For now, I think I'll move to a +design where list pointers are partitioned as 16/16/32, and regular +heap pointers as 16/4/12/32, with a static 16-byte alignment allowing +up to 64 GiB of regular (non-list) heap objects for now. + +And if one day someone writes a program in Zisp (lol) that needs more +heap data then that, we'll see. In most cases, having hundreds of GiB +of data probably means you just have some enormous mapped files or so, +for which you could just use handle objects and index values, so the +actual heap pointers of the runtime don't need to be able to represent +those addresses. Dog knows what corporations do with Java that makes +them want a GC algorithm that can handle terabytes of heap data. diff --git a/notes/index.md b/notes/index.md index 346bcb6..96ade16 100644 --- a/notes/index.md +++ b/notes/index.md @@ -34,3 +34,4 @@ * [Cons cell optimization again](260610-fastcons3.html) * [Cons cell optimization AGAIN](260611-fastcons4.html) * [AST Optimizations](260625-optimize.html) +* [Further list array optimization](260626-fastcons5.html) -- cgit v1.2.3