# Where Do I Land?

*Task 2 of 5 · [Stream Compaction](https://gpu.rocks/learn/stream-compaction-0aed2e43.md) · GPU.js Learn*

A survivor's output slot has a very short definition: **how many survivors
are in front of me**. Element 9 with four survivors before it lands at index 4.
That number, for every element at once, is the **exclusive prefix sum** — a
*scan* — of the flags: cell `i` holds the total of flags
`0 … i−1`, *not counting its own*.

Scan is a whole subject of its own, and the Prefix Sums module derives the log-time
ladder version properly. Sixty-four elements do not need it: every thread can simply walk
the flags and count. That is `n` reads per thread — blunt, but perfectly
parallel, and right now what matters is what the number *means*, not how fast you
can get it.

Exclusive, not inclusive. Count yourself and every survivor lands one slot too far,
with the first one shoved off the front of the array.

## Figures

- **flags say who survives; the scan under them says where each one lands**

## Goal

**Goal:** for every index, return how many of the flags
*strictly before* it are `1`.

## Requirements

- Loop the full fixed range — `for (let i = 0; i < this.constants.n; i++)`
- Add `flags[i]` only when `i` is strictly less than `this.thread.x`
- Cell `0` is always `0`, whatever `flags[0]` says

## Hint 1 — "strictly before"

The loop already visits every flag; it just needs to ignore the ones that are
not in front of this thread. Guard the accumulation with
`if (i < this.thread.x)` — note `<`, not
`<=`.

## Hint 2 — the loop body

```js
if (i < this.thread.x) {
  seen += flags[i];
}
```

## Hint 3 — check it by hand

For flags `[1, 0, 1, 1]` the destinations are
`[0, 1, 1, 2]`: the survivor at index 0 goes to slot 0, the one at index 2
goes to slot 1, the one at index 3 goes to slot 2. Index 1 gets a number too — it just
never uses it, because it does not survive.

## Same idea elsewhere

Exclusive scan is one of the two or three primitives every GPU library is built
on: `thrust::exclusive_scan`, CUB's `DeviceScan::ExclusiveSum`,
rocPRIM's equivalent, and `subgroupExclusiveAdd` burned into WGSL and hardware.
Blelloch's 1990 formulation gets it in O(n) work and O(log n) depth — the loop here is the
honest, slow version of the same answer.

## Starter code

```js
// The scan: every thread counts the survivors in front of it.
const gpu = new GPU({ mode });

const destination = gpu.createKernel(function (flags) {
  let seen = 0;
  for (let i = 0; i < this.constants.n; i++) {
    // TODO: count only the flags STRICTLY BEFORE this thread's index.
    seen += flags[i];
  }
  return seen;
}, {
  output: [64],
  constants: { n: 64 },
});

const offsets = await destination(flags);
console.log('flags:   ', Array.from(flags).slice(0, 12).join(', '));
console.log('offsets: ', Array.from(offsets).slice(0, 12).join(', '));
```

---

Interactive version: https://gpu.rocks/learn/stream-compaction-0aed2e43/2

[Previous task](https://gpu.rocks/learn/stream-compaction-0aed2e43/1.md) · [Next task](https://gpu.rocks/learn/stream-compaction-0aed2e43/3.md)