Task 5 of 5

Which One Wins?

Two formulations, one answer, and a price that depends on n. Both are wired up below, both report the same thing so the comparison is honest — the score at the boundary — and both run twice: once on 4,096 scores, once on 131,072. Rank-by-counting reads 4,096² ≈ 16.8 million values at the small size and 17.2 billion at the large one. The bisection reads 4,096 values eighteen times (about 74,000) and 131,072 eighteen times (about 2.4 million). Between the two sizes one of those grows 1,024×, the other 32×.

So run it, and watch the winner change. At 4,096 the ranking pass wins, despite doing two hundred times the arithmetic: it is one dense, embarrassingly parallel launch, which is precisely what the hardware is for, while the bisection spends its life waiting for eighteen tiny kernels to come back — latency, not arithmetic. At 131,072 the arithmetic finally outgrows the latency and the order flips. On the machine this was written on (an M1 Max) the small size measures about 1 ms for the ranking against 10 ms for the bisection, and the large one about 48 ms against 15 ms: 32× the data costs the bisection five milliseconds, because eighteen round trips are eighteen round trips whatever they carry, and costs the ranking pass everything. The crossover sits near 65,000, where the two trade places from run to run — and it will not sit there on your hardware, which is the point.

Every kernel gets one untimed warm-up call before the clock starts: a kernel's first launch compiles it, and a shader compiler inside the timer measures nothing you asked about. Even so, one performance.now() sample is a shape, not a benchmark. Read the four lines, then read them again with Mode switched from Auto to CPU — there the ranking pass loses at 4,096 already (about 50 ms against 0.2 ms), and at 131,072 it is not run at all, because a minute of single-threaded counting is the same lesson in a harsher form.

⏱ Benchmark answers a different question, and on this task it answers it badly — which is worth seeing once. It runs the whole file twice, once per backend, and on the CPU backend the file skips the big ranking pass; so it times a smaller job on one side and reports something near 1×. That number means "the CPU backend got out of the work", not "the GPU is not helping" — timing two things that are not the same thing is the oldest way to get a benchmark wrong, and it is exactly what the four lines above go out of their way to avoid.

Goal: write one bisect() driver and one boundaryOf() scan, use them at both sizes, and read off the four timings.

Requirements

One bisect(counter, values, k) serving both the 4,096 and the 131,072 case
It brackets from the data, halves while hi - lo > 0.5, and returns Math.floor(lo)
One boundaryOf(ranks, values) for the ranking side: the score of the element whose rank is K - 1, over flat ranks so the same scan serves the grid
Every measurement the backend can afford runs and logs a time — four on the GPU, three on the CPU, where the 131,072-score ranking pass is reported instead of run (already written)

Hint 1 — one driver, two counters

bisect never mentions a size: it takes the counting kernel as an argument and gets its bracket from the values it was handed. That is why the same four lines serve 4,096 scores and 131,072.

Hint 2 — the boundary from ranks

The K-th largest score is the one whose rank is K - 1. One plain loop over the ranks finds it:

for (let i = 0; i < ranks.length; i++) {
  if (ranks[i] === K - 1) cut = values[i];
}

The big ranking pass hands back a 512 × 256 grid, so the driver flattens it first (utils.flatten) — flat rank i then belongs to values[i] in both cases.

Hint 3 — reading the numbers

The two cutoffs at a size will not be the same number, and they should not be: the ranking pass reports the 10th largest score, the bisection reports the largest whole number strictly below it. Both describe the same boundary — exactly ten scores are above the bisection's cutoff, and the tenth of them is the ranking pass's answer.

Then compare the two times at 4,096 against the two at 131,072. The bisection barely notices the 32× more data; the ranking pass notices it 1,024 times over.

Same idea elsewhere

Picking a formulation by measurement rather than by asymptotics is the whole job. CUB ships several k-selection strategies and dispatches on size; cuDNN and cuBLAS carry multiple kernels per operation and choose at runtime; PyTorch's topk switches between a sorting path and a radix-select path on k and n. The crossovers are found the way you just found this one — by running both on both sides of it, warm, and reading the clock.

All tasks in Top-K Selection

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