webasm (and cpu): scatter/predicate kernels run 20–32× slower than the plain JavaScript they were transpiled from

[fuzzie360]

Follows #866. Two workloads compile to WebAssembly successfully and produce correct results, but land far below the plain-JS loop they are a translation of. The cpu backend is equally slow on the same kernels, so this looks upstream of the wasm emitter rather than caused by it.

Apple M1 Max, Chrome 150, branch build of #866 (11b4c0e). Medians, warm.

workload	plain JS	webasm	cpu backend	WebGL2
stream compaction — 2^22 fp32, ~50% kept, ×24 rounds	585 ms	12,501 ms (0.05×)	13,016 ms	410 ms
orientation histogram — 2048×2048 samples → 64 bins	158 ms	5,134 ms (0.03×)	5,949 ms	23 ms

Both are correct — checksums match the plain-JS reference to within 1e-4 relative. It is purely throughput.

For contrast, on the same machine and the same harness, matmul goes the other way: 1400 ms plain JS → 857 ms webasm (1.63×), and 3106 ms on cpu, so webasm is 3.6× the cpu backend there. The emitter is clearly capable. Something about these two shapes costs ~20–30× rather than ~1×.

What the two have in common, and what a dense kernel like matmul does not:

• A predicate and a running offset per cell. Compaction's kernel evaluates a keep/drop test and then indexes by a prefix offset — a data-dependent write position rather than a static one.
• Many-to-one accumulation into a small output. The histogram's 64 bins are each read by a huge number of source samples, so the kernel loops over a large stride per output cell.

Both therefore have a per-cell loop whose trip count depends on data, and both index with computed integers. Guesses at what could produce a 20× factor, offered only as starting points since I have not read the emitter closely: integer index expressions being materialised as f32 and round-tripped per access; the divergent-lane masking described in the PR executing every lane's branch on kernels where the branch is the entire body; or the per-cell loop failing to hoist an invariant the JIT hoists trivially in the plain-JS version.

The cpu backend showing the same slowdown (1.04× and 1.16× of webasm respectively) is the strongest hint — whatever it is, it likely lives in the shared transpilation of these constructs rather than in the wasm-specific path. That also means fixing it would improve the cpu backend at the same time.

Reproduction: both kernels are in the gpu.rocks benchmark suite (src/Bench/workloads/compaction.js, histogram.js), each with a plain-JS oracle in the same file to diff against. Happy to reduce either to a standalone case if that would help.

[fuzzie360]

Measured, and the emitter is exonerated: the factor is the algorithm transposition, not the transpilation.

The control that settles it is hand-written plain JavaScript of the same transposed algorithm the kernels use (per-bin scan for the histogram, binary-lift gather for compaction), sitting between the oracle and the backends. Node 22, M-series, scaled shapes (1024²×64 bins; 2^20 elements, 20 probes):

shape	oracle (scatter)	hand JS, same gather algorithm	gpu.js cpu	webasm SIMD	webasm scalar
histogram partial	1.3 ms	57.8 ms	58.3 ms	84.4 ms	94.5 ms
compaction gather	5.8 ms	57.6 ms	58.8 ms	47.6 ms	52.8 ms

The cpu backend is within 2% of hand-written JS of the identical algorithm on both shapes — the transpiled loop costs nothing. The 20–32× against the oracle is the gather-for-scatter rewrite doing bin-count× (histogram) or log-factor× (compaction, plus cache misses across the 16 MB incl array at full size) more reads, which a GL backend hides under thousands of parallel threads and a serial backend pays in full. The cpu and webasm numbers matching each other (1.04×/1.16× in the original report) was exactly this: both were faithfully executing the same 64–256×-work algorithm.

Each specific guess, against the measurements:

• integer indices materialised as f32 and round-tripped — no measurable cost; webasm's gather beats plain JS on the compaction shape.
• mask predication executing both branch sides — the branchy histogram kernel runs faster on the SIMD path than the scalar wasm path (84 vs 95 ms), so the masks are paying for themselves, not costing 20×.
• invariant hoisting — ruled out by cpu ≡ hand JS.

The one real (second-order) observation: webasm is ~1.5× slower than plain JS on the histogram shape specifically, because codes[thread.x][x] strides by a full row per SIMD lane — a 4-address gather against V8's sequential scalar loads. On the compaction shape the same machinery wins. Not actionable without per-kernel memory-pattern analysis, and orders of magnitude below the headline number.

Resolution on feature/webasm-backend (d21af00): a README note in the webasm section pricing this honestly — a kernel is priced by the work it describes, and when cpu/webasm is a likely destination the direct algorithm beats the GPU-shaped rewrite. For the benchmark suite itself: the fair webasm/cpu column for these two rows would be the scatter-shaped kernel those backends could run directly, but that is a gpu.rocks decision, not a gpu.js one.

[fuzzie360]

Accepted, and the control you built is the right one — a hand-written JS implementation of the same transposed algorithm, sitting between the oracle and the backends, is exactly what my report was missing. cpu landing within 2% of it on both shapes settles the question: the transpiled loop costs nothing, and all three of my guesses were wrong. They were offered as guesses precisely because I had not read the emitter, and it is better to have them refuted by measurement than left standing.

One correction on the closing suggestion, from the gpu.rocks side:

the fair webasm/cpu column for these two rows would be the scatter-shaped kernel those backends could run directly

Those backends can, but gpu.js cannot express it on any of them. The cpu backend emits

this.leadingReturnStatement = this.output.length > 1 ? 'resultX[x] = ' : 'result[x] = ';

— a thread writes only its own output cell, identically on WebGPU, WebGL, WebASM and cpu. Gather-only is a property of the programming model, not of the backend, so there is no scatter-shaped gpu.js kernel for the cpu/webasm columns to run instead. Writing one would mean leaving gpu.js, which would measure something a gpu.js user cannot do.

So those two rows stay as they are. What they price is not "the cpu backend is slow at histograms" but "a gather-only model on a scatter-shaped problem costs bin-count× or a log factor, and a GPU hides that under thousands of threads while a serial backend pays it in full" — which is the thing worth knowing before choosing the model, and both workload headers already argue it at length.

What was wrong was on the page, not in the workloads. gpu.rocks claimed each column runs "the best implementation for its platform", which is true of the two hand-written columns and false of the four gpu.js ones, which share a kernel by construction. On scatter-shaped rows that difference is the entire finding, and the copy now says so explicitly.

Fixed in gpu.rocks rather than here, so nothing is outstanding on gpu.js from my side. The README note pricing this in the webasm section is the right home for it, and the second-order observation about codes[thread.x][x] striding a full row per SIMD lane is a genuinely useful finding that the 20–32× headline was hiding.