diff options
| -rw-r--r-- | notes/261002-radix-opt.md | 49 | ||||
| -rw-r--r-- | notes/index.md | 1 |
2 files changed, 50 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. diff --git a/notes/index.md b/notes/index.md index 227610e..b3d7256 100644 --- a/notes/index.md +++ b/notes/index.md @@ -2,6 +2,7 @@ ## 2026 Q4 +* [2026-10-02: Radix Bush Improvement](261002-radix-opt.html) * [2026-10-02: Free-List Improvement](261002-free-bitmap.html) ## 2026 Q3 |