Fork me on GitHub
#architecture
<
2018-08-13
>
john19:08:09

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

john19:08:22

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

john19:08:45

I'll post it up here this evening

john21:08:33

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.

john21:08:48

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)

john21:08:09

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

john21:08:34

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

john21:08:13

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])

john21:08:59

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

john21:08:47

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

john21:08:11

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++++++=========================================================================

john21:08:10

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

john21:08:01

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++++++++++======================================================

john21:08:06

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.

john21:08:21

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++++++++++===========================================

john21:08:51

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

john22:08:49

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++++++++++===========================================

john22:08:49

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++++========================================================================

john22:08:21

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

john22:08:14

Here's the code to view the model:

john22:08:55

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

john22:08:42

hang on, a pigeon just flew into my apartment

john22:08:02

It was trying to escape this noachian deluge going on outside

😱 8
john22:08:09

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?

john22:08:02

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

john22:08:45

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