Clojurians Log v2

So the above works, but I was storing the free/alloc structures in a single tau, which ends up enforcing a global write lock. It's "lock-free" in the sense that it's not susceptible to dead-locks. But writers have to wait in line to mutate the free/alloc structures

So I endeavored to build a wait-free/lock-free array mutation procedure that allocates and frees memory and I've got a buggy, half working thing actually doing the thing

I'll post it up here this evening

Okay, so I may pull this into a blog post at some point, so I'd like to work through the details here and if anybody has any comments/corrections/verbiage that can help characterize these methods, that'd be appreciated.

So to recap, we need a data structure that stores at least an address and a length for each object stored in another data structure (which contains the actual data for the object)

So for this implementation, we'll just use a SharedArrayBuffer/Int32Array which allows for js/Atomics.CompareAndExchange with a byte layout of: [addy len addy len addy len ...]

For a minimal implementation, we'll use a 64 byte SAB, containing 16 ints, altogether allowing for 8 object references

A table representing the initial values of this "reference" array looks like this: ([0 -1 -1] [1 -1 -1] [2 -1 -1] [3 -1 -1] [4 -1 -1] [5 -1 -1] [6 -1 -1] [7 -1 -1])

a -1 for addy will mean the reference is free for allocation. a -1 for len means there are no further allocations to the right

Consider this a "picture" of what the current memory structure (the pool) looks like: ================================================================================

When we do (swap-tmap t1 (constantly [0 1 2])), where t1 is a map that has a value referencing which reference slot it points to, we want to see the following afterwards:

([0 0 7] [1 -1 -1] [2 -1 -1] [3 -1 -1] [4 -1 -1] [5 -1 -1] [6 -1 -1] [7 -1 -1])
0++++++=========================================================================

Well, here we're stringifying [0 1 2] into "[0 1 2]", so it takes up 7 bytes in memory

Then if we do: (swap-tmap t2 (constantly [0 1 2 3])) and then (swap-tmap t1 (constantly [0 1 2 3 4])) Then we should see this:

([0 -1 7] [1 7 9] [2 16 11] [3 -1 -1] [4 -1 -1] [5 -1 -1] [6 -1 -1] [7 -1 -1])
======1++++++++2++++++++++======================================================

our second swap invocation placed t2 in slot one (after slot zero), with an address of seven and length nine on the memory pool. The third swap, which was on t1, made a new allocation in slot two, freeing up slot zero for a future allocation. Slot zero still remembers how much length is left over.

Let's do another swap on t2: (swap-tmap t2 (constantly [0 1 2 3 4])) And now we see:

([0 -1 16] [1 -1 0] [2 16 11] [3 27 11] [4 -1 -1] [5 -1 -1] [6 -1 -1] [7 -1 -1])
===============2++++++++++3++++++++++===========================================

After slot one was freed, it's extra memory was migrated leftward, into slot zero

If we swap into t1 something much smaller: (swap-tmap t1 (constantly [0])) Then we'll see slot zero wins the allocation and remaining memory is pushed right:

([0 0 3] [1 -1 24] [2 -1 0] [3 27 11] [4 -1 -1] [5 -1 -1] [6 -1 -1] [7 -1 -1])
0++=======================3++++++++++===========================================

shrinking t2 again will again move things to the left and free up the remaining space: (swap-tmap t2 (constantly [0 1]))

([0 0 3] [1 3 5] [2 -1 -1] [3 -1 -1] [4 -1 -1] [5 -1 -1] [6 -1 -1] [7 -1 -1])
0++1++++========================================================================

Here's the code to get that does the swapping stuff:

Here's the code to view the model:

I find that building a visual assistant to assist in debugging is super helpful. It's much easier to quickly test and see flaws in the algorithm's alignment when it's represented at least partially in a geometrically meaningful way

hang on, a pigeon just flew into my apartment

no shit

It was trying to escape this noachian deluge going on outside

Anyway, I think there are some edge cases where the above algorithm fails. I need to build more robust testing mechanisms. But the general operation of it is starting to come together. Does anyone disagree that this (at least, in spirit) is a lock-free and wait-free algo?

Also, would you call this "garbage collection?" I think it sort of is and sort of isn't, but there's definitely a lot here we're not having to worry about, since A) we're on JS, and B) everything is copy-on-write

Also, would specs and spec.gens be helpful here, ya think?