Advanced level · Module 5: Concurrency in Modern C++ · Lesson 4 of 4
Parallel Algorithms and Measuring Speed-up
Use the standard parallel execution policies, and measure and explain the speed-up you achieve.
In this lesson you will
- Use execution policies with standard algorithms
- Measure speed-up and explain its limits
Key concepts
std::execution::parspeed-upAmdahl's lawthread overhead
The lesson
Many standard algorithms accept an execution policy: std::sort(std::execution::par, v.begin(), v.end()) may use several threads. Support depends on the standard library (some need an extra threading library), so check your toolchain.
Speed-up is the sequential time divided by the parallel time. It is limited by the part of the work that remains sequential (Amdahl's law), by the overhead of starting tasks and by memory bandwidth.
Small inputs often run slower in parallel. Measure with realistic data and different thread counts, and keep the sequential path for small jobs.
Step by step
- Sort a large vector with and without std::execution::par.
- Measure the speed-up with 1, 2 and 4 threads in your task-based processor.
- Find the input size where parallelism starts to pay off.
- Write a short explanation of the results.
Practice activity
Add a --threads option to the sensor processor and write a speed-up report for three data sizes.
Expected result: A report with measured speed-ups and an explanation of where and why they stop improving.
Check your understanding
-
How is speed-up calculated?
Show answer
Sequential time divided by parallel time.
-
Why can parallel code be slower for small inputs?
Show answer
The overhead of starting and coordinating threads outweighs the work.
Taught live by an instructor — online or in person. Free course lessons are for self-study and do not lead to a certificate — see registration options.