CX: Wait-Free Universal Construction

https://concurrencyfreaks.blogspot.com/2019/11/cx-wait-free-universal-construction.html

by ingve • 7 years ago

91 24 7 years ago

concurrencyfreaks.blogspot.com

0xffff2• 7 years ago

Is "Universal Construction" a well-known term? I don't recall ever encountering it in my Comp. Sci. degree, and some quick searching only leads me to more academic papers.

FisDugthop2• 7 years ago

I only know them from category theory and abstract algebra. You could think of them as polymorphic constructions from some set of assumptions. As an example, given some type of elements, the type of lists of those elements is a monoid (the free monoid) on those elements.

rhacker• 7 years ago

It's horribly over garbled. The Github repo doesn't do a better job of explaining anything. This is a horrible news item.

ajkjk• 7 years ago

It's mentioned on https://en.wikipedia.org/wiki/Non-blocking_algorithm, at least.

banachtarski3• 7 years ago

Make any data structure wait-free as long as it has a copy constructor

I'm going to hazard a guess that in many cases, a simple mutex (or even better, striped mutexes) will perform better.

gpderetta2• 7 years ago

a simple mutex will never be wait free and as such is never appropriate where a wait free data structure is required (it is not about performance).

banachtarski3• 7 years ago

Maybe not but I can count on one hand the number of times I've truly needed that property. Compare to a try-lock or a timed lock for example.

chrisseaton3• 7 years ago

...but that's not wait free? What happens if a processes crashes or a thread is de-scheduled while holding the lock? Or just isn't scheduled again very quickly?

eternalban2• 7 years ago

Glancing at OP, it appears CX itself uses a RW lock.

"Several years ago, when Andreia first came up with the idea that we could use a reader-writer lock to achieve wait-freedom, I though that was crazy, but cool. After joining up forces with Pascal and a lot of work, we were able to turn that into a universal construction, CX."

"- wait-freedom can be achieved with locks"

FisDugthop2• 7 years ago

How would this compare with RCU techniques, as used in Linux? Is it about getting finer-grained access without compromising speed?

scottlamb• 7 years ago

How would this compare with RCU techniques, as used in Linux? Is it about getting finer-grained access without compromising speed?

I'm wondering this, too. To me it sounds the same. From the "bad news" section:

CX serializes all mutative operations which means it's flat at best if the workload consists of only mutations on the sequential object. ... It also consumes larges amounts of memory and in the very unlikely worst case, may require 2x MAX_THREADS replicas of the sequential object.

That's roughly the same text I'd expect to see on an RCU implementation. (Maybe the exact number of replicas differs; I think with some RCU schemes it's GCed asynchronously and is theoretically unbounded.) At first glance, it's hard to understand what's new here. They say they used this to make "the world's first wait-free balanced binary tree". How does that description apply to this but not to RCU?

dmoldavanov• 7 years ago

They also have _comparison_ with RCU https://concurrencyfreaks.blogspot.com/2019/10/is-rcu-generi...

kimi• 7 years ago

Oh yes, that's a Clojure atom. Been there, done that. https://www.braveclojure.com/zombie-metaphysics/

(BTW, in practice, Clojure atoms were initially thought of as the simple case of refs, where you have a full STM behind you. In practice, atoms end up being "good enough" in nearly all cases....)

dwohnitmok• 7 years ago

I think (?) the difference between this and an atomic reference (of which a Clojure atom is a specific example) is that it is geared towards mutable data structures rather than immutable ones. Although as far as I can tell it's more or less emulating immutable data structures by copying the mutable data structure before modification.

As for the ultimate lack of widespread use of STM in real-world Clojure code, I think in addition to the nice interface provided by atoms, it's also in part because Clojure's STM lacks a couple of combinators that limit its composability, and so a lot of other concurrency approaches make more sense. See the combinators provided by https://github.com/skejserjensen/eclojure and http://www.thattommyhall.com/2013/02/15/stm-clj-vs-haskell/

gbrown_• 7 years ago

Sadly arXiv appears to be undergoing an outage at the moment so the link to the paper isn't reachable.

https://twitter.com/arxiv/status/1192508633092898816

gpderetta2• 7 years ago

Herlihy[1] has a general transformation to make any arbitrary algorithm wait free, so I think that the claim of novelty is a bit overblown.

[1] The Art of Multiprocessor Programming; I seem to have misplaced my copy so I can't reference chapter and verse.

DSingularity• 7 years ago

Yeah I remember it. Basically, compare-and-swap to enqueue an operation. In contention threads will cooperate to help threads finish operations. With this you bound the blocking and achieve wait-free concurrent operation.

thekdude• 7 years ago

I believe you are talking about chapter 6 section 4, page 130 of the Revised First edition

amluto• 7 years ago

It also consumes larges amounts of memory and in the very unlikely worst case, may require 2x MAX_THREADS replicas of the sequential object.

Depending on how many threads are involved, I have a simple construction [0] that is likely to scale much better. It uses multiple copies of the data structure, but each successive copy is used only half as often, resulting in logarithmic amortized complexity.

IMO these types of constructions only make sense when reads are far more common than writes. Using this for an std::set is ridiculous — if you really want to apply one of these constructions to a mapping, you should build a whole new optimized seat structure for each write. Or maybe you could cleverly use immutable data structures to improve memory and bandwidth usage.

[0] https://link.springer.com/chapter/10.1007%2F978-3-540-92221-...

CX: Wait-Free Universal Construction

Related Stories