diff options
Diffstat (limited to 'notes')
| -rw-r--r-- | notes/260822-release3.md | 16 |
1 files changed, 12 insertions, 4 deletions
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. |