0% completed
Why Concurrency Matters
On This Page
Know the Vocabulary
Part 1: A Server That Serves One Fan at a Time
The Checkout Line
The Ticket Job
Two Problems, Two Kinds of Work
Part 2: Two Kinds of Slow Work
I/O-Bound Work
CPU-Bound Work
Telling Them Apart
Part 3: What Concurrency Gains
Gain 1: Overlapping the Waits
Gain 2: Using Every Core
Gain 3: Staying Responsive
What Concurrency Is Not
Part 4: Measuring Both Gains in Code
The Code
What Happens, Step by Step
Part 5: What Limits the Gain
Limit 1: The Number of Cores
Limit 2: The Part That Cannot Be Split
Limit 3: What the Threads Wait For
Limit 4: Python's Global Interpreter Lock
Part 6: What Concurrency Costs
When Threads Pay Off
FAQs
Key Takeaways
Check Your Understanding
Know the Vocabulary
This lesson uses the terms below many times. Read them once now, and come back here when a later section needs one.
- Thread: One path of work inside a program. A program can run many threads at the same time.
- Core: One part of the processor that runs one thread at a time.
- Logical processor: What the operating system counts as one processor. On many machines, each core counts as two logical processors.
- Concurrency: Making progress on several tasks during the same period of time. The tasks may take turns on one core or run on several cores.
- Parallelism: Running several tasks at the very same moment, each on its own core.
- I/O-bound task: A task that spends most of its time waiting for something outside the program, such as a disk. "I/O" means input and output.
- CPU-bound task: A task that spends most of its time computing on a core.
- Throughput: The amount of work a system finishes in a period of time, such as payments per second.
- Response time: The time one fan waits for an answer from the server.
- Speedup: How many times faster a job runs with several threads than with one. A job that drops from 400 ms to 100 ms has a speedup of 4.
- Serial part: The part of a job that must run as one step after another, on one thread.
- Amdahl's law: A rule that gives the largest speedup a job can reach when part of it is serial.
- Global Interpreter Lock (GIL): A lock in the standard Python build that lets only one thread run Python code at a time.
Part 1: A Server That Serves One Fan at a Time
Before the concert ticket site sold its first seat, its server was simple. It had one thread, and that thread handled one request at a time. A request is one message from a fan's browser, such as asking for the seat map. Every other request waited in line until the thread finished the current one.
The engineering team tested the server with one fan, and it felt fast. Then they tried a busy minute.
The Checkout Line
When a fan clicks "Pay," the server sends the card details to the payment provider. A payment provider is an outside company that charges cards for the site. Each call goes over the network and takes about 100 ms to come back.
With one thread, payments happen one after another. Four fans who click "Pay" together wait 100, 200, 300, and 400 ms. A thousand fans would wait up to 100 seconds. The server can finish at most 10 payments per second, no matter how fast its processor is.
Look at what the server does during those 100 ms. It sends a short message and then waits for the answer. The processor has almost nothing to do, yet the next fan cannot start.
The Ticket Job
After a sale, the site builds a PDF ticket for every buyer. A big sale has 2,000 buyers. Building one PDF takes about 40 ms of pure computing, so all 2,000 take about 80 seconds. Then the job writes every PDF into one file for the printing company, which takes 20 more seconds.
Building the PDFs never waits for anything, so it keeps one core busy for 80 seconds. The server machine has 4 cores, and 3 of them sit idle the whole time. The server's only thread is busy with the job too, so for 100 seconds no fan can even load the home page.
Two Problems, Two Kinds of Work
The checkout line is slow because the server waits. The ticket job is slow because it computes on only one core. Concurrency helps with both problems, but in two different ways, and this lesson measures both.
Part 2: Two Kinds of Slow Work
I/O-Bound Work
An I/O-bound task spends most of its time waiting for something outside the program. A payment call is I/O-bound. So are reading from a database, writing to a disk, and sending an email. While a thread waits, it uses no CPU time. Its core is free to run other threads.
CPU-Bound Work
A CPU-bound task spends most of its time computing on a core. Building a PDF is CPU-bound. So are resizing images, compressing files, and sorting long lists. While a thread computes, it keeps its core fully busy. Another thread can use that core only by taking turns with it.
Telling Them Apart
The table below compares the two kinds of work.
| I/O-bound task | CPU-bound task | |
|---|---|---|
| Where the time goes | Waiting for a network, a disk, or a database | Computing on a core |
| What the core does meanwhile | Almost nothing | Works the whole time |
| Ticket site example | Calling the payment provider | Building ticket PDFs |
| What makes it faster | More tasks waiting at the same time | More cores computing at the same time |
| Can threads make it faster on one core? | Yes | No |
Many real tasks mix both kinds, so name a task by the side that takes most of its time. When you are unsure, compare the total time of the task with the processor time it used. If the two are close, the task is CPU-bound. If the processor time is much smaller, the task is I/O-bound.
Part 3: What Concurrency Gains
Concurrency means the server makes progress on several tasks during the same period of time. With threads, each task runs on its own thread. The operating system then shares the cores among the threads. This brings three gains.
Gain 1: Overlapping the Waits
Give each payment its own thread. Thread 1 sends its call and waits. While it waits, Thread 2 sends its call, and so on. Four calls are now waiting at the same time, and all four answers arrive after about 100 ms.
This gain does not need more cores. A waiting thread uses no CPU time, so even one core can keep many waiting threads going. The gain is in throughput: the server finishes more payments per second. Each single payment still takes 100 ms.
Gain 2: Using Every Core
Split the 2,000 PDFs among 4 threads, so that each thread builds 500. With 4 cores, the operating system can run all 4 threads at the very same moment, one on each core. This is parallelism. The 80 seconds of building can drop to about 20 seconds.
This gain needs real cores. On one core, the 4 threads would only take turns. The job would take 80 seconds as before, plus the time spent switching between threads.
Standard Python needs a closer look here, because of its Global Interpreter Lock. The demo in Part 4 tests this gain in Python, and Part 5 explains the result.
Gain 3: Staying Responsive
Run the ticket job on its own thread, and let other threads keep answering fans. The job still takes its time, but the home page loads while it runs. This gain is about response time, the time each fan waits.
What Concurrency Is Not
Concurrency does not make a single task faster. One payment call takes 100 ms with one thread or with a hundred threads. One PDF still takes 40 ms to build. Concurrency only changes how many tasks are in progress at once. A big job such as the ticket job finishes sooner only because its many small tasks run together.
Concurrency is not the same as parallelism. Parallelism means tasks run at the very same moment on different cores. The payment gain is concurrency, and it works on one core, while the PDF gain needs parallelism. The Concurrency, Parallelism, and Multithreading lesson explains this difference.
Concurrency is not free speed either. Every thread adds work of its own, as Part 6 shows.
Part 4: Measuring Both Gains in Code
The Code
The program below runs two jobs, first with 1 thread and then with 4 threads. The payment job makes 4 payment calls. A 100 ms sleep stands in for the wait for the provider. The PDF job builds 400 ticket PDFs. A loop of 20,000 computing steps stands in for drawing each PDF.
With 4 threads, each thread takes every fourth item and counts its work in its own slot of an array. The program prints the number of processors that the machine reports, the work done, and the time. For the PDF job, it also prints a checksum. A checksum is one number made from every result. If two lines show the same checksum, both versions did the same work.
Before you look at the results, predict what 4 threads do in the Python version.
The Python version runs 4 payment calls of 100 ms and then builds 400 ticket PDFs, first with 1 thread and then with 4 threads. Each payment only waits, and each PDF only computes. What do the 4 threads do to the two times?
Here is one real run of the Python version on one test machine:
Processors reported: 16 4 payments of 100 ms, 400 ticket PDFs of 20000 steps Payments, 1 thread : 4 paid, 401 ms Payments, 4 threads: 4 paid, 101 ms PDFs, 1 thread : 400 built, checksum 201151677, 474 ms PDFs, 4 threads : 400 built, checksum 201151677, 495 ms
Here is one real run of the Java version on the same machine:
Processors reported: 16 4 payments of 100 ms, 400 ticket PDFs of 20000 steps Payments, 1 thread : 4 paid, 426 ms Payments, 4 threads: 4 paid, 114 ms PDFs, 1 thread : 400 built, checksum 201151677, 28 ms PDFs, 4 threads : 400 built, checksum 201151677, 7 ms
The payment job behaved the same way in every language. Four threads cut the time from about 400 ms to about 100 ms. Python printed 401 ms and 101 ms in both of its runs. Java, C++, and C# took 426 to 443 ms with 1 thread and 107 to 115 ms with 4 threads. On that test machine, each 100 ms sleep in those three languages lasted about 106 to 111 ms.
The PDF job split the languages into two groups. In Java, 4 threads cut the time from 27 or 28 ms to 6 or 7 ms. That is a speedup of about 4. C++ and C# did the same, going from 23 to 25 ms down to 6 or 7 ms. In Python, 4 threads took 495 ms and 470 ms in two runs. One thread took 474 ms and 472 ms. That is no gain at all.
Notice the checksum. It is 201151677 in every PDF line, in every language. All versions built the same PDFs, so the difference in time comes only from the threads.
Notice also that Python computes far more slowly than the other three. One thread took about 470 ms in Python and about 24 ms in C++. That gap comes from how each language runs code, not from threads. Compare each language only with itself.
Times also move from run to run, more so on a busy machine. Still, in every Python run, the 4 threads were never close to 4 times faster.
Notice the first line too. Every language reported 16 processors, but the test machine has 8 physical cores. Part 5 explains the difference.
What Happens, Step by Step
Follow the payment job, once with one thread and once with four.
Step 1: The first 100 ms. The single thread sends payment 1 and waits for the provider. In the other version, Threads 1 to 4 each send one payment, and all four wait together.
Step 2: The core during the wait. No thread computes while it waits, so the core is almost idle in both versions. Waiting together does not need four cores.
Step 3: After 100 ms. All four answers arrive. Threads 1 to 4 finish, so the four-thread version is done. The single thread has finished only payment 1, and it now sends payment 2.
Step 4: After 400 ms. The single thread finishes payment 4. It did the same work in four times as long.
The diagram below shows the same payments over time.
Part 5: What Limits the Gain
Limit 1: The Number of Cores
A CPU-bound thread keeps a core busy the whole time. The ticket server has 4 cores, so it runs at most 4 such threads at the same moment. Suppose 8 threads all compute on it. Each core takes turns between 2 threads, and the job is no faster than with 4 threads. It can even be a little slower, because each switch between threads costs time.
The core count that a program sees is often not the number of physical cores. Java's Runtime.getRuntime().availableProcessors(), Python's os.cpu_count(), C++'s std::thread::hardware_concurrency(), and C#'s Environment.ProcessorCount all count logical processors. On the test machine, they printed 16 for 8 physical cores. On many processors, one physical core can run two threads at once. The two threads share the parts of that core, so the second one adds much less than a full core.
Limit 2: The Part That Cannot Be Split
Go back to the full ticket job from Part 1. It builds 2,000 PDFs in 80 seconds and then writes them into one file in 20 seconds. The PDFs do not depend on each other, so many threads can build them. The file must be written in seat order by one thread. Those 20 seconds are the serial part, and more cores cannot shorten them.
The table below shows the job on more and more cores.
| Cores | Building PDFs | Writing the file | Total | Speedup |
|---|---|---|---|---|
| 1 | 80 s | 20 s | 100 s | 1 |
| 2 | 40 s | 20 s | 60 s | 1.7 |
| 4 | 20 s | 20 s | 40 s | 2.5 |
| 8 | 10 s | 20 s | 30 s | 3.3 |
| Unlimited | almost 0 s | 20 s | 20 s | 5 |
Notice that 8 cores give a speedup of 3.3, not 8. Notice also the last row. Even with unlimited cores, the job never takes less than 20 seconds, so its speedup can never pass 5.
This is Amdahl's law, named after the computer designer Gene Amdahl. It says that the serial part of a job limits its speedup. If a share S of the job is serial, the speedup on N cores is:
speedup = 1 / (S + (1 - S) / N) largest possible speedup = 1 / S
For the ticket job, S is 0.2, because 20 of the 100 seconds are serial. On the server's 4 cores, the speedup is 1 / (0.2 + 0.8 / 4) = 2.5, as in the table. The largest possible speedup is 1 / 0.2 = 5.
The diagram below shows the same job on 1, 2, 4, and 8 cores.
Amdahl's law holds even when the serial part is small. A job that is only 5 percent serial can never run more than 20 times faster. So before you add threads, look for the serial part, and try to make it smaller.
Limit 3: What the Threads Wait For
Overlapping the waits helps only if the other side can answer many calls at once. The payment provider accepts at most 4 calls from the site at the same time, and it declines the rest. With 40 threads, 36 of the calls would fail. That is one reason the demo makes only 4 payment calls. The Semaphore lesson shows how to respect a limit like that. A database with a fixed number of connections sets the same kind of limit.
Limit 4: Python's Global Interpreter Lock
In the standard Python build, the GIL lets only one thread run Python code at a time. A thread gives up the lock while it waits, for example during a sleep or a network call. That is why the Python payment job gained as much as the others. A thread that computes needs the lock the whole time. The computing threads pass the lock between them, about every 5 ms by default, so only one of them computes at any moment. That is why the Python PDF job gained nothing.
For CPU-bound work in Python, use processes instead of threads. Each process has its own interpreter and its own GIL, so several processes can compute on several cores at once. The multiprocessing module and ProcessPoolExecutor do this. Some libraries written in C also release the lock while they compute.
Part 6: What Concurrency Costs
Each thread has a price, so add threads only where the gain is larger than the cost.
- Time to create threads. The operating system must set up each new thread and clean it up when it ends. For many short tasks, this can take longer than the tasks themselves. The Thread Pools and Executors lesson measures this cost and shows how to reuse threads.
- Memory. Each thread has its own stack, which is the memory for its function calls. On many systems, each stack reserves about 1 MB of memory space.
- Switching. When more threads are ready to run than there are cores, the operating system keeps switching each core between threads. Each switch costs a few microseconds of work that does nothing useful. The Thread Life Cycle and Scheduling lesson explains how switching works.
- Coordination. Threads that share data must take turns with it, using tools such as locks. While one thread holds a lock, the others wait, and that waiting eats into the gain.
- New kinds of bugs. Two threads can change the same data at the same time and leave it wrong. This bug is a race condition. Threads can also wait for each other forever, which is a deadlock. Both bugs appear only with certain timings, so tests often miss them, and the order of events changes from run to run. The Race Conditions and Critical Sections lesson starts with the first one.
When Threads Pay Off
Threads help when:
- Tasks wait for something outside the program, such as a payment provider, a database, or a disk.
- A big CPU-bound job splits into independent pieces, and the machine has free cores.
- A long job must not stop the program from answering users.
More threads do not help when:
- The work is short, and starting threads would cost more than the work.
- The job is mostly serial, so Amdahl's law leaves little to gain.
- The threads wait for a limited thing that is already full. A provider that accepts only 4 calls at once gains nothing from a fifth caller.
- The work is CPU-bound Python code in the standard build. Use processes there.
FAQs
Q: Does concurrency make one fan's payment faster?
No. Each payment still takes about 100 ms. Concurrency lets many payments wait at the same time. The server finishes more payments per second, and fans near the back of the line wait much less.
Q: Does a machine with 16 logical processors run 16 computing threads 16 times faster?
No. The test machine reports 16 logical processors but has only 8 physical cores. Two threads that share a core run less than twice as fast as one, and the serial part lowers the gain even more.
Q: Is multithreading the only way to get concurrency?
No. A program can also use several processes. It can also use one thread with an event loop, which switches between tasks while they wait. The Concurrency, Parallelism, and Multithreading lesson compares these ways. This course focuses on threads.
Q: Given the GIL, are threads useful in Python at all?
Yes, for I/O-bound work. A Python thread gives up the GIL while it waits. So the payment demo gained as much in Python as in the other languages.
Key Takeaways
- Concurrency helps two kinds of slow work in different ways. I/O-bound tasks gain by waiting together. CPU-bound tasks gain by computing on several cores at once.
- Waiting together needs no extra cores. In the demo, 4 threads cut 4 payments from about 400 ms to about 100 ms in every language.
- Computing together needs real cores. Java, C++, and C# built 400 PDFs about 4 times faster with 4 threads. Standard Python gained nothing, because of its GIL.
- Concurrency does not make one task faster. It raises throughput and keeps the server responsive, while each payment still takes 100 ms.
- The serial part sets a hard limit. The ticket job is 20 percent serial. It can never run more than 5 times faster, however many cores it gets.
- Count cores with care. The usual core-count calls return logical processors, such as 16 on a machine with 8 physical cores.
- Threads cost time, memory, switching, coordination, and new kinds of bugs. Add them only where the gain is larger.
- In a coding interview, say whether the work is I/O-bound or CPU-bound before you choose a number of threads. Then name what limits the gain: the cores, the serial part, or the thing the threads wait for.
Both gains in this lesson came from threads, and the costs came from them too. The next lesson, Programs, Processes, and Threads, shows what a thread is and what the threads of one process share.
Check Your Understanding
1. A request waits 95 ms for a database and computes for 5 ms. Is it I/O-bound or CPU-bound, and can threads help on a machine with one core?
<details> <summary>Show answer</summary>It is I/O-bound, and threads can help. While one thread waits for the database, the core is free for other threads. Many requests can wait together, even on one core.
</details>2. A job is 25 percent serial. What is the largest speedup it can reach with any number of cores?
<details> <summary>Show answer</summary>A speedup of 4. Amdahl's law gives 1 / 0.25 = 4. Even with unlimited cores, the serial quarter still takes its full time.
</details>3. A Java job computes the whole time on a machine that reports 8 logical processors. A developer raises the threads from 8 to 64. What happens to the time?
<details> <summary>Show answer</summary>It stays about the same or gets a little worse. At most 8 threads can run at the same moment, so the other threads only take turns. The extra switching costs time and does no useful work.
</details>4. A Python program splits a CPU-bound job across 4 threads, and it runs no faster. Why, and what should it use instead?
<details> <summary>Show answer</summary>The GIL lets only one thread run Python code at a time. A computing thread keeps the lock, so the threads only take turns. Separate processes, for example with ProcessPoolExecutor, can compute on several cores at once.
Flashcards Review
What is an I/O-bound task?
Reading Progress
0%
On This Page
Know the Vocabulary
Part 1: A Server That Serves One Fan at a Time
The Checkout Line
The Ticket Job
Two Problems, Two Kinds of Work
Part 2: Two Kinds of Slow Work
I/O-Bound Work
CPU-Bound Work
Telling Them Apart
Part 3: What Concurrency Gains
Gain 1: Overlapping the Waits
Gain 2: Using Every Core
Gain 3: Staying Responsive
What Concurrency Is Not
Part 4: Measuring Both Gains in Code
The Code
What Happens, Step by Step
Part 5: What Limits the Gain
Limit 1: The Number of Cores
Limit 2: The Part That Cannot Be Split
Limit 3: What the Threads Wait For
Limit 4: Python's Global Interpreter Lock
Part 6: What Concurrency Costs
When Threads Pay Off
FAQs
Key Takeaways
Check Your Understanding