Concurrency vs Parallelism: Interleaving, Nondeterminism and Amdahl's Law

Version note: The code in this post was built and run with .NET 10 (C# 14); tests use xUnit v3 4.0.3 and measurements were taken with BenchmarkDotNet 0.15.8. The measurement platform is ARM64 (10 cores: 4 performance and 6 efficiency cores); statements about x64 are based on documentation.

Guess First

The month-end report of Bookstore, the online bookstore used as the shared example across this site's series, takes 360 ms on a single thread. Emre from the team says that once the work is spread with Parallel.For, the report will run 64 times faster on a 64-core server. But 10% of the report has to run in order by its nature: every line's audit hash includes the previous line's hash. At most how much faster can 64 cores make it? And when we measure on a 10-core machine, will 10 workers beat 8?

Second question: two threads each do a three-step job. In how many different orders can these six steps run? If you start both threads together a hundred thousand times, how many of those orders will you actually see? We answer both with real runs. This is the first post of the Concurrency Theory series; the series is not about APIs but about why concurrent code behaves the way it does.

Concurrency and Parallelism Are Not the Same Thing

The two words are used interchangeably in everyday talk, but they describe different things. Concurrency is about the structure of a program: several jobs have started in the same time window and have not finished yet, so they overlap. Parallelism is about execution: more than one instruction is really running at the same moment. That is also the core of Rob Pike's talk "Concurrency is not parallelism", given at Heroku's Waza conference in 2012: concurrency is building work as independent pieces; parallelism is being able to run those pieces at the same time.

A single-core machine has concurrency too. The scheduler gives threads time slices in turn; each thread makes some progress and is interrupted. We looked at this slicing in detail in the scheduling and context switch post of the Operating System Fundamentals series; what matters here is the consequence: even on one core, the steps of two threads get mixed. Parallelism needs more than one core. The multi-core post of the How Computers Work series explains what cores share.

There is also the kind of work. An I/O-bound job (a database query, an HTTP call) spends most of its time waiting; the gain there comes not from the number of cores but from releasing the thread while waiting, which is the subject of the first post of the C# Asynchronous Programming series. A CPU-bound job (computing a report, compression, hashing) keeps a core really busy; it only gets faster through parallelism. The Amdahl calculation in this post is for CPU-bound work.

Interleaving: In How Many Orders Can Two Threads Run?

An interleaving is how the steps of several threads are ordered on a single timeline. Each thread runs its own steps in its own order; the only thing that can change is how the steps mix with each other. If two threads have two steps each, six orders are possible, and we can draw them as a tree:

The general formula is simple combinatorics: if n threads each do k atomic steps, the number of possible orders is (n·k)! / (k!)^n. Let's write a small method that produces the orders one by one:

// Each list keeps its own order; only the mix changes
public static IEnumerable<string[]> Enumerate(string[] a, string[] b)
{
    if (a.Length == 0) { yield return b; yield break; }
    if (b.Length == 0) { yield return a; yield break; }
    foreach (string[] rest in Enumerate(a[1..], b))
        yield return [a[0], .. rest];
    foreach (string[] rest in Enumerate(a, b[1..]))
        yield return [b[0], .. rest];
}

Now let's apply these orders to a stock counter. Two threads each increase the stock of the same book by one, and stock = stock + 1 splits into three steps: read the value, add one, write it back. RunIncrement simulates each order step by step and returns the final value:

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- interleavings

interleavings: 20, final=2: 2, final=1: 18
2 threads x 3 steps -> 20
2 threads x 10 steps -> 184,756
3 threads x 10 steps -> 5,550,996,791,340
4 threads x 10 steps -> 4,705,360,871,073,570,227,520

Only two of the twenty orders give the right result: when one thread runs completely before the other, or completely after it. In the other eighteen, both threads read the same old value and one increment is lost. The number of orders explodes as steps grow: four threads with ten steps each have 4.7 × 10^21 orders. That number is why you cannot test concurrent code "by trying every case". We classify these bugs in detail in the next post.

Nondeterminism: Where "Works on My Machine" Comes From

All orders are possible, but they are not equally likely. To see this, I released two threads at the same moment with a Barrier, had each write three entries, and repeated the experiment a hundred thousand times:

private static void Steps(string name, ConcurrentQueue<string> log, Barrier start)
{
    start.SignalAndWait();
    for (int i = 1; i <= 3; i++)
        log.Enqueue($"{name}{i}");
}

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- observe 100000

100,000 runs, 13 distinct orders out of 20
BBBAAA   99,598   99.60%
AAABBB      248    0.25%
BAAABB      125    0.12%
BBAAAB       15    0.01%
BABABA        4    0.00%
BBABAA        2    0.00%
BABBAA        2    0.00%
ABAABB        1    0.00%
ABBBAA        1    0.00%
AABABB        1    0.00%
BBAABA        1    0.00%
BAABBA        1    0.00%
ABABAB        1    0.00%

Thirteen of the twenty orders showed up, but the distribution is heavily skewed: in 99.6% of the runs B finishes first. The reason is how Barrier works: the last thread to arrive continues without waiting, while the thread that arrived first waits to be woken up. Waking up takes a few microseconds, and B finishes its three small steps in that time. When I ran the same command twice more, I saw 8 and 12 distinct orders; even which orders appear changes from run to run.

This is where "works on my machine" comes from. On your machine, under your load, the rare orders may never come; in production, a different CPU, a different load and a different thread pool state make them frequent. According to the 2008 study by Shan Lu and colleagues, which examined 105 real concurrency bugs from MySQL, Apache, Mozilla and OpenOffice, 92% of those bugs can be triggered reliably by forcing a specific order on no more than four memory accesses. The problem is not complex orders but short, rare ones.

Bugs like this are called Heisenbugs: bugs that disappear when you try to observe them. The term spread with Jim Gray's 1985 report "Why Do Computers Stop and What Can Be Done About It?". Adding a Console.WriteLine, setting a breakpoint or switching to a Debug build changes the timing, and the faulty order goes away. Techniques for catching races in the debugger are in the multi-thread debugging post of the Debugging and Problem Solving series; in this series we learn to define the bug on paper, through orders and invariants.

Amdahl's Law: The Serial Part Sets the Ceiling

Back to the speed question. In a short paper published in 1967, Gene Amdahl argued that the part of a program that cannot be parallelized puts an upper bound on the achievable speedup; the formula we use today is a later write-up of that idea. If a fraction s of the single-thread time is serial and the rest can be split across N cores, the speedup is 1 / (s + (1 − s) / N). As N goes to infinity, the value approaches 1 / s:

public static double Speedup(double serialFraction, int cores) =>
    1.0 / (serialFraction + (1.0 - serialFraction) / cores);

public static double Limit(double serialFraction) => 1.0 / serialFraction;

With a 10% serial part, the best speedup 64 cores can give is 1 / (0.1 + 0.9 / 64) = 8.77 times; even with infinite cores you cannot pass 10 times. That is why Emre's 64x expectation in the first guess falls apart. If the serial part drops to 5%, 64 cores give 15.4 times; if it rises to 25%, only 3.7 times. The right panel of the figure shows these three curves.

Measurement: The Bookstore Report Job

To compare the theory with a real job, I modelled the monthly report of institutional orders: 200,000 orders, each with 22 different books. The report has two phases. In the first, each order's total and a SHA256 fingerprint of its lines are computed; each order only looks at itself, so this phase can run in parallel. The second phase is the audit chain: each link is the hash of the previous link's hash and the order's fingerprint. Computing a link requires knowing the previous one, so this part is serial:

public static (decimal Revenue, string AuditHash) Build(Order[] orders, int workers)
{
    decimal[] totals = new decimal[orders.Length];
    byte[] fingerprints = new byte[orders.Length * HashSize];
    Parallel.For(0, orders.Length, new ParallelOptions { MaxDegreeOfParallelism = workers }, i =>
    {
        totals[i] = Summarize(orders[i], fingerprints.AsSpan(i * HashSize, HashSize));
    });
    byte[] audit = new byte[HashSize];
    Chain(fingerprints, audit);
    return (totals.Sum(), Convert.ToHexString(audit)[..16]);
}

// Serial part: every audit hash includes the previous one, so it cannot be split
public static void Chain(ReadOnlySpan<byte> fingerprints, Span<byte> chain)
{
    Span<byte> buffer = stackalloc byte[2 * HashSize];
    chain.Clear();
    for (int offset = 0; offset < fingerprints.Length; offset += HashSize)
    {
        chain.CopyTo(buffer);
        fingerprints.Slice(offset, HashSize).CopyTo(buffer[HashSize..]);
        SHA256.HashData(buffer, chain);
    }
}

We covered Parallel.For itself in the parallelism post of the C# Asynchronous Programming series; here we only use it to limit the number of workers. Each order's result goes to its own index, so threads do not write to the same memory and the result does not depend on the number of workers. First, let's measure both phases on a single thread to find the serial fraction:

dotnet run -c Release --project src/Bookstore.ConcurrencyLab -- report-phases 200000 22

orders=200,000 summarize=328 ms chain=37 ms serial fraction=10.2 %
Amdahl n= 2: 1.82x
Amdahl n= 4: 3.07x
Amdahl n= 8: 4.67x
Amdahl n=10: 5.22x
Amdahl n=64: 8.64x
limit: 9.83x

The serial fraction is 10.2%, and the theory says 8.64 times for 64 cores. Now let's measure 1, 2, 4, 8 and 10 workers with BenchmarkDotNet:

dotnet run -c Release --project bench/Bookstore.ConcurrencyLab.Benchmarks -- --filter "*ReportBenchmarks*"

| Method      | Orders | Workers | Mean          | StdDev        |
|------------ |------- |-------- |--------------:|--------------:|
| SingleChain | 200000 | 1       | 363,621.43 us | 10,610.172 us |
| SingleChain | 200000 | 2       | 203,420.68 us |  1,768.823 us |
| SingleChain | 200000 | 4       | 129,589.39 us |    450.475 us |
| SingleChain | 200000 | 8       | 104,962.35 us |  5,933.538 us |
| SingleChain | 200000 | 10      | 112,846.34 us |  7,923.190 us |

The speedups are 1.79 with 2 workers, 2.81 with 4, 3.46 with 8 and 3.22 with 10. With 2 workers the measurement is almost identical to the theory (1.82). With 4 workers we are slightly below it (2.81 instead of 3.07); the cost of distributing the work and waking threads starts to show. With 8 and 10 workers the gap is large, and 10 workers are not faster than 8; the two measurements are the same within the standard deviation.

The reason is a silent assumption in Amdahl's law: all cores run at the same speed. The machine I measured on has 4 performance and 6 efficiency cores, and the efficiency cores do the same work more slowly. Up to 4 workers the work mostly runs on the fast cores; after that, each added worker contributes less. This is common in the x64 world too: since the 12th generation, most of Intel's desktop processors mix performance and efficiency cores. On a server with identical cores we would expect the curve to stay closer to Amdahl, but I did not measure that; running the same benchmark on your own machine and comparing is the most instructive part of this post.

Shrinking the Serial Part, and Gustafson

The real lesson of Amdahl's law is that the serial part, not the core count, sets the ceiling. Instead of adding cores, let's shrink the serial part. If we build the audit chain separately for each day, the 31 chains can be computed in parallel; only linking the 31 day hashes into one chain stays serial:

Parallel.For(0, starts.Length - 1, new ParallelOptions { MaxDegreeOfParallelism = workers }, d =>
{
    Chain(fingerprints.AsSpan(starts[d] * HashSize, (starts[d + 1] - starts[d]) * HashSize),
        dayHashes.AsSpan(d * HashSize, HashSize));
});
byte[] audit = new byte[HashSize];
Chain(dayHashes, audit);

| Method      | Orders | Workers | Mean          | StdDev        |
|------------ |------- |-------- |--------------:|--------------:|
| PerDayChain | 200000 | 1       | 351,856.57 us |    793.487 us |
| PerDayChain | 200000 | 4       | 109,433.71 us |  3,904.916 us |
| PerDayChain | 200000 | 8       |  89,755.72 us |  4,592.320 us |
| PerDayChain | 200000 | 10      |  78,001.59 us |  8,427.606 us |

On the same machine, 10 workers now give a 4.66x speedup, and going from 8 to 10 still pays off. This is a design change: the audit hash is now a different value, and the business side (Selin) has to accept a per-day chain. Most concurrency decisions are like this; the speedup comes not from a trick in the code but from changing the dependency structure of the data.

In 1988 John Gustafson looked at Amdahl's law from a different angle: in real life, when the core count grows, the problem usually grows too. If the serial time stays fixed and the parallel work grows with the core count, the scaled speedup is s + (1 − s) · N; for a 10% serial part and 64 cores that is 57.7 times. This optimistic picture does not hold for our report, because with a single chain the serial part grows with the number of orders: when orders double, the chain doubles too, and the fraction stays at 10%. Gustafson's model fits work whose serial part does not depend on the problem size; the per-day chain moves the report closer to that side.

In Production

Measure the serial fraction before you parallelize; do not guess it. In our report the serial part looked small in the code but was 10% of the time in reality. Timing the phases separately with a Stopwatch and making the worker count a parameter in BenchmarkDotNet takes a few minutes, and the result directly informs how many cores you pay for.

The server's core count and the core count your application sees may differ. A container's CPU limit, a VM's vCPU count and shared cores in the cloud change the behaviour of Environment.ProcessorCount and the thread pool. In the scheduling post of the Operating System Fundamentals series we measured how a container CPU limit turns into throttling; if you run a parallel job in a pod with a CPU limit, do the Amdahl calculation against that limit.

The parallel version must produce the same result as the serial version, and you should test that. Our test builds the report with 1, 2, 4 and 8 workers and checks that the totals and the audit hash are exactly the same. The most common failure of parallel code is not slowness but silently producing a wrong result.

[Theory]
[InlineData(2)]
[InlineData(4)]
[InlineData(8)]
public void Parallel_report_equals_single_threaded_report(int workers) =>
    Assert.Equal(MonthlyReport.Build(Orders, 1), MonthlyReport.Build(Orders, workers));

dotnet test

Test run summary: Passed!
  total: 10
  failed: 0
  succeeded: 10
  skipped: 0

Common Pitfalls

The "more threads means faster" assumption. In the measurement, 10 workers were not faster than 8; opening more CPU-bound threads than cores adds context switches and gains nothing. With small jobs it is even clearer: in the same benchmark, 8 workers made the 50-order report only 1.8 times faster (from 85 µs to 47 µs), because the fixed cost of distributing work and waking threads is on the same scale as the work itself.

Forgetting the coordination cost. Merging the results of parallel pieces, writing to a shared counter or waiting on a shared lock all add to the serial part and increase Amdahl's s. In our report each worker writes to its own index, so there is no merge cost; had we updated a shared Dictionary under a lock, the serial fraction would be well above 10%.

Treating a rare order as impossible. The ABABAB order, seen once in a hundred thousand runs, is an order seen hundreds of times a day by a service that processes thousands of orders a second. Read an interleaving you have not seen in tests as "not hit yet", not as "does not happen".

Mixing up concurrency and parallelism and picking the wrong tool. Trying to speed up an I/O-waiting job with Parallel.For fills the thread pool with waiting threads; the right tool there is async/await. Making a CPU-bound job async does not make anything faster by itself.

A Small Experiment

★☆☆ In the observe command, have each thread write ten steps instead of three and compare how many distinct orders you see with the 184,756 possible ones. Then add Thread.Sleep(1) at the start of the Steps method and watch how the distribution changes.

★★☆ Run the report-phases command with 8-line orders instead of 22. How did the serial fraction change? Compare Amdahl's 8-worker prediction for the new fraction with the value the benchmark measures.

★★★ Run the benchmark on your own machine and plot the speedup curve. Find out whether your cores are identical or mixed, and try to explain the points where the measurement departs from Amdahl. Measure the serial fraction of the per-day chain with a Stopwatch and compute the theory's 10-worker prediction.

In this post we saw an increment lost in eighteen of twenty orders, but we did it with a simulation. In the next post we produce the same bug with real threads and give it a name: why a race condition and a data race are different things, how to recognize check-then-act and read-modify-write bugs, and why a decimal price can be read half old, half new.