Performance, Scalability and Queueing Theory

A supermarket with two tills works fine until shoppers arrive faster than the tills can serve them — then the queue grows without limit, however small the overload.

Learning Objectives

Measure throughput and latency, including average, median, p95, p99 and tail latency; separate service time from waiting time.

Apply Little's Law; understand queue length and saturation; use backpressure, load shedding and concurrency limits.

Predict parallel speedup (Amdahl, Gustafson); choose workload decomposition and granularity; account for scheduling, context-switch, contention, false-sharing, memory-bandwidth, cache-locality, NUMA and oversubscription costs.

Size thread pools; compare blocking and async I/O; account for async overhead; batch and vectorise; understand fan-out tail amplification and warm-up.

Design benchmarks and load tests, avoid coordinated omission, profile before optimising, and plan capacity with safety margins.

Plain-Language Explanation

A supermarket with two tills works fine until shoppers arrive faster than the tills can serve them — then the queue grows without limit, however small the overload. Waiting time explodes long before the tills are "100% busy": at 90% utilisation, customers wait far longer than at 50%. Concurrency performance is mostly about queues: where they form, how long they get, and what happens at the edges (the slowest 1% of customers).

Precise Technical Explanation

Throughput and latency Throughput: completed operations per second. Latency: time per operation, from the user's point of view (including queueing).

Average, median, p95, p99 and tail latency Averages hide tails: a service with 99 requests at 10 ms and one at 2 s has a mean of 30 ms but a p99 of 2 s. Report percentiles from histograms (HdrHistogram), not averages of averages.

Service time and waiting time Response time = waiting time (in queues) + service time (doing the work). Optimising code reduces service time; reducing load or adding capacity reduces waiting time.

L = average number of items in the system, λ = average arrival (= throughput) rate over a stable interval, W = average time in the system. It holds for any stable system regardless of distributions — but only on average and only when the system is stable (arrivals ≈ departures over the window). It does not apply to an overloaded system whose queue keeps growing. Verified by simulation below.

Queue length and saturation For an M/M/1 queue (random arrivals, random service, one server) with utilisation ρ = λ/μ, mean time in system W = 1/(μ − λ) — it grows as 1/(1 − ρ): ×2 at 50%, ×10 at 90%, ×100 at 99%. Real systems behave similarly: latency rises sharply well before 100% utilisation.

Backpressure and load shedding When demand exceeds capacity, either slow the sources (backpressure) or reject some work early (shed load — HTTP 503, dropping low-priority work) so admitted work still meets its latency targets.

Cap in-flight work (semaphores, pool sizes, adaptive limits such as Netflix's concurrency-limits using Little's Law and latency gradients) at the point where throughput stops increasing.

S(N) = T(1) / T(N); efficiency = S(N)/N.

Module 16: S ≤ 1 / (s + (1 − s)/N).

Gustafson's law Module 16: scaled speedup N − s(N − 1).

Split by data (partitions), by task (pipeline stages), or by request (independent requests) — whichever minimises communication and imbalance.

Granularity and overhead Too fine: scheduling/synchronization overhead dominates. Too coarse: poor load balance and idle cores.

Scheduling and context-switch cost A context switch costs ~1–5 µs directly on bare metal plus cache/TLB refill; a hand-off through a mutex/condition variable needs a sleep and a kernel wake-up — measured below at tens of microseconds per round trip inside the build machine's WSL2 virtual machine (virtualisation makes wake-ups more expensive).

Serialises threads; throughput may *drop* as threads are added (Module 4).

Memory bandwidth limits Streaming workloads saturate memory bandwidth with a few cores; more threads do not help.

Partition data so each thread works on its own contiguous region.

On multi-socket machines, keep threads near their memory (Memory course, Module 19).

Many more runnable threads than cores: time slicing, context switches and cache pollution with no extra throughput for CPU-bound work (measured below).

Thread pool sizing Module 15: ≈ cores for CPU-bound; cores × (1 + wait/compute) for blocking; validate with measurements and Little's Law (threads in use = throughput × time per request).

Blocking I/O versus async I/O Blocking: a thread per in-flight operation. Async: few threads, many in-flight operations. Async wins on memory and context switches at high concurrency; blocking (especially with virtual threads) wins on simplicity.

Async overhead and allocation Every await that suspends allocates/schedules; for fine-grained in-memory work, async can be slower than synchronous code (measured below).

Batching and vectorization Amortise fixed costs per operation (system calls, round-trips, locks) and use SIMD for data-parallel loops.

Tail amplification in fan-out requests Module 20: waiting for N backends makes the slowest backend set the latency.

Warm-up and steady-state behavior JIT compilation, caches, connection pools and page faults make the first iterations slower; benchmark steady state separately from cold start (Java example below).

Fixed environment, warm-up, many repetitions, realistic data, measure the right thing (latency distribution, throughput at a target latency), compare against a baseline, report variance; use harnesses (JMH, BenchmarkDotNet, pytest-benchmark, Criterion, Go's testing.B).

Drive a system at controlled arrival rates (open model) to find the throughput at which latency targets break (wrk2, k6, Gatling, Vegeta).

A closed-loop load generator waits for each response before sending the next request; when the server stalls, the generator stops sending, so the stall affects only one measured request — hiding the latency that real users (who keep arriving) would see. Measure with intended send times (open loop) or correct for it (demonstrated below).

Profiling before optimization Find where time goes (CPU profilers, off-CPU/lock profilers, async profilers) before changing code; optimise the bottleneck, then measure again.

Capacity planning and safety margins Plan for peak load with headroom (e.g. run below 60–70% utilisation) because latency explodes near saturation and failures shift load onto survivors.

L = λ × W

Why It Matters in Real Systems

Most outages are capacity problems in disguise: a retry storm, a slow dependency or a traffic spike pushes a queue past saturation. Queueing intuition prevents both over-provisioning and collapse.

Key Terms

Fraction of time a server is busy (λ/μ) L = λW for stable systems

Latency under which 99% of requests complete Rejecting excess work early More runnable threads than cores Load generator hiding stalls by waiting Period before steady-state performance

Syntax and API Overview

This is a concurrency concept, not a language construct.

Little's Law:      L = λ × W          (stable system, long-run averages)
M/M/1:             ρ = λ/μ,  W = 1/(μ − λ),  L = ρ/(1 − ρ)
Amdahl:            S(N) = 1 / (s + (1 − s)/N)
Pool sizing:       N_threads ≈ N_cores × U × (1 + wait/compute)

Complete Code Example

A discrete-event simulation of a single-server queue verifying Little's Law and showing latency versus utilisation, plus a coordinated-omission comparison (CPython 3.13.1, seeded — a *model*, not a measurement of any real system):

Measured costs on the build machine — thread wake-up round trips and CPU oversubscription (G++ 11.2 -O2; one real run):

JIT warm-up: the same method timed on its first and later invocations (Temurin JDK 21; one real run):

import heapq
import random


def simulate(arrival_rate, service_rate, n=200_000, seed=1):
    rng = random.Random(seed)
    t, server_free_at = 0.0, 0.0
    waits, systems = [], []
    area, last_event, in_system = 0.0, 0.0, 0
    departures = []
    for _ in range(n):
        t += rng.expovariate(arrival_rate)                    # next arrival
        while departures and departures[0] <= t:              # account departures before this arrival
            d = heapq.heappop(departures)
            area += in_system * (d - last_event); last_event = d; in_system -= 1
        area += in_system * (t - last_event); last_event = t; in_system += 1
        start = max(t, server_free_at)
        service = rng.expovariate(service_rate)
        server_free_at = start + service
        heapq.heappush(departures, server_free_at)
        waits.append(start - t)
        systems.append(server_free_at - t)
    duration = last_event
    L = area / duration                                       # time-average number in system
    lam = n / t
    W = sum(systems) / n
    systems.sort()
    pct = lambda p: systems[int(p * n) - 1] * 1000
    return L, lam, W, pct(0.5), pct(0.99)


print("service rate 1
…

service rate 100/s (10 ms per request), one server
utilisation |  mean W (ms) | M/M/1 1/(mu-lambda) | p50 (ms) | p99 (ms) | L   vs lambda*W
    50%     |        20.0  |                20.0 |     13.9 |     91.8 | 1.00 vs 1.00
    80%     |        49.7  |                50.0 |     34.1 |    235.9 | 3.97 vs 3.97
    90%     |        98.6  |               100.0 |     67.8 |    485.7 | 8.86 vs 8.86
    95%     |       220.4  |               200.0 |    135.7 |   1193.8 | 20.89 vs 20.89
coordinated omission: closed-loop p99 = 1.0 ms (802 samples); open-loop p99 = 1901.0 ms (1000 samples)

#include <chrono>
#include <condition_variable>
#include <iostream>
#include <mutex>
#include <thread>
#include <vector>

using clk = std::chrono::steady_clock;

int main() {
    // ping-pong: each round trip forces two thread hand-offs through a mutex + condition variable
    std::mutex m;
    std::condition_variable cv;
    int turn = 0;
    constexpr int rounds = 50'000;
    auto t0 = clk::now();
    std::thread other([&] {
        for (int i = 0; i < rounds; ++i) {
            std::unique_lock l(m);
            cv.wait(l, [&] { return turn == 1; });
            turn = 0;
            cv.notify_one();
        }
    });
    for (int i = 0; i < rounds; ++i) {
        std::unique_lock l(m);
        turn = 1;
        cv.notify_one();
        cv.wait(l, [&] { return turn == 0; });
    }
    other.join();
    double us = std::chrono::duration<double, std::micro>(clk::now() - t0).count() / rounds;
    std::cout << "condition-variable ping-pong: ~" << int(us * 10) / 10.0 << " us per round trip (two wake-ups)\n";

    // oversubscription: the same CPU work split over 8 vs 256 threads on 8 hardware threads
    constexpr long total = 400'000'000;
    for (int threads : {8, 256}) {
        a
…

condition-variable ping-pong: ~59 us per round trip (two wake-ups)
8 threads: 52 ms (checksum 1400000000)
256 threads: 70 ms (checksum 1400000000)

public class Warmup {
    static long work(int n) {
        long s = 0;
        for (int i = 0; i < n; i++) s += (i * 31L) ^ (s >>> 3);
        return s;
    }

    public static void main(String[] args) {
        long sink = 0;
        for (int round = 1; round <= 6; round++) {
            long t0 = System.nanoTime();
            for (int k = 0; k < 200; k++) sink += work(20_000);
            long us = (System.nanoTime() - t0) / 1000;
            System.out.printf("round %d: %6d us%n", round, us);
        }
        System.out.println("(sink " + (sink != 0) + ") early rounds run in the interpreter / C1; later rounds use C2-compiled code");
    }
}

round 1:  11665 us
round 2:   3520 us
round 3:   3535 us
round 4:   3347 us
round 5:   3462 us
round 6:   3320 us
(sink true) early rounds run in the interpreter / C1; later rounds use C2-compiled code

Line-by-Line Explanation

Queueing: exponential inter-arrival and service times model an M/M/1 queue; the simulation tracks the time-average number in the system (L), the arrival rate (λ) and mean time in system (W). L and λW agree (Little's Law), the mean W matches 1/(μ − λ), and p99 grows much faster than the median as utilisation rises.

Coordinated omission: the closed-loop generator sends nothing during the stall, so only one sample sees it; the open-loop generator keeps "arriving" every 10 ms, so ~200 requests (2% of samples) experience the stall — the true p99.

Ping-pong: each round trip includes two condition-variable wake-ups (sleep, kernel futex wake, schedule).

Oversubscription: 256 threads do the same total work as 8 but add context switches and cache disruption (the checksums match, proving equal work).

Warm-up: the first round includes interpretation and JIT compilation.

Output

Shown above: the queueing table and coordinated-omission comparison are deterministic simulations; the C++ and Java timings are one real run on the build machine.

Interleaving or State Trace

Queue at ρ = 0.9: arrivals at 90/s, service at 100/s — the server is idle only 10% of the time; bursts of arrivals build queues that drain slowly because spare capacity is small, hence long waits.

Correctness and Safety Analysis

Performance changes must preserve correctness: verify results (checksums above), keep the same semantics when batching or parallelising, and watch for floating-point reduction-order differences (Module 16).

Common Mistakes and Misconceptions

Reporting averages instead of percentiles.

Running near 100% utilisation "for efficiency".

Closed-loop load tests that hide stalls (coordinated omission).

Benchmarking cold JIT code or debug builds.

More threads for CPU-bound work beyond core count.

Applying Little's Law to an unstable, growing queue.

Failure Modes and Debugging Steps

Latency rises with load → find the saturated resource (CPU, pool, lock, I/O) via utilisation and queue-length metrics; throughput falls when adding threads → contention or oversubscription; p99 spikes → GC pauses, lock convoys, stalls, fan-out tails.

Performance and Scalability Implications

This whole module: utilisation drives queueing delay; concurrency limits and load shedding keep latency bounded; granularity and contention decide parallel efficiency.

Security Considerations

Systems near saturation are easy to push over (DoS); capacity headroom, admission control and per-client limits are security controls as much as performance ones.

Platform and Runtime Caveats

Simulated results assume M/M/1 statistics; real service-time distributions are often heavier-tailed (worse tails). Measured timings depend on CPU, OS, power management and background load.

Real-World Applications

SLO-driven capacity planning, autoscaling policies (target utilisation), load testers (wrk2's coordinated-omission correction), adaptive concurrency limits in proxies (Envoy), JVM warm-up strategies (CDS, JIT caches).

Best Practices

Measure percentiles with histograms; track utilisation and queue lengths.

Keep utilisation of critical resources well below saturation.

Limit concurrency and shed load explicitly.

Benchmark steady state and cold start separately; avoid coordinated omission.

Profile first; verify results after optimising.

Exercises

E1 · Beginner. A service handles 200 requests/s with an average latency of 50 ms. How many requests are in flight on average?

Answer: L = λW = 200 × 0.05 = 10.

E2 · Intermediate. Using M/M/1, how does mean time in system change when utilisation goes from 80% to 95% for a 10 ms service time?

Answer: W = S/(1 − ρ): 10/0.2 = 50 ms → 10/0.05 = 200 ms — four times longer for 19% more load.

E3 · Advanced challenge. Explain how to fix coordinated omission in a closed-loop benchmark without changing it to open-loop.

Answer: Record each request's *intended* start time on a fixed schedule; when a response arrives late, compute latency from the intended time, and add synthetic samples for the requests that would have been sent during the stall (HdrHistogram's recordValueWithExpectedInterval).

Quiz

? When does Little's Law apply?
+ To long-run averages of a stable system :: Arrivals and departures balance.
- Only to M/M/1 queues :: It is distribution-independent.
- To a queue that grows without bound :: Not stable.
- To single requests :: It concerns averages.

? Why does the closed-loop load generator understate p99 during a stall?
+ It stops sending while waiting, so only one request observes the stall. :: Coordinated omission.
- It sends too many requests. :: It sends too few during the stall.
- Its clock is wrong. :: The sampling is the issue.
- p99 cannot be measured in closed loop. :: It can, but biased.

? Which typically increase latency sharply? (select all that apply)
+ Raising utilisation from 80% to 95% :: Queueing delay ~ 1/(1-ρ).
+ Fan-out to many backends without hedging :: Tail amplification.
- Batching requests to reduce per-request overhead at moderate load :: Usually improves throughput.
+ Oversubscribing CPU-bound threads :: Context switches, cache churn.

Summary

Latency = waiting + service; waiting explodes as utilisation approaches 1. Little's Law ties concurrency, throughput and latency for stable systems. Measure percentiles, not averages; keep headroom; limit concurrency and shed load; mind granularity, contention, oversubscription, async overhead and warm-up; benchmark carefully and avoid coordinated omission.