Augmenting bordeaux-threads with atomic operations
Bordeaux-threads is a portability layer that defines a low-level API for programming shared-state concurrency: basic thread management, locks, timeouts, and condition variables. It has been ported to plenty of CL implementations: ABCL, Allegro CL, CLISP, Clozure CL, CMUCL, Corman Lisp, ECL, Lispworks, MCL, SBCL, and SCL. As such, it's an ubiquitous building block for useful higher-level libraries such as lparallel, PCall, CL-STM, and many others.
One important piece missing from bordeaux-threads is the support for atomic operations such as compare-and-swap, fetch-and-add, atomic-swap, etc. Among other things, these operations are useful for implementing scalable, efficient lock-free or wait-free algorithms and data-structures. The availability of such data-structures in a portable fashion would benefit many of the higher-level libraries that use bordeaux-threads. (E.g.: lparallel, when running on SBCL, takes advantage of the lock-free queues provided by that implementation.)
Back when bordeaux-threads was created, virtually no CL implementation supported these operations.1 Nowadays, though, more and more implementations support at least a subset thereof. What follows is a survey of that support in modern CL implementations, a necessary first step to add an atomic operation API to bordeaux-threads.
compare-and-swap
I'll start with compare-and-swap (CAS), which is the most powerful of the atomic operators we'll be looking into, and consequently the most widely supported in CL implementations. Typically, this operation is syntactically similar to SETF
but is restricted to a handful of CL places:
SLOT-VALUE
.SYMBOL-VALUE
, i.e. the value of a dynamic variable.- The global value of a dynamic variable, a common extension to standard CL.
- Structure accessors.
CAR
andCDR
.SYMBOL-PLIST
.SVREF
.- MOP's
STANDARD-INSTANCE-ACCESS
andFUNCALLABLE-STANDARD-INSTANCE-ACCESS
.
slotval | symval | gsymval | structslot | car/cdr | symplist | svref | mop | |
---|---|---|---|---|---|---|---|---|
ACL 9.0b | ✔ | ✖ | ✔ | ✔ | ✔ | ✔ | ✔ | ✖ |
CCL 1.7 | ✖ | ✔ | ✖ | ✔ | ✖ | ✖ | ✔ | ✖ |
LW 6.0 | ✔ | ✔ | ✖ | ✔ | ✔ | ✖ | ✔ | ✖ |
SBCL 1.0.54 | ✔ | ✖ | ✔ | ✔ | ✔ | ✔ | ✔ | ✔ |
SCL 1.3 | ✔ | ✔ | ✔ | ✔ | ✔ | ✔ | ✔ | ✖ |
(2012-06-07 update: fixed table to correctly reflect the fact that SCL does support SYMBOL-GLOBAL-VALUE
as a CAS place.)
(2012-06-10 update: Nikodemus wrote in to point out that (cas (symbol-value '*foo*) ...)
on SBCL modifies the special variable's global value rather than its dynamic binding. Fixed table accordingly.)
As far as I can tell, ABCL, CMUCL and ECL don't yet have any support for atomic operations. I didn't check MCL or Corman Lisp. Also, note that CCL's CAS — ccl::conditional-store
— is in fact an unexported interface. All in all, the feature overlap amongst the Lisps that better support CAS (ACL, LW, SBCL, SCL) is not too bad.
Conclusion: bordeaux-threads should support CAS for SLOT-VALUE
, CAR/CDR
, structure accessors, and SVREF
on ACL, LW, SBCL, and SCL. The other partially supported places could perhaps be supported where possible but with a compile-time style warning about their unportability; haven't decided yet whether this would be worth the trouble.
fetch-and-add
A concrete implementation of fetch-and-add is the x86 LOCK
-prefixed XADD
instruction. It atomically increments an integer using word-sized modular arithmetic, i.e. the addition can overflow and the result wraps.
SBCL has ATOMIC-INCF
whose name is slightly misleading because it is pretty much a direct interface to the aforementioned XADD
instruction (on x86, of course), and thus only works on word-sized places: structure slots with type SB-EXT:WORD
or simple arrays with element-type SB-EXT:WORD
.
Lispworks on the other hand, provides ATOMIC-FIXNUM-INCF
. Although it also boils down to XADD
and the addition will overflow, it works on all the same places as CAS since it handles plain fixnums.
Conclusion: bordeaux-threads can define ATOMIC-WORD-INCF
and ATOMIC-FIXNUM-INCF
, support those operations efficiently on SBCL and LW respectively, and emulate them on other Lisps using CAS.
atomic-swap
Only Lispworks provides this functionality (via ATOMIC-EXCHANGE
). Not yet sure whether it's sensible to emulate this using CAS on other Lisps.
Coming next
Having surveyed the support for atomic operations, we'll proceed to define a useful interface and some slightly higher-level utilities around CAS. There's plenty of inspiration to be found in the various implementations and we should be able to draw various ideas from each.
(P.S.: hopefully this doesn't overlap too much with Nikodemus's MADEIRA efforts.)
1 (2012-06-07 update) I hadn't realized this until Douglas Crosher wrote in to set some facts straight: turns out SCL has supported SMP (including compare-and-swap) for nearly a decade!
8 komentoj:
There is also a trivial-compare-and-swap library that currently only exists (I think) within Sykopomp’s chanl library: https://github.com/sykopomp/chanl/blob/master/src/trivial-cas.lisp
It only does CCL & SBCL and it doesn’t use CCL’s conditional-store, though – it defines its own lap functions.
I would love to see these operations portably available.
Interesting. If the CCL implementation of CAS on conses is that straightforward, perhaps I should bring the issue up in openmcl-devel. Thanks.
I would suggest a new library for these additions. Bordeaux Threads is quite stable and would benefit from not being hindered by new instability issues.
The functionality you propose falls under the category of atomic operations, which is related to threading but is still conceptually distinct.
A new atomic-op library would seem the best approach in my opinion.
I've considered the option of starting a new library, but haven't yet found a compelling argument not to use bordeaux-threads. Its maintainer agrees that atomic operations is within the scope of bordeaux-threads (Greg, you're the original author; do you agree?) and I don't think this addition would hinder the stability of bordeaux-threads existing functionality in any way. But I suppose the option you suggest is still on the table.
There are two additional reasons to make it a separate library. First, it is code-wise independent. Someone who is not using Bordeaux Threads should be able to use an Atomic Op library without introducing extra baggage. Why not?
Second, I wonder if you underestimate the stability issue? You have to find each version of each CL implementation that supports each operation. That's a lot of cases. It seems quite possible that something will be missed, at least on the first few releases. I would find it frustrating if Bordeaux Threads didn't compile as a result of new, independent functionality that I'm not even using.
Good point, anonymous person. I'll have to think about this some more!
I know this blog is ancient but was such a project/library ever created?
I didn't do it 😢, but Shinmera did! https://github.com/Shinmera/atomics
Post a Comment