# Widen the Radix

*Task 3 of 6 · [Radix Sort](https://gpu.rocks/learn/radix-sort-fd3ff796.md) · GPU.js Learn*

One bit per pass means 32 passes for a 32-bit key. Four bits per pass means
**16 buckets** and eight passes — the same total work rearranged, with far
fewer round trips. That is the real engineering trade in radix sorting, and every library
picks a number here (4 and 8 bits are the usual answers).

The price is that the bucket table stops being a single number. You need a
**histogram** — how many keys carry each of the 16 digits — and then a
running total across the buckets to turn those counts into **starting offsets**:
bucket `b` begins after every key whose digit is smaller than `b`.
Both of those are primitives in their own right (and each has a module of its own); at 16
buckets they are small enough to write out in a loop.

Note the word *smaller*. The scan is **exclusive**: bucket 0 starts
at slot 0, and bucket `b`'s offset stops at `b − 1`. Include your own
count and every bucket starts one whole bucket too far along.

## Figures

- **count, scan, and every key knows its slot without comparing itself to anything (four buckets here, sixteen in the code)**

## Goal

**Goal:** write both kernels — `histogram` counts the keys in
each of the 16 digit buckets at a given `place`, and `offsets` turns
those counts into starting slots with an exclusive scan.

## Requirements

- The digit of a key at `place` is `Math.floor(key / place) % this.constants.radix`
- `histogram`: 16 threads, thread `b` counts the keys whose digit is `b`
- `offsets`: thread `b` totals `counts[0 … b−1]` — exclusive, so `offsets[0]` is `0`

## Hint 1 — extracting a digit

`place` selects which digit you want: `1` for the ones
digit, `16` for the sixteens, `256` for the next. Divide it away,
then take what is left modulo the radix:

```js
const d = Math.floor(keys[i] / place) % this.constants.radix;
```

Skip the `% 16` and `d` is the whole quotient, not a digit.

## Hint 2 — the histogram is a gather, not a scatter

You cannot walk the keys and bump a counter — that is 64 threads fighting over
16 cells. Invert it: each of the 16 threads owns one bucket and walks the whole key
array counting its own digit. `if (d === this.thread.x) count++;`

## Hint 3 — exclusive means stop early

```js
for (let b = 0; b < this.constants.radix; b++) {
  if (b < this.thread.x) start += counts[b];
}
```

Sixteen values is far too few to be worth a clever scan; the point is the
`b < this.thread.x`.

## Same idea elsewhere

Count, scan, scatter is the skeleton of every real GPU radix sort: CUB and
rocPRIM histogram each tile of keys locally, scan the per-tile histograms into global
digit offsets, then move the keys. Choosing the radix is a genuine tuning knob — wider
digits mean fewer passes over memory but a bigger bucket table to keep on chip, which is
why 4 and 8 bits win in practice and 16 does not.

## Starter code

```js
// 16 buckets now, so the bucket table needs counting and scanning.
const gpu = new GPU({ mode });

const histogram = gpu.createKernel(function (keys, place) {
  let count = 0;
  for (let i = 0; i < this.constants.n; i++) {
    // TODO: this key's digit at `place`, then count it if it is MY bucket
    const d = 0;
    if (d === this.thread.x) {
      count++;
    }
  }
  return count;
}, {
  output: [16],
  constants: { n: 64, radix: 16 },
});

const offsets = gpu.createKernel(function (counts) {
  let start = 0;
  for (let b = 0; b < this.constants.radix; b++) {
    // TODO: add the buckets STRICTLY BEFORE this one
    start += 0;
  }
  return start;
}, {
  output: [16],
  constants: { radix: 16 },
});

const onesCounts = await histogram(keys, 1);
console.log('ones-digit counts: ', Array.from(onesCounts).join(' '));
console.log('ones-digit offsets:', Array.from(await offsets(onesCounts)).join(' '));

const sixteensCounts = await histogram(keys, 16);
console.log('16s-digit counts:  ', Array.from(sixteensCounts).join(' '));
console.log('16s-digit offsets: ', Array.from(await offsets(sixteensCounts)).join(' '));
```

---

Interactive version: https://gpu.rocks/learn/radix-sort-fd3ff796/3

[Previous task](https://gpu.rocks/learn/radix-sort-fd3ff796/2.md) · [Next task](https://gpu.rocks/learn/radix-sort-fd3ff796/4.md)