From 425bb051b60e4e63de0173dd5679fb356f72f72b Mon Sep 17 00:00:00 2001 From: Taylan Kammer Date: Fri, 21 Aug 2026 23:15:30 +0200 Subject: Add a note. --- notes/260821-release2.md | 113 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 113 insertions(+) create mode 100644 notes/260821-release2.md (limited to 'notes/260821-release2.md') diff --git a/notes/260821-release2.md b/notes/260821-release2.md new file mode 100644 index 0000000..5ea4510 --- /dev/null +++ b/notes/260821-release2.md @@ -0,0 +1,113 @@ +# Releasing vmem, reloaded + +_2026 August_ + +Here's a cool strategy I came up with that's a huge improvement over +the naive one with the array sort explained here: + +* [Releasing virtual memory](260817-release.html) + +At least, it doesn't require extra memory allocation, so it would be +safe to use whenever. All it needs is a statically allocated array, +like in the `.data` or `.bss` section of the executable. + +As above, I will describe the algo in terms of a single size class; +just loop over the size classes and apply it to as many as needed +until enough memory is released to the kernel. + +* Allocate a single static array of a relatively small even number, + like 16, 32, or 64. Every two elements are a FROM and a TO index. + +* Initialize them all to some NULL/INVALID index value. (Need this + every time the algo runs, since it may be dirty from last run.) + +* Initialize a counter UNHANDLED to 0. + +* Now iterate through all free-list entries (the chunk head indexes + and indexes of each chunk) and do as follows for each INDEX: + + For each FROM / TO pair in the static array, do one of these: + + * Check if FROM is NULL; if so, write INDEX into FROM and TO. + (Registers a new span of memory into the static array.) + + * Check if INDEX equals FROM - 1; if so, write INDEX into FROM. + (Expands this span of memory backwards.) + + * Check if INDEX equals TO + 1; if so, write INDEX into TO. + (Expands this span of memory forwards.) + + * Otherwise, increment UNHANDLED. (Found an index belonging to a + span of memory we can't handle right now; static array is full.) + + Note: When I write INDEX - 1 and INDEX + 1 I mean "the index that + would belong to the previous / next slot of this size class" which + typically means subtracting or adding some multiple of 8 to the + index value, depending on slot size. + +* After we're done with the free-list iteration, we now have pairs of + from-to indexes representing free spans of memory. There may be + some that actually connect to each other (one "to" happens to be + equal to another "from") so we could run a normalization loop over + the array... Which may be most easily achieved by just sorting it. + +* In any case we've found N vacancies in a single iteration through + the free-list... Except it could actually just be a single one, + because the array immediately filled up with dispersed indexes + within a single span, which we didn't know would eventually all + connect to each other! Crap. + + Well, this is why I write down these notes; clarifying some idea + often reveals a flaw in it. Anyhow, moving on for now. + +* If UNHANDLED is a reasonably large number, we may decide to go for + another loop through the free-list. + +OK, a small improvement immediately occurs to me: + +* Keep the array permanently sorted by shifting around entries when + new ones are added. (It's small; that's fine to do. Just don't + literally call sort every time; use a smart algo that keeps empty + slots in the array etc., like a kind of streaming sort with upper + size bound. No idea if "streaming sort" is a thing. Now it is? + Another way to view this is... Just a B-Tree of height 1?) + +* This will have a chance of revealing connected spans as we go, so + they can be concatenated on-the-run and a from/to pair slot in the + array freed up. + +Choosing a sufficiently large static array could actually make this +quite effective, but 16 or 32 probably won't cut it. It all depends +on the user's memory allocation and freeing patterns, but using an +array of length 1024 or a small multiple thereof may work well. + +Ultimately, it's better than nothing. The size of the array sets a +lower bound on the length of the span we will find in the pessimal +case: `N * slot_size`. For N = 1024, and the smallest size class, +which is 128 bytes, that's still... 128 KiB. OK, maybe that's not +very much, but it's the *absolute worst* case. + +Another improvement comes to mind, along with a flaw in the original +plan: + +First of all, the static array must be large enough to hold at least +every element of a free-list node including the head of the chunk. +And that twice, since each index is stored as FROM and TO initially. +Given 16-element chunks, that means the array must be at least 34 +indexes long. The reason is simple: I didn't consider at what point +entries / chunks would be pruned from the free-list. If every index +of a chunk is inserted into our array, OK, detach the chunk, but if +there's even one index that remains unhandled, what do we do with it? +The chunk header has to stay in the free-list, the other indexes get +"liberated" from it, and the one index we couldn't handle remains. +That's pretty ugly. + +But lo and behold: What if we reuse the memory of the free slots?? +Even with the smallest size class of 128, that's space for 32 more +index values. + +We could build a B-tree of free slots, out of the free slots! + +I'm getting tired, so I think I'll leave it here. + +To be continued... -- cgit v1.2.3