On “correct and efficient work-stealing for weak memory models”

https://wingolog.org/archives/2022/10/03/on-correct-and-efficient-work-stealing-for-weak-memory-models

by ingve • 4 years ago

78 8 4 years ago

gpderetta• 4 years ago

Love discussing work stealing queues. My first comment is that once you have a private queue you sort of lose the benefits of a work stealing queue and are in the domain of work sharing. That might be fine in practice but has different properties.

The weirdest work stealing queue I have read about is one that tries to model the x86 store queue to avoid a StoreLoad by making sure enough stores happen between the push and the take. Not very practical though.

shwestrick• 4 years ago

Private deques can still be very effective for work-stealing, both in theory and practice! This paper comes to mind: https://hal.inria.fr/hal-00863028/document

sadiq• 4 years ago

There's a high performance Chase-Lev work stealing queue written to exploit the OCaml 5 memory model in the lockfree library: https://github.com/ocaml-multicore/lockfree/blob/main/src/ws...

rand_flip_bit• 4 years ago

Sadly, while Chase-Lev is great, there is currently a patent for the algorithm that won’t expire until 2025. Of course, this algorithm is held by non other than Sun/Oracle.

Once I discovered this, I had to switch over my implementation to something less… of a legal risk. What a shame.

Mathnerd3142• 4 years ago

I guess you mean this patent? https://patents.google.com/patent/US20070143326

Looks like your standard software patent of an abstract idea so per https://en.wikipedia.org/wiki/Software_patents_under_United_... it is probably invalid. Also Oracle has issued a statement https://www.gordoni.com/software-patents/statements/oracle.s... in the 1990's saying that they oppose software patents, and besides the Android case with Google they seem to mainly be invalidating patents rather than suing others. So I would say the risk is minimal. But IANAL and to each their own.

ncmncm2• 4 years ago

Off-topic, is this the David Chase who did all the original work on e-cash, decades before there was crypto currency?

Mathnerd3142• 4 years ago

Per https://en.wikipedia.org/wiki/Cryptocurrency#History it was David Chaum, not Chase.

ncmncm2• 4 years ago

So it was, tx.

On “correct and efficient work-stealing for weak memory models”

Related Stories