Home

Awesome

STMX

Summary

STMX is a high-performance implementation of composable Transactional Memory (TM) for Common Lisp. TM is a concurrency control mechanism aimed at making concurrent programming easier to write and understand. Instead of traditional lock-based programming, one programs with atomic memory transactions, which can be composed together to make larger atomic memory transactions.

A memory transaction gets committed if it returns normally, while it gets rolled back if it signals an error (and the error is propagated to the caller).

Finally, memory transactions can safely run in parallel in different threads, are re-executed from the beginning in case of conflicts or if consistent reads cannot be guaranteed, and their effects are not visible from other threads until they commit.

Memory transactions give freedom from deadlocks, are immune to thread-safety bugs and race conditions, provide automatic roll-back on failure, and aim at resolving the tension between granularity and concurrency.

News

Latest news, 1st March 2020

Fixed STMX for internal changes in SBCL 2.0.0 and SBCL 2.0.2. Updated list of Intel CPUs supporting memory transactions in hardware (Intel TSX) - see below.

News, 16th January 2015

Version 2.0.1 released. It adds support for transactional structs in addition to transactional CLOS objects, and a faster, struct-based implementation of transactional CONS cells and lists, including several list-manipulating functions - see util/tcons.lisp and util/tlist.lisp

Unluckily, the hardware bug that prompted Intel to disable hardware transactional memory (TSX) in August 2014 is still there, and very few new models are available without the bug. So for the moment STMX will be software-only on many CPUs.

Older news

See the file NEWS.md

General documentation

An introduction is available to explain more in detail what STMX is, what it is not, and how it is implemented.

For background information, Composable Memory Transactions is a very good - though a bit technical - explanation of memory transactions and how they are used and combined. For the interested reader, it also goes in deep detail on how to actually implement them.

Supported systems

STMX is currently tested on the following Common Lisp implementations:

Partially supported systems

Untested systems

STMX will probably work on several other Common Lisp implementations as long as they support log4cl, closer-mop, bordeaux-threads and trivial-garbage, but the author gives no guarantees.

Installation and loading

Stable version - from Quicklisp

STMX is available from Quicklisp. The simplest way to obtain it is to first install Quicklisp then run these commands from REPL:

CL-USER> (ql:quickload "stmx")
;; lots of output...
CL-USER> (use-package :stmx)

If all goes well, this will automatically download and install the stable branch of STMX and its dependencies:

Latest version - from GitHub

In case you want to use the "latest and greatest" version directly from the author, in order to get the newest features - most notably hardware memory transactions - improvements, bug fixes, and occasionally new bugs, you need to download it into your Quicklisp local-projects folder. Open a shell and run the commands:

$ cd ~/quicklisp/local-projects
$ git clone git://github.com/cosmos72/stmx.git

then proceed as before - load a REPL and run:

CL-USER> (ql:quickload "stmx")
;; lots of output...
CL-USER> (use-package :stmx)

If all goes well, it will automatically load STMX and its dependencies.

Note: unless you know what you are doing, do not try to load different STMX versions one after the other from the same REPL - strange things may happen.

Other versions - from Sourceforge

All the stable versions of STMX, present and past, are also available from Sourceforge, including version 1.9.0.

Troubleshooting

In case you get errors:

Testing that it works

After loading STMX for the first time, it is recommended to run the test suite to check that everything works as expected. From the REPL, run:

CL-USER> (ql:quickload "stmx.test")
;; lots of output...
CL-USER> (fiveam:run! 'stmx.test:suite)
;; even more output...
 Did 7133 checks.
    Pass: 7133 (100%)
    Skip: 0 ( 0%)
    Fail: 0 ( 0%)

Note: (ql:quickload "stmx.test") intentionally works only after (ql:quickload "stmx") has completed successfuly.

The test suite should report zero Skip and zero Fail; the number of Pass may vary. You are welcome to report any failure you get while running the test suite, please include in the report:

See "Contacts, help, discussion" below for the preferred method to send the report.

Basic usage

STMX offers the following Lisp macros and functions, also heavily documented in the sources - remember (describe 'some-symbol) at REPL.

Input/Output during transactions

WARNING: since transactions will be re-executed in case of conflicts with others and can also rollback or retry, all code inside an atomic block may be executed more times than expected, or may be executed when not expected.

Some transactional memory implementations, especially for statically-typed languages, forbid performing input/output during a transaction on the ground that I/O is not transactional: if a transaction sends an irreversible command to the outside world, there is no way to undo it in case the transaction rolls back, retries or conflicts.

STMX does not implement such restrictions, i.e. I/O and any other irreversible action can also be performed inside an atomic block. This means you are free to launch missiles during a transaction, and destroy the world when you shouldn't have. You have been warned.

Despite the risk, there are at least two reasons for such a design choice:

The typical solution for the above risk is: during a transaction, perform I/O only for debugging purposes, for example using a logging library as log4cl (or whatever is appropriate for your program), and queue any I/O operation in a transactional buffer. Then, invoke a separate function that first runs a transaction to atomically consume the buffer and only later, outside any transaction, performs the actual I/O operation.

An alternative solution is: during a transaction, instead of performing I/O pass to AFTER-COMMIT a function that will perform I/O when executed. Note: AFTER-COMMIT is described in Advanced usage below, read it carefully because functions executed by AFTER-COMMIT have several restrictions on what they are allowed to do.

Advanced usage

For those cases where the basic features are not sufficient, or where more control is desired during the execution of transactional code, some advanced features are available:

Hardware transactions

STMX versions 1.9.0 or later can take advantage of hardware transactions on Intel CPUs that support Transactional Synchronization Extensions (TSX) As of February 2020, many recent consumer and server Intel CPUs support them, including at least:

(This list is necessarily incomplete. To check whether a specific Intel CPU supports Transactional Synchronization Extensions (TSX) browse https://ark.intel.com/)

To actually use hardware transactions from STMX, there are two more requirements:

Also, hardware transactions only work in compiled code - SBCL sometimes interprets very short functions and simple code executed at REPL instead of compiling them, which may cause hardware transactions to fail.

How to tell if hardware transactions are supported

There are several ways. The easiest are:

How to use hardware transactions

STMX automatically uses hardware transactions if they are supported. There is no need for special commands, just execute the usual (ATOMIC ...) or (RUN-ATOMIC ...) forms.

Hardware transactions have several limitations, and STMX will seamlessly switch to (slower) software transactions in the following cases:

Utilities and examples

See the example and util folder, which contains several examples and utilities built with STMX and should be relatively straightforward to understand. The folder util contains the following classes with related methods and functions, all in the STMX.UTIL package - for more details, use (describe 'some-symbol) at REPL:

Performance

STMX automatically discovers and takes advantage of many optional, non-standard features of the underlying Common Lisp compiler. It also performs graceful degradation, i.e. if the fastest version of a feature is not available it automatically switches to a slower, available alternative.

Depending on the available features, STMX performance can vary up to a factor 100 or more (!).

To reach its peak performance, several requirements need to be satisfied by the hardware and by the Lisp compiler being used. They are listed here in order of importance:

Hardware requirements:

Lisp compiler requirements:

  1. it must have good multi-threading support. Without it, what would you need a concurrency library as STMX for?
  2. it must expose atomic compare-and-swap operations, to implement fast mutexes. A much slower alternative, but still better than nothing, is to expose a function that returns which thread has acquired a bordeaux-threads lock.
  3. it must produce fast, highly optimized code.
  4. it must be 64-bit. 32-bit is much slower because transactional memory version counters are then BIGNUMs instead of FIXNUMs.
  5. it must expose memory barrier operations. This is less important on x86 and x86-64, and more important on unordered architectures (almost all others).

Among the non-commercial Lisp compilers, SBCL is the only one known to STMX author that satisfies all the compiler requirements, and (guess why) the only one where STMX author has implemented support for hardware transactions.

Actually, all the other tested free Lisp compilers (ABCL, CCL, CMUCL, ECL) are at least somewhat lacking in the area "fast, highly optimized code", and none of them offers atomic compare-and-swap or memory barrier operations at all. One - CMUCL - produces relatively fast code, but does not support native threads. STMX is not tested on any commercial Lisp compiler, so performance on them is simply unknown.

For these reasons, STMX will reach the highest known performance on SBCL by a large margin - possibly by a factor from 10 to 100 or more with respect to other tested systems.

For more performance considerations and a lot of raw numbers produced by running micro-benchmarks, see the included files doc/benchmark.md, doc/benchmark-abcl.md, doc/benchmark-ccl64.md and doc/benchmark-cmucl.md.

The short version is: as of March 2015, on a fast consumer PC (Core i7 4770 @ 3.5GHz or better) with 64-bit SBCL 1.1.9 or better, STMX can execute more than 35 millions hardware transactions per second per CPU core, and more than 7 millions software transactions per second per CPU core. The second platform in terms of performance is CCL (x86_64), that reaches 1.1 millions software transactions per second per CPU core using two threads, but STMX performance quickly decreases with more threads (reason still needs to be investigated).

A small example with very short transactions is the dining philosophers, with 5 reads and 5 writes to transactional memory per atomic block, where each CPU core runs approximately 4.5 millions software transactions per second - hyperthreading has very limited effects.

Obviously, performance in other usage scenarios will depend on the complexity of the code inside transactions, on the availability of hardware transactions, on the number of reads and writes to transactional memory, and the rate of conflicts and rollbacks.

Note

These result are not absolute performance considerations of the tested Lisp systems. They are simply the outcome of running micro-benchmarks of a particular library optimized for SBCL (see the hardware transactions, atomic compare-and-swap and memory barriers considerations) on several other Lisp systems. Do not try to construct these results as STMX author's opinions on the mentioned Lisp systems.

Lee-STMX

For a less artificial and hopefully more realistic benchmark, the author has ported Lee-TM, a non-trivial benchmark suite for transactional memory developed in 2007 by the University of Manchester (UK). The result is Lee-STMX - as of July 2013, its status is BETA.

Contacts, help, discussion

As long as the traffic is low enough, GitHub Issues can be used to report test suite failures, bugs, suggestions, general discussion etc.

If the traffic becomes high, more appropriate discussion channels will be set-up.

The author will also try to answer support requests, but gives no guarantees.

Status

As of July 2013, STMX is being written by Massimiliano Ghilardi and is considered by the author to be stable.

STMX is a full rewrite of CL-STM, which has been developed by Hoan Ton-That for the Google Summer of Code 2006.

Donations

STMX is a spare-time project. Donations can help the project by recognizing its usefulness and covering expenses.

You can <a href="http://stmx.org/donations">donate with PayPal or credit card</a>.

Legal

STMX is released under the terms of the Lisp Lesser General Public License, known as the LLGPL.