# Which One Wins?

*Task 5 of 5 · [Top-K Selection](https://gpu.rocks/learn/top-k-selection-1ba56df3.md) · GPU.js Learn*

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

**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:

```js
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.

## Starter code

```js
// Same question, two formulations, two sizes. Time them, then ⏱ Benchmark.
const gpu = new GPU({ mode });

const K = 10;

// --- approach A: rank everything (tasks 1-2), at both sizes
const rankSmall = gpu.createKernel(function (values) {
  const mine = values[this.thread.x];
  let ahead = 0;
  for (let j = 0; j < this.constants.n; j++) {
    const other = values[j];
    if (j < this.thread.x) {
      if (other >= mine) ahead++;
    } else if (other > mine) {
      ahead++;
    }
  }
  return ahead;
}, { output: [4096], constants: { n: 4096 } });

// The same pass on 131,072 scores. A launch that wide is a 2D texture
// underneath whatever you call it, so this one says so — a 512 x 256
// grid, ranked by the flat index y * 512 + x, exactly like task 3.
const rankBig = gpu.createKernel(function (values) {
  const me = this.thread.y * this.constants.width + this.thread.x;
  const mine = values[me];
  let ahead = 0;
  for (let j = 0; j < this.constants.n; j++) {
    const other = values[j];
    if (j < me) {
      if (other >= mine) ahead++;
    } else if (other > mine) {
      ahead++;
    }
  }
  return ahead;
}, { output: [512, 256], constants: { n: 131072, width: 512 } });

// --- approach B: bisect for a cutoff (task 4), at both sizes
const countSmall = gpu.createKernel(function (values, t) {
  let hits = 0;
  for (let i = 0; i < this.constants.chunk; i++) {
    if (values[i * this.constants.threads + this.thread.x] > t) hits++;
  }
  return hits;
}, { output: [64], constants: { threads: 64, chunk: 64 } });

const countBig = gpu.createKernel(function (values, t) {
  let hits = 0;
  for (let i = 0; i < this.constants.chunk; i++) {
    if (values[i * this.constants.threads + this.thread.x] > t) hits++;
  }
  return hits;
}, { output: [512], constants: { threads: 512, chunk: 256 } });

function total(partials) {
  let sum = 0;
  for (let i = 0; i < partials.length; i++) sum += partials[i];
  return sum;
}

function bracket(values) {
  let lo = values[0];
  let hi = values[0];
  for (let i = 1; i < values.length; i++) {
    if (values[i] < lo) lo = values[i];
    if (values[i] > hi) hi = values[i];
  }
  return [lo - 1, hi];
}

async function bisect(counter, values, k) {
  // TODO: bracket the values, halve while hi - lo > 0.5 keeping the half
  // that can still contain the cutoff, and return Math.floor(lo). Each
  // counting pass has to be awaited before its answer can be read.
  return 0;
}

function boundaryOf(ranks, values) {
  // TODO: the K-th largest score is the one whose rank is K - 1. Ranks
  // arrive flat, so this same scan serves both sizes.
  return 0;
}

// A kernel's first launch compiles it, and a shader compiler inside the
// timer is not a measurement. One untimed warm-up call each.
await rankSmall(scores);
await bisect(countSmall, scores, K);
// mode carries the gpu.js mode string — 'async' on the default Auto setting,
// 'gpu' only when WebGL is picked by hand. The question here is "is this the
// slow single-threaded backend?", so ask that.
if (mode !== 'cpu') await rankBig(bigScores);
await bisect(countBig, bigScores, K);

let t0 = performance.now();
const smallByRank = boundaryOf(await rankSmall(scores), scores);
const rankSmallMs = performance.now() - t0;

t0 = performance.now();
const smallCut = await bisect(countSmall, scores, K);
const bisectSmallMs = performance.now() - t0;

console.log('rank 4096:', rankSmallMs.toFixed(1), 'ms - 10th largest score is', smallByRank);
console.log('bisect 4096:', bisectSmallMs.toFixed(1), 'ms - cutoff', smallCut);

// 131,072 x 131,072 = 17.2 billion comparisons. The GPU eats them in tens
// of milliseconds; the CPU backend, one thread, would need about a minute,
// so there this measurement is reported rather than run.
if (mode !== 'cpu') {
  t0 = performance.now();
  const bigByRank = boundaryOf(utils.flatten(await rankBig(bigScores)), bigScores);
  const rankBigMs = performance.now() - t0;
  console.log('rank 131072:', rankBigMs.toFixed(1), 'ms - 10th largest score is', bigByRank);
} else {
  console.log('rank 131072: not run on the cpu backend - 17.2 billion comparisons, about a minute');
}

t0 = performance.now();
const bigCut = await bisect(countBig, bigScores, K);
const bisectBigMs = performance.now() - t0;

console.log('bisect 131072:', bisectBigMs.toFixed(1), 'ms - cutoff', bigCut);
```

---

Interactive version: https://gpu.rocks/learn/top-k-selection-1ba56df3/5

[Previous task](https://gpu.rocks/learn/top-k-selection-1ba56df3/4.md)