STM against a mutex: Haskell and C++
A counter shared by two threads is the smallest concurrent program there is, and it is where the two languages disagree most sharply. In C++ the counter is a variable, the threads write it, and the language leaves it to the programmer to make that safe with a lock or an atomic. In Haskell the counter is a TVar and the only way to change it is a transaction, so a lost update cannot be written: the compiler does not accept the program that loses it.
Both sides count to four million from two threads here. The C++ programs come first, in the order a programmer meets them: the plain variable that loses updates, the mutex that fixes it and costs a lock per increment, and the atomic that fixes it without a lock. Then the Haskell one, and a table of the five runs each way on this machine.
Two threads and a counter
The first version is the one that looks right. Two threads, two million increments each, one long, and no synchronisation at all. counter = counter + 1 is three machine operations, a load, an add and a store, and nothing stops the other thread from running between them:
#include <cstdio>
#include <thread>
long counter = 0;
constexpr long per_thread = 2000000;
void bump() {
for (long i = 0; i < per_thread; ++i) {
counter = counter + 1;
}
}
int main() {
std::thread first(bump);
std::thread second(bump);
first.join();
second.join();
std::printf("%ld of %ld\n", counter, 2 * per_thread);
}
The build is at -O0 on purpose, and the reason is in the last chapter: an optimised build happens to print the right number here. Three runs of the unoptimised program:
g++ -std=c++23 -O0 -Wall -Wextra -pthread race.cpp -o race
./race; ./race; ./race; echo "status $?"
2452602 of 4000000
2526011 of 4000000
2506466 of 4000000
status 0
About two and a half million of four, and a different number every run. The increments are not lost at random: two threads that read the same value both write it back plus one, so one of the two additions disappears. The program prints a number, exits 0, and is wrong.
The mutex version puts a lock around the increment. It is correct, and it is slow, because the lock is taken four million times and two threads fight for it:
#include <chrono>
#include <cstdio>
#include <mutex>
#include <thread>
std::mutex guard;
long counter = 0;
constexpr long per_thread = 2000000;
void bump() {
for (long i = 0; i < per_thread; ++i) {
std::lock_guard<std::mutex> lock(guard);
++counter;
}
}
int main() {
const auto start = std::chrono::steady_clock::now();
std::thread first(bump);
std::thread second(bump);
first.join();
second.join();
const auto end = std::chrono::steady_clock::now();
const long ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
std::printf("%ld of %ld in %ld ms\n", counter, 2 * per_thread, ms);
}
g++ -std=c++23 -O2 -Wall -Wextra -pthread mutex.cpp -o mutex
for i in 1 2 3 4 5; do ./mutex; done; echo "status $?"
4000000 of 4000000 in 530 ms
4000000 of 4000000 in 669 ms
4000000 of 4000000 in 777 ms
4000000 of 4000000 in 494 ms
4000000 of 4000000 in 477 ms
status 0
The third way is the one a C++ programmer reaches for when the lock shows up in a profile: an std::atomic<long> with fetch_add, which is one instruction on x86-64 and needs no lock at all. The relaxed memory order is enough here because the only thing the program needs is the final total:
#include <atomic>
#include <chrono>
#include <cstdio>
#include <thread>
std::atomic<long> counter{0};
constexpr long per_thread = 2000000;
void bump() {
for (long i = 0; i < per_thread; ++i) {
counter.fetch_add(1, std::memory_order_relaxed);
}
}
int main() {
const auto start = std::chrono::steady_clock::now();
std::thread first(bump);
std::thread second(bump);
first.join();
second.join();
const auto end = std::chrono::steady_clock::now();
const long ms = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
std::printf("%ld of %ld in %ld ms\n", counter.load(), 2 * per_thread, ms);
}
g++ -std=c++23 -O2 -Wall -Wextra -pthread atomic.cpp -o atomic
for i in 1 2 3 4 5; do ./atomic; done; echo "status $?"
4000000 of 4000000 in 140 ms
4000000 of 4000000 in 126 ms
4000000 of 4000000 in 100 ms
4000000 of 4000000 in 143 ms
4000000 of 4000000 in 76 ms
status 0
A TVar and two threads
In Haskell the shared counter is a TVar Int, a mutable variable that can only be read and written inside atomically. modifyTVar' is the strict read-modify-write, and the transaction it runs in either applies entirely or is retried by the runtime, which is why no update can disappear: the two threads serialise on the variable, not on a lock the programmer wrote.
{-# LANGUAGE NumericUnderscores #-}
module Main (main) where
import Control.Concurrent (forkIO)
import Control.Concurrent.MVar (newEmptyMVar, putMVar, takeMVar)
import Control.Concurrent.STM (TVar, atomically, modifyTVar', newTVarIO, readTVarIO)
import Control.Monad (forM_, replicateM_)
import Data.Time.Clock (diffUTCTime, getCurrentTime)
import Text.Printf (printf)
perThread :: Int
perThread = 2_000_000
bump :: TVar Int -> IO ()
bump counter = replicateM_ perThread (atomically (modifyTVar' counter (+ 1)))
main :: IO ()
main = do
counter <- newTVarIO 0
done <- newEmptyMVar
start <- getCurrentTime
forM_ [1 .. 2 :: Int] $ \_ -> forkIO (bump counter >> putMVar done ())
replicateM_ 2 (takeMVar done)
end <- getCurrentTime
total <- readTVarIO counter
printf "%d of %d in %d ms\n" total (2 * perThread) (round (diffUTCTime end start * 1000) :: Int)
-threaded gives the runtime real OS threads; +RTS -N2 gives it two capabilities, so the two Haskell threads run on two cores, which is the fair comparison with two C++ threads. -rtsopts is what allows the flags on the command line.
ghc -Wall -O1 -threaded -rtsopts -o stm-hs Stm.hs
for i in 1 2 3 4 5; do ./stm-hs +RTS -N2 -RTS; done; echo "status $?"
4000000 of 4000000 in 654 ms
4000000 of 4000000 in 698 ms
4000000 of 4000000 in 441 ms
4000000 of 4000000 in 815 ms
4000000 of 4000000 in 656 ms
status 0
Every run is exactly four million. The number of milliseconds is not the point of this program and the next chapter is about it, but the total never moves, which is the property the C++ plain variable did not have.
Locks against transactions
A mutex is a lock: take it, change something, release it, and keep the critical section short. A transaction is a block of reads and writes that the runtime applies atomically, and the difference is what composes. Two atomic operations on two variables cannot be combined into one atomic operation with locks without a second lock and a rule about the order to take them; with STM the two reads and two writes sit in one atomically and the runtime takes care of it. retry and orElse go further and let a thread wait for a condition or try two alternatives, which is the subject of the course lessons on STM patterns.
The price is the runtime. Every transaction logs its reads and writes, and a conflict means a retry, so a workload that hammers one variable is the worst case for STM and the best case for a mutex: the lock makes the two threads take turns, and the transaction makes them take turns and check whether anybody else touched the log. The table below is that effect, measured.
Neither replaces the other. STM is the right tool when several variables must change together or when a thread must wait for a condition; a mutex or an atomic is the right tool for one counter, which is what this page measures. A C++ program that needs transactional semantics writes the log and the rules itself, or takes a library, and that is the cost the Haskell version does not pay.
The numbers on this machine
Four million increments from two threads, five runs each way, all with the same total so that the only difference is the mechanism. The machine is the container of this site: 4 CPUs (nproc 4), Alpine Linux 3.24.3 on x86_64, g++ 15.2.0 with -std=c++23 -O2 -Wall -Wextra -pthread, GHC 9.10.3 with -Wall -O1 -threaded -rtsopts and the default RTS settings apart from -N2. The container may be loaded by other work, so the minimum is the number to trust and the median is the one to quote.
| Way | The five runs, ms | Min | Median |
|---|---|---|---|
| C++ std::mutex | 530, 669, 777, 494, 477 | 477 | 530 |
| C++ std::atomic, relaxed | 140, 126, 100, 143, 76 | 76 | 126 |
| Haskell STM, +RTS -N2 | 654, 698, 441, 815, 656 | 441 | 656 |
| Haskell STM, +RTS -N1 (for contrast) | 261, 263, 265 | 261 | 263 |
The last row is the interesting one. The same program with one capability and two Haskell threads is faster than with two capabilities, because the work is one hot variable and the second capability only adds contention. The two threads still interleave on one capability, which is why the total is still exactly four million. STM does not make a bad parallel workload good; it makes a correct one easy to write.
The atomic is the fastest because the work per increment is one instruction and there is no lock and no log. It is also the least useful of the four for anything but a counter: an atomic gives a total, not a consistent view of several variables.
The race the optimiser hides
The first program, compiled at -O2 instead of -O0, prints the right number three times:
g++ -std=c++23 -O2 -Wall -Wextra -pthread race.cpp -o race-fast
./race-fast; ./race-fast; ./race-fast; echo "status $?"
4000000 of 4000000
4000000 of 4000000
4000000 of 4000000
status 0
Nothing became correct. The optimiser may keep the counter in a register or reorder the loop, and either can hide the missing synchronisation on this machine, with this compiler, today. A data race in C++ is undefined behaviour, so a program that prints the right answer is not evidence that it would print it on another machine or after the next compiler update. This is the reason the C++ programs above are built at -O2 only where they are correct and at -O0 where the race is the lesson.
The tools that find this are not runnable in this container: ThreadSanitizer fails to start here, and the page on tooling shows that error rather than a report. AddressSanitizer does work, and it finds memory bugs, not races.
The Haskell lesson on the subject is STM and the one on -threaded and the RTS explains why -N2 is not always twice as fast. The next page in this set is Throughput: the same loop in both.
The C++ programs were built with g++ 15.2.0 (Alpine 15.2.0) using -std=c++23 -Wall -Wextra -pthread with -O2 or -O0 as stated, and the Haskell program with GHC 9.10.3 using -Wall -O1 -threaded -rtsopts, all run on a 4-CPU Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev