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.¹ 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.)

¹ (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!