2012-06-06

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 and CDR.
  • SYMBOL-PLIST.
  • SVREF.
  • MOP's STANDARD-INSTANCE-ACCESS and FUNCALLABLE-STANDARD-INSTANCE-ACCESS.

Table 1. CAS support per place.
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!

6 komentoj:

Greg Pfeil disse...

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.

Luís disse...

Interesting. If the CCL implementation of CAS on conses is that straightforward, perhaps I should bring the issue up in openmcl-devel. Thanks.

Anónimo disse...

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.

Luís disse...

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.

Anónimo disse...

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.

Luís disse...

Good point, anonymous person. I'll have to think about this some more!

Kategorioj