From 0696ee5702a36fe1a4cd13015eb9445115869f35 Mon Sep 17 00:00:00 2001 From: Taylan Kammer Date: Sun, 23 Aug 2026 15:39:17 +0200 Subject: Another lil addition to last note. --- notes/260822-release3.md | 16 ++++++++++++---- 1 file changed, 12 insertions(+), 4 deletions(-) (limited to 'notes/260822-release3.md') diff --git a/notes/260822-release3.md b/notes/260822-release3.md index e569ed9..4305ae1 100644 --- a/notes/260822-release3.md +++ b/notes/260822-release3.md @@ -241,7 +241,9 @@ one, while the bit-count of words increases one by one: The need to move entire node contents to keep the trie sorted worries me a little, but I think it should be fine. Just make sure to sort the indexes within each free-list chunk in-place before iterating -through them to insert them into the trie. +through them to insert them into the trie. Actually, I'm not sure +whether that would really be an optimization; may need a benchmark, +and may depend on size class. ### How to traverse @@ -284,9 +286,7 @@ But it was fun to come up with, and good to know that it's possible. ### Useful to others? Can any general-purpose allocator using free-lists make use of this -strategy? - -Yes, provided that: +strategy? I think yes, provided that: * Each free-list entry points to a memory slot that can hold at least two references to other slots, but preferably many more. @@ -300,3 +300,11 @@ Yes, provided that: I've not thought much about unequal slot size, since it isn't relevant to Meta Alloc, but I think it would work. + +And, assuming that the "sort a chunk of indexes in-place first" idea +actually improves performance by decreasing the need to move around +too much data between nodes, then we can emulate that: + +* Use a statically allocated "scratch-pad array" into which you load + chunks of free-list entries, so you can sort them in-place before + iteratively adding them to the trie. -- cgit v1.2.3