Task 2 of 5

One Thread Per Bin

Run the last task sixteen times over, once per bin, and you have the whole histogram. output: [16] launches sixteen threads; thread x owns bin x, scans the entire array, and counts the codes that belong to it. Nobody writes into anybody else's cell, so there is nothing left to race over. The scatter became a gather — the same move Thinking in Parallel makes, wearing its most useful disguise.

Say the price out loud, because it is real: every one of the 16 threads reads all 4,096 codes, so this histogram costs n × bins reads where the CPU's cost n. You bought correctness with redundant work. On a GPU that is very often the right trade — the redundant reads run in parallel and hit cache, while the serialization an atomic costs does not parallelize at all — but it stops being the right trade as the bin count grows, and task 4 fixes the other end of it.

One check catches almost every histogram bug ever written, so build the habit now: the counts must sum to the number of inputs. Every input belongs to exactly one bin, so 4,096 codes must produce counts totalling 4,096. Anything else means values are being dropped or double-counted, and the size of the gap usually tells you which.

Goal: produce all 16 counts in one kernel launch, then total them in plain JavaScript and log the total.

Requirements

output: [16] — one thread per bin, no loop over the bins
Each thread scans all this.constants.n codes and counts only the ones equal to this.thread.x
Sum the 16 returned counts in ordinary JavaScript and console.log the total (it should come to 4096)

Hint 1 — which bin am I?

this.thread.x is both this thread's output cell and the code it is counting. That coincidence is the entire kernel: thread 5 counts the 5s.

Hint 2 — the loop body

if (codes[i] === this.thread.x) count++;

Hint 3 — the total

A plain loop after the kernel call:

let total = 0;
for (let b = 0; b < counts.length; b++) {
  total += counts[b];
}

If that is not 4096, stop and find out why before you trust a single bar.

Same idea elsewhere

"One thread per output bucket, each scanning the input" is the shape shaders used for histograms for years before compute shaders and atomics existed, and it is still what libraries fall back to when the bin count is small and contention would be brutal. The general lesson outlives the example: when a parallel algorithm wants to write where it cannot, re-derive it so each output owner reads what it needs. CUDA, WGSL and Metal all reward that reformulation even where they would have let you scatter.

All tasks in Histograms & Binning

This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.