This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2018-08-13
Channels
- # aleph (6)
- # architecture (29)
- # beginners (175)
- # cider (22)
- # clara (5)
- # cljdoc (5)
- # cljs-dev (28)
- # cljsrn (6)
- # clojure (62)
- # clojure-finland (7)
- # clojure-italy (7)
- # clojure-nl (2)
- # clojure-spec (23)
- # clojure-uk (194)
- # clojurescript (90)
- # core-async (2)
- # cursive (23)
- # datomic (41)
- # defnpodcast (2)
- # editors (4)
- # emacs (1)
- # figwheel-main (41)
- # fulcro (53)
- # hoplon (15)
- # hyperfiddle (4)
- # immutant (1)
- # jobs (7)
- # jobs-discuss (103)
- # lein-figwheel (9)
- # off-topic (34)
- # onyx (3)
- # parinfer (1)
- # portkey (1)
- # re-frame (7)
- # reagent (2)
- # remote-jobs (2)
- # rum (1)
- # shadow-cljs (148)
- # sql (54)
- # tools-deps (3)
- # vim (7)
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
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++++++=========================================================================
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++++++++++===========================================
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++++========================================================================
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
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?