Pointer Walk

Do More Threads Make It Faster?

The same job on 1, 2, 4, 8 and 16 threads with a shared lock in the middle. Past the number of cores the gains stop, then reverse.

ConcurrencyIntermediate8 min read

More hands, less time?

A job takes 100 seconds on one thread. Your machine has 8 cores. Surely 8 threads will finish it in 12.5 seconds, and 16 threads faster still?

It is one of the most natural assumptions in programming, and it is usually wrong. Sometimes more threads make a program slower.

How much faster, with more threads?Interactive
Under a lock

Times faster than a single thread

1.0x
1 thread
2 threads
4 threads
8 threads
16 threads
32 threads

Start. A job that takes 100 units of time on one thread, on a machine with 8 cores. 20% of it must be done inside a shared lock, one thread at a time.

Try all three settings. With nothing shared, it scales cleanly up to the number of cores. With a fifth of the work under a lock, 8 threads manage only about 2.5 times. With half under a lock, adding threads is nearly pointless.

Three separate things hold the bars down.

Limit 1: the part that cannot be shared

Most jobs have some work that only one thread can do at a time: reading the input, updating a shared total, writing the result, anything inside a lock. Call it the serial part.

Threads speed up only the rest.

Example

Painting a house

Painting the walls takes 80 hours and can be split between painters. Waiting for the paint to dry takes 20 hours and cannot.

One painter: 80 + 20 = 100 hours.

Four painters: 20 + 20 = 40 hours. Two and a half times faster, not four.

A thousand painters: nearly 0 + 20 = 20 hours. Five times faster, and that is the ceiling. No number of painters makes paint dry quicker.

This is Amdahl's law. If a fraction of the job is serial, the best possible speed-up is one divided by that fraction.

Serial partBest possible speed-up, with unlimited cores
50%2 times
20%5 times
10%10 times
5%20 times
1%100 times

A job that is 95% parallel sounds almost perfectly parallel. It can never go more than 20 times faster, however many cores you buy.

Limit 2: the number of cores

A thread needs a core to run on. With 8 cores, at most 8 threads are actually running at any instant. Threads 9 to 16 are not helping. They are waiting for a turn.

So for work that is pure computation, threads beyond the number of cores add nothing. That is the plateau.

Limit 3: threads cost something

They are not free, and past the plateau the costs are all that is left.

  • Switching. With more threads than cores, the operating system keeps pausing one and resuming another. Each switch takes time, and the resumed thread finds the processor's cache full of someone else's data.
  • Fighting over locks. The more threads want the same lock, the longer the queue for it, and the more time is spent waiting and waking up.
  • Memory. Each thread needs its own stack.

That is why the bars do not just flatten. They fall.

When more threads than cores is right

Everything above is about work that keeps the processor busy. Much real work is not like that. A thread waiting for a database reply or a network response is not using a core at all.

If each task spends 90% of its time waiting, then one core can keep about ten such threads going. This is why a web server may run hundreds of threads on a handful of cores.

Kind of workSensible number of threads
Mostly computing (image processing, compression, number crunching)About the number of cores
Mostly waiting (network calls, database queries, disk)Many more than the number of cores

For waiting-heavy work there is also another approach altogether: one thread that juggles many tasks without blocking. See Async/Await.

Making parallel work actually faster

  1. Measure first

    Find where the time goes. The serial part is often smaller, or larger, than you think.

  2. Shrink what is shared

    Give each thread its own data and combine the results at the end. Each thread counts its own total and they are added up once.

  3. Hold locks for less time

    Do the slow work outside the lock and take it only to publish the result.

  4. Match the thread count to the work

    Around the number of cores for computing. More for waiting. Then measure again.

Key takeaways

  • Threads only speed up the part of a job that can be done in parallel.
  • Amdahl's law: if a fraction is serial, the speed-up can never exceed one divided by that fraction.
  • For pure computation, threads beyond the number of cores do not help.
  • Extra threads add switching and lock contention, so too many make things slower.
  • Work that mostly waits, on a network or disk, benefits from many more threads than cores.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress