Add note.HEADmaster

1 files changed, 49 insertions, 0 deletions

diff --git a/notes/261002-radix-opt.md b/notes/261002-radix-opt.md
new file mode 100644
index 0000000..c3ab2a0
--- /dev/null
+++ b/notes/261002-radix-opt.md
@@ -0,0 +1,49 @@
+# Radix Bush Improvement
+
+_2026 October_
+
+This may be a dumb micro-optimization, or not; here goes.
+
+Context:
+
+* [Green Tea](260923-green-tea.html): See 'Radix Bush' section.
+
+The "Level 1" is 512 bytes and the "Level 2" is 32 KiB.
+
+Most applications will use a small fraction of the total 256 GiB vmem
+that Meta Alloc manages.  But it will be spread across the slabs that
+are each 16 GiB.  So, the GC will need to touch widely spread apart
+locations of Level 1 and 2.
+
+For example, if the application uses 1 MiB from the first and 1 MiB
+from the fifth slab:
+
+* Level 1: Touches u64 bitmap at index 0, and u64 bitmap at index 16
+  if my math is correct.  That's two separate cache lines.
+
+* Level 2: Touches u64 bitmap at index 0, and at index 1024, again if
+  my math is correct.  That's two separate *pages* of memory.
+
+Consider the following alternative: From the full 35-bit Meta Alloc
+unit index (that's 31 bits per slab and 4 bits to identify the slab)
+we could put the highest 4 bits at the front instead (i.e., swap the
+positions of the 31-bit intra-slab index and the 4-bit slab index).
+
+Now the above becomes:
+
+* Level 1: Touches only one u64 bitmap, at index 0, because it covers
+  the first 4 GiB of each slab.
+
+* Level 2: Touches only one u64 bitmap, at index 0, because it covers
+  the first 1 MiB of each slab.
+
+At level 2, we don't touch a second cache line until one slab reaches
+over 64 MiB of memory use.  At level 1, we don't touch a second cache
+line until a slab reaches a whopping 4 GiB of memory use.
+
+Yeah, I think that's pretty good!
+
+We may need to pay with some additional arithmetic, but I think that
+should be fine.  And in fact, given that we already have to do some
+arithmetic on Meta Alloc indexes, we may actually end up with an
+equivalent count of CPU instructions; I've not analyzed it yet.