Part 2 of 7 · 2 min read
Scalability
Think of it this way. A supermarket with one till serves a queue slowly. Adding a second till should halve the waiting, but not if both tills share one card reader that only one customer can use at a time. The analogy stops in one place: shops add tills freely, and this machine has two processors, so the gain from threads can never exceed two.
In plain words: A data structure is scalable if its throughput grows as threads are added, up to the number of processors. A structure that runs slower with two threads than with one is the opposite, and it is common when every operation takes one lock.
The simplest counter is a shared integer under a mutex, as in Level 2, page 4. The test gives each thread 2,000,000 increments to do, so with n threads the total work grows with n. A perfectly scalable counter would take the same time for 1, 2 or 4 threads on enough processors, since each thread does the same amount of work, in parallel. On two processors, the time for 4 threads should be about twice the time for 1, as the 4 threads share 2 processors.
The result for the mutex counter (median seconds):
| Threads | Total increments | Time |
|---|---|---|
| 1 | 2,000,000 | 0.042 |
| 2 | 4,000,000 | 0.291 |
| 4 | 8,000,000 | 0.573 |
Per increment, the cost rises from 21 ns (one thread, no contention) to 73 ns (two threads, 0.291 s over 4,000,000 increments) and 72 ns (four threads). Two threads that run in parallel take seven times as long as one thread for twice the work. The reason is contention (page 3): the lock's cache line has to move between the two processors on every acquisition (Level 2, page 6), and sleeping and waking threads cost system calls.
An atomic counter, __atomic_fetch_add on a shared long, avoids the sleeping:
| Threads | Time (atomic) |
|---|---|
| 1 | 0.018 |
| 2 | 0.096 |
| 4 | 0.203 |
It is about three times faster than the mutex. It still has the shared cache line, so two threads cost 24 ns per increment against 9 ns for one. The line bouncing remains.
Scalability
Scalability is the ability of a program or data structure to do more work per unit time as the number of threads (up to the number of processors) increases, with efficiency measured as the speed-up divided by the number of processors (Level 2, page 6).
Example: a counter whose two-thread run takes seven times as long as the one-thread run for twice the work does not scale.
Check yourself: 1. Why does the mutex counter cost more per increment with two threads than with one? 2. What is the per-increment cost of the atomic counter with 4 threads? 3. What stays the same in the atomic counter that still limits it?