Add a note.

1 files changed, 113 insertions, 0 deletions

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...