On “correct and efficient work-stealing for weak memory models”(wingolog.org)
wingolog.org
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
4 comments
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...
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.
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.
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
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.
Once I discovered this, I had to switch over my implementation to something less… of a legal risk. What a shame.
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.
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.
Off-topic, is this the David Chase who did all the original work on e-cash, decades before there was crypto currency?
Per https://en.wikipedia.org/wiki/Cryptocurrency#History it was David Chaum, not Chase.
So it was, tx.