Using Library Functions in Multi-threaded Code (Common Lisp)

Question

When a variable can be accessed/updated from multiple threads, it normally needs protection from simultaneous changes. One efficient approach is to use atomic functions to guarantee mutually exclusive access; eg, (sb-ext:atomic-incf *count*). Another approach is to wrap a lock around the updating operations like so (bt:with-lock-held (*lock*) (incf *count*)), but this is somewhat costly.

Is there an efficient way to include library functions (say from the alexandria library) in multi-threaded code? For example, if you want to do (alexandria:deletef x *list*) from multiple threads? Or would you need to do a lock? (ps: I'm assuming a deletef would need protection, but not entirely sure.)

Answer 1

Fully general, optimized multi-threaded code is notoriously difficult to write.

The simplest solution is usually to protect concurrent modifications with a lock, as in the example you provided: (bt:with-lock-held (*lock*) (incf *count*)). The performance is acceptable in most cases. I'd only consider the other options below if you benchmark your specific use case and find out that it is too slow for your needs.

Atomic operations as (sb-ext:atomic-incf *count*) are a very low-level primitive: very fast, but very difficult to compose correctly into more complex operations. If the features you need can be mapped one-to-one to atomic operations, you can just use them and you're done. But most of the times, you need to compose atomic operations to provide more complex features - and there comes the difficulty: you need to understand in deep detail the architecture you are using, including (lack of) memory ordering guarantees and memory barriers. And that's an extremely hard path to follow.

My library STMX provides supposedly intuitive and easy-to-compose primitives, as for example (stmx:atomic (incf *count*)). It internally uses atomic operations (if available) and Intel TSX transactional memory CPU instructions (only on sbcl x86-64 and only on Intel CPUs that have them) to optimize execution speed.

It has some caveats:

1. it only works on transaction-aware types, as tvar, tcell, tcons, tlist, tmap, tfifo, tchannel, classes defined with (stmx:transactional (defclass ...)) or structs defined with (stmx:transactional (defstruct ...))

2. code inside (stmx:atomic ...) may be retried multiple times in case of conflicts among multiple threads, so it should not perform I/O.

3. it's usually slower than hand-optimized code that uses atomic operations, but it is much easier to write, also because it is composable: (atomic (atomic (foo) (atomic (bar)) is a single transaction (not three) and is equivalent to (atomic (foo) (bar)).

In your specific case, you want to use existing, non-thread-safe library calls as (alexandria:deletef x *list*) in multi-threaded code i.e. you want to make them thread-safe.

If the libraries do not use and mutate global variables internally, then locks and atomic operations can be used successfully. Instead STMX can be used only if you modify concurrently transaction-aware types only - library-provided types can be used, but should be treated as read-only by concurrent code.

If instead the libraries use and mutate global variables internally, you are much more constrained and probably locks are the only viable solution.

P.S. please submit STMX issues at https://github.com/cosmos72/stmx/issues @Svante just updated https://github.com/cosmos72/stmx/issues/14 with @davipough error in the comments above, but exact versions are needed to troubleshoot the issue.

Answer 2

You could use STMX to get software transactions with “optimistic locking”.

This works with classes marked as transactional, or with transactional primitives also provided by the library: tcell, tcons etc. You'd need to use those, or wrap other things into them. The places in those structures are available to the places machinery, so library functions like alexandria:deletef just work.