A parallel for over one atomic counter

Every scanline of a rendered frame can be computed independently, which makes a renderer the textbook example of an embarrassingly parallel workload. It is also the textbook example of how a parallel loop can waste half a machine, because independent does not mean equal: a row that looks at the sky returns immediately, and a row that grazes a surface marches until it runs out of iterations.

This article measures four ways of handing those rows to threads, on the same work, on one machine, and explains which of the differences are properties of the schedule and which are properties of the hardware.

Machine: Intel Core i7-7700HQ, four physical cores, eight logical processors, gcc 13.2 at -O2. Every timing is the minimum of nine runs. Timings are measurements and cannot be recomputed by this site’s audit; every ratio, speedup and prediction derived from them is recomputed on each build.

The workload, and how uneven it isPermalink to “The workload, and how uneven it is”#

The benchmark sphere-traces a wavy ground plane into a 960×540 frame, with the horizon inside the frame so that some rows escape after two steps and others march for hundreds. Rendering it serially and timing each row gives the cost profile:

Nothing about that profile is unusual. Any scene with a horizon, any Mandelbrot-style iteration count, any adaptive quadrature and any sparse matrix with an uneven row pattern has the same shape: cost concentrated in a band, and the band’s position not known until the work is done.

Four schedulesPermalink to “Four schedules”#

/* 1. contiguous blocks: thread i takes rows [i*H/T, (i+1)*H/T) */
static void *worker_block(void *arg)
{
    int id = (int)(intptr_t)arg;
    for (int y = id * H / THREADS; y < (id + 1) * H / THREADS; y++) render_row(y);
    return NULL;
}

/* 2. interleaved: thread i takes rows i, i+T, i+2T, ... */
static void *worker_stride(void *arg)
{
    int id = (int)(intptr_t)arg;
    for (int y = id; y < H; y += THREADS) render_row(y);
    return NULL;
}

/* 3. dynamic: every thread pulls the next row off one shared counter */
static atomic_int next_row;

static void *worker_dynamic(void *arg)
{
    (void)arg;
    for (;;) {
        int i = atomic_fetch_add_explicit(&next_row, chunk_size, memory_order_relaxed);
        if (i >= H) break;
        int end = i + chunk_size < H ? i + chunk_size : H;
        for (int y = i; y < end; y++) render_row(y);
    }
    return NULL;
}

The third is what the demo engine uses, in the Win32 form: InterlockedIncrement on a shared LONG, workers released by a semaphore, and the dispatching thread joining in as worker zero instead of blocking. Fifteen lines, no queue, no task objects, no allocation.

What the profile predictsPermalink to “What the profile predicts”#

Before running anything in parallel, the measured per-row costs already say what each static schedule will do, because a static schedule’s makespan is the largest total any one thread is given:

Thread 4 draws the horizon and holds 1015.6 ms of a 3205.56 ms frame. Every other thread finishes and waits. The predicted speedups are 3.16 for contiguous blocks and 7.90 for interleaving, against a perfect-hardware ceiling of 8.

Interleaving looks like it has solved the problem, and on this profile it has. Hold that thought.

What actually happenedPermalink to “What actually happened”#

Two things in that table need explaining, and both are more interesting than the headline.

Why nothing reaches 8. The machine has eight logical processors on four physical cores. Hyper-threading fills issue slots that a single thread leaves empty; it does not double the execution resources, and this workload — dependent floating-point arithmetic in a tight loop — is exactly the kind that leaves few slots empty. The best result any schedule achieved was 6.27, so that, not 8, is the number the schedules should be judged against. Contiguous blocks reached 47.1 per cent of what the hardware could deliver; the atomic counter reached 98.2 per cent.

Why interleaving ties with the counter. On a smooth profile it should. Interleaving is a static schedule that happens to sample the cost profile uniformly, and when the profile varies slowly with row index, every thread gets a fair share of the expensive band. It costs no atomics at all. If the profile is always smooth, interleaving is the better answer.

The profile where interleaving collapsesPermalink to “The profile where interleaving collapses”#

Give the same renderer a cost pattern whose period is the thread count — every eighth row four times as expensive, which is what happens when a scene has periodic structure, or when rows alternate between two materials, or when a stride matches a cache geometry:

Interleaving is now the worst of the three, and worse than doing nothing clever at all, because thread 0 draws every expensive row and the other seven idle. The counter is unaffected: it never assigns anything in advance, so no pattern in the data can line up with it. On this profile it is 2.15 times faster than interleaving.

That is the whole argument for dynamic scheduling. It is not that it is faster on the average case — here it tied — it is that its worst case is bounded by something that does not depend on the data. Graham’s bound for greedy list scheduling says the makespan is at most $\frac{1}{T}\sum_i c_i + \max_i c_i$: with these numbers, 400.7 ms of perfectly divided work plus one worst row of 25.5928 ms, or 426.29 ms — a guaranteed 7.52 out of 8 whatever order the rows arrive in. No static schedule can promise that without knowing the costs first.

What the atomic costsPermalink to “What the atomic costs”#

The obvious objection to a shared counter is contention, so it is worth measuring rather than arguing about. Twenty million atomic_fetch_add operations on one counter, relaxed ordering, minimum of five runs:

Contention costs about a factor of four, not a factor of a hundred: the cache line holding the counter ping-pongs between cores, and that is all. What matters is how many times it happens. One dispatch of this frame is 540 handouts, so at 20 ns the counter costs 10.8 µs against a 520.51 ms frame — 0.002 per cent. It is free at row granularity.

It would not be free at pixel granularity. The same frame is 518,400 pixels, and 518,400 handouts at 20 ns is 10.37 ms, or 2.0 per cent of the frame, before counting the cache traffic the handouts themselves generate. Granularity is the whole design decision, and a row is the right unit here because it is thousands of times more expensive than the handout that produced it.

Chunk size, and where the tail takes overPermalink to “Chunk size, and where the tail takes over”#

Handing out $k$ rows at a time divides the number of atomics by $k$ and multiplies the worst-case tail by it, because the last chunk cannot be split:

There is no gain anywhere in that table, because there is nothing to gain: the atomic was already 0.002 per cent of the frame. There is a steady loss, and it accelerates once the chunk count approaches the thread count — 540 rows in chunks of 64 is 8.44 chunks for 8 threads, so one thread takes two chunks while seven take one, and the schedule degenerates into the contiguous case it started from.

The rule this suggests is the opposite of the folk advice to “batch to reduce contention”: choose the smallest chunk whose work dominates the handout, and stop. Chunking pays only when the task is small enough that the atomic is a measurable share of it, which is the regime that called for a different decomposition anyway.

Two implementation details that are easy to get wrongPermalink to “Two implementation details that are easy to get wrong”#

The counter’s ordering can be relaxed; the dispatch’s cannot. The handout itself needs only atomicity — memory_order_relaxed is enough, because nothing is being published through the counter, and each index is consumed by exactly one thread. What does need ordering is the boundary: the arguments written before the workers are released must be visible to them, and the results written by the workers must be visible after the join. In the engine those edges are the semaphore release and wait, which carry the necessary ordering themselves; written by hand with atomics they need release on the dispatch and acquire on the completion. Using sequentially consistent ordering everywhere hides the question and costs a fence per handout.

Per-thread state has to be padded. Rows are written to disjoint memory here, so no two threads ever touch the same cache line and false sharing does not arise. The moment a worker accumulates anything — a sample count, a timing, a running maximum — into an array indexed by thread id, eight counters land in one 64-byte line and every increment invalidates the line in the other seven cores. Measured on this machine the penalty for eight packed counters against eight padded ones ranged from 1.3 to 2.0 times across runs, too variable to quote as a single figure, and it grows with core count. The fix costs a char pad[56] and needs no measurement to justify.

The name is wrong, and the distinction mattersPermalink to “The name is wrong, and the distinction matters”#

The engine’s header calls this a work-stealing parallel-for. It is not work stealing. Work stealing gives each thread its own deque and has idle threads steal from the back of another thread’s queue; it is what Cilk, TBB and Rayon implement, and its advantage is that the common case — a thread taking its own work — touches no shared line at all.

What this is, is dynamic self-scheduling from a shared counter, the scheme OpenMP spells schedule(dynamic, 1). For a flat parallel-for over a few hundred items it is the better trade: fifteen lines instead of several hundred, one shared line touched once per item, and no deque to keep coherent. Work stealing earns its complexity when tasks spawn tasks, which a scanline loop never does.

Being precise about which one you have written matters when someone reads the header and expects the load balancing to survive nested parallelism, or expects the shared counter not to be there.

What to take from thisPermalink to “What to take from this”#

• Measure the profile before choosing a schedule. One serial run with a timer around each item tells you what any static split will do, and costs less than the argument about it.
• Prefer a schedule whose worst case is bounded. Interleaving won on the smooth profile and lost badly on the periodic one; the counter was within 2 per cent of the best result on both.
• Judge against what the hardware can deliver, not against the thread count. On four cores with hyper-threading, 6.27 was the ceiling for this workload, and a schedule at 6.16 has almost nothing left to win.
• Keep the shared thing tiny and touch it rarely. One counter, one increment per row, and the work between increments a thousand times larger than the increment.
• Keep the work pure. The row function here reads a scene description and writes its own row, which is what makes any of these schedules interchangeable — the same property that lets a distance-field march be reordered freely, and the same reason summation order has to be pinned down deliberately when the reduction is not a per-row write but a shared accumulator.

The benchmark is a single C file with no dependencies beyond pthreads, and it is the thing to run on your own machine before believing any of these numbers; the renderer it models is the demo engine, where the same fifteen lines drive every frame.