Add a note.

1 files changed, 93 insertions, 0 deletions

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.