A tiled matmul in Bend runs about 4x slower than the same kernel handwritten in CUDA: where the time goes

What Bend should do

These are questions more than a request; the measurements are under Why.

Could a balanced tree's leaves be dealt to threads in a fixed order, or could a bang expose the thread's index? (CUDA: the leaves of a balanced fork tree land on threads in an order that changes from run to run, so a layout cannot be coalesced #1780)
Could the tree be grown on more than one group, or could a bang over a known balanced tree skip the grow?
Is there a way to keep a bang's blocks on the device between bangs (no host touches until the result is read)?
Could a spin's array masks be computed once per spin when its arrays are passed unchanged (the common case in a flat loop over one block)?
Would a separate, smaller kernel for leaf-only spins be possible, so a flat loop does not inherit the runtime's 80 registers?

Programs and Nsight reports available on request; I can rerun anything on this GPU.

Why

I wrote a tiled matmul with the one-block pattern of tests/run/stencil3d.bend (Array.fork/Array.join, one block per array, one 4x4 block of C a leaf over 2^14 leaves, A stored transposed so lanes read neighbouring cells), and the same kernel in CUDA (same thread mapping, layouts and data, compiled with NVRTC, --fmad=false as Bend's device build). RTX 4050 Laptop, driver 615.78.08, main 881cb2e (with #1602), idle machine, 5 alternated rounds; the results are the same bits in both:

From K = 1024 to 4096 (512², 4x4): ~0.97 µs a K step in Bend against ~0.27 µs, plus ~0.7 ms a bang, which is why the smaller product does worse. This is where the time goes, with Nsight Systems and Nsight Compute.

A bang's fixed cost (~1.3 ms empty)

Each bang is five bend_dev launches back to back, then the host's turn. Nsight Systems, medians of 19 bangs:

ms	grow, 1 group	grow, 128 groups	main pass	final	host, between bangs
an empty bang over a 2^14-leaf tree	0.55	0.10	0.11	0.007	0.58
the 512² matmul (4x4)	0.32	0.15	5.06	0.009	0.30

(the fifth launch, between the grows and the main pass, takes ~1 µs). The first launch grows the fork tree on one group of 128 lanes, so a balanced 2^14 tree costs up to 0.55 ms before any leaf runs, and the host's turn adds about as much. On 2.0.37 I counted hundreds of CPU page faults a bang in that turn (Bend's heap is managed memory), while the host only reads a result.

The main pass

Nsight Compute on main, application replay (kernel replay restores device memory, and with Bend's managed heap that makes every replay fault its pages back in):

	Bend	handwritten
warp instructions	175.7 M	95.5 M
SASS instructions a K step	83	~45
registers; blocks of 128 per SM	80; 6 (registers)	39-48; 10-12
warps active a cycle	21.6	23.6
sectors a load request	16.45	8.5

The step carries, besides the 8 loads and 32 float operations:

the error poll (YIELD, BSSY/BSYNC, a counter and a branch every step; CUDA: the error poll in every flat loop (err_spun) makes ptxas yield on each iteration; tight loops run up to 20x slower #1776);
~30 address instructions: every Array.get masks its index (i & (2^cls - 1)) and the mask is rebuilt from the block's class bits each step (blk_at reads blk_cls(a) of an array that is a loop variable), so the compiler cannot turn base + i into a pointer plus a fixed offset;
a 64-bit counter for the Nat fuel.

And the whole runtime is one kernel, so the matmul's loop runs with the register count of the largest path in it (80), which caps the resident lanes at 6 blocks per SM.

The largest single part is coalescing: Bend's loads cost 16.45 sectors a request against the twin's 8.5, because the warps do not hold the leaves the layout assumes. Each block of 128 threads runs one aligned range of 128 leaves, but inside the block the leaves are dealt in an order that changes from run to run (#1780). Renumbering the leaves to fit the order I observed (a permutation of the low 7 bits) brings the loads to 9.59 sectors a request, with the same instructions:

512², 4x4, ms a product
as built	4.62-4.72
leaves renumbered	2.82-2.96
renumbered, poll split (#1776's patch)	3.14-3.30
renumbered, poll removed	2.16-2.22
handwritten	1.08-1.23

The last Bend row minus the ~0.7 ms a bang costs (~1.5 ms) is where the handwritten kernel lands once it copies Bend's index mask, poll and occupancy: 1.36-1.47 ms at 6 blocks per SM (2026-10-18, busy CPU; the mask alone +20%). Copying Bend's addressing further (both masks rebuilt every step, a 64-bit counter) costs the twin nothing measurable. Ruled out: the leaf count (4,096 to 16,384 leaves give the same ratio), unrolling (the twin without unrolling is not slower), managed memory (the twin in one managed heap runs as fast) and the data layout (the same in both).

One thing I did not expect: with the leaves renumbered, #1776's split poll is slower than the plain poll (3.14-3.30 against 2.82-2.96 ms), while on the matmul as built it is faster (222-227 against 230-237 ms for 50 products). I have not looked at why.

A PR for the poll, which is one of the per-step costs of the main pass:
#1820

The device's native spin now runs its body in an inner loop of 4096 steps and
reads the error word once, after them, so the poll's branch (the YIELD and the
BSSY/BSYNC around it) leaves the hot path. The poll's period does not change,
so an error is caught after the same number of steps as before.

Measured on an idle RTX 5060 (driver 615.71.09, CUDA 13.4), your flat loop
with five rounds, the three builds alternated, the best of each: main 648 ms,
the PR 332 ms, and 324 ms with the poll removed entirely, so the split is 2.5%
off the floor. A memory-bound loop is not affected
(tests/run/stencil3d.bend takes 175 ms against 172 ms).

This addresses the poll only. The coalescing, which the tables say is the
larger part of the main pass (16.45 sectors a request against the twin's 8.5),
is not addressed here: the leaves still land on the lanes in an order that
changes from run to run (#1780), so the layout cannot be chosen to fit.

Two of your other questions look reachable next, in the order they would pay
off:

the array mask (your fourth question): blk_at rebuilds the index mask
from the block's class bits on every Array.get, and the class bits come
from a handle that the loop threads, so the compiler cannot turn
base + i into a pointer and a fixed offset. A spin's array parameters do
not change while it runs, so the mask can be computed once per spin; the
emitted C would take the mask from the spin's own parameter instead of the
handle.
the leaf-only kernel (your fifth): the runtime is one kernel, so a flat
loop inherits the register count of the largest path in it (80 registers,
six blocks of 128 per SM, against the twin's 39-48 and ten to twelve). A
separate kernel for a bang whose leaves only run flat loops would take the
loop's own count.

If you still have the programs and the Nsight reports for the tiled matmul, I
would like to run the mask change against them: the numbers here are from a
tighter loop than the matmul, and the matmul is where the mask shows.

A native spin polls the error word every 4096 steps, not every step (b…

Some CPU numbers on the mask, since it shows up there too, from a set of ML workloads I'm putting together (each checked bit for bit against a handwritten C version).

On the C backend the mask is already loop-invariant: in the emitted loop clang keeps it in a register and doesn't reload the class bits. What stays is the and on every read, and with it the loads can't use a base plus a fixed offset. A rotating dot product (tensor-array's), unrolled by 2 by clang, keeps an and per read, with a lea or a mov around it, plus movaps copies for the four rotating sums:

import Base

type R is Type:
  R{a: Array<F32>, b: Array<F32>, s: F32}

def dot(k: Nat, +i: U32, a0: F32, a1: F32, a2: F32, a3: F32, ra: Array<F32> & F32, rb: Array<F32> & F32) -> R:
  match k ra rb:
    case 0n Tuple{a, x} Tuple{b, y}: R{a, b, ((a0 + a1 : F32) + (a2 + a3 : F32) : F32)}
    case 1n+p Tuple{a, +x} Tuple{b, +y}: dot(p, (i + 1 : U32), a1, a2, a3, (a0 + (x * y : F32) : F32), Array.get(F32, a, (i + 1 : U32)), Array.get(F32, b, (i + 1 : U32)))

def go(left: Nat, +acc: F32, r: R) -> F32:
  match left r:
    case 0n _: acc
    case 1n+q R{a, b, +s}: go(q, (acc + s : F32), dot(65536n, 0, 0.0, 0.0, 0.0, 0.0, Array.get(F32, a, 0), Array.get(F32, b, 0)))

def fill(left: Nat, +i: U32, +m: U32, a: Array<F32>) -> Array<F32>:
  match left:
    case 0n: a
    case 1n+q: fill(q, (i + 1 : U32), m, Array.set(F32, a, i, ((F32.from_nat(U32.to_nat(((i * m : U32) % 1000 : U32))) / 1000.0 : F32) - 0.5 : F32)))

def show(x: F32) -> IO(Unit):
  match x:
    case F32{w}: IO.print(U32.show(U32{w}))

def main() -> IO(Unit):
  show(go(4096n, 0.0, R{fill(65536n, 0, 7, Array.new(F32, 16n, 0.0)), fill(65536n, 0, 13, Array.new(F32, 16n, 0.0)), 0.0}))

and the same loop in C (same output, 1214833289), both built with -std=c11 -O3:

#include <stdint.h>
#include <stdio.h>
#include <string.h>

static float a[65536], b[65536];

static float dot(int k) {
  float a0 = 0, a1 = 0, a2 = 0, a3 = 0;
  for (int p = 0; p < k; p++) {
    float t = a0 + a[p] * b[p];
    a0 = a1; a1 = a2; a2 = a3; a3 = t;
  }
  return (a0 + a1) + (a2 + a3);
}

int main(void) {
  for (uint32_t i = 0; i < 65536; i++) {
    a[i] = (float)((i * 7u) % 1000u) / 1000.0f - 0.5f;
    b[i] = (float)((i * 13u) % 1000u) / 1000.0f - 0.5f;
  }
  float acc = 0, s = 0;
  for (int q = 0; q < 4096; q++) { acc = acc + s; s = dot(65536); }
  uint32_t w; memcpy(&w, &acc, 4); printf("%u\n", w);
  return 0;
}

Bend 2.0.39, clang 23.1.3, one thread pinned to a P-core (Core Ultra 7 155H), user-mode counts, 3 runs each:

	instructions	cycles
Bend	3,357 M	487-497 M
C	2,014 M	291-295 M

On a bigger loop, SmolLM2-1.7B's feed-forward matrix-vector products at one token (tensor-array's Bands, 24 tokens), the C version takes 3,258 M instructions and ~1.0 G cycles against Bend's 10,635 M and ~2.4 G. Giving the C version the same masks, read from a volatile so clang can't drop them, brings it to 9,902 M and 2.0-2.3 G, so on that loop the mask is most of the distance. Where the reads come in cells of 8 (tensor-array's tiled product), the mask is paid once per cell and the gap is 1.33x.

So on the CPU, computing the mask once per spin wouldn't change much by itself; what would is dropping the and when the index is known to stay below the capacity. Here the loop's k counts down from the array's length, which the type checker could carry as a proof. Is that something the compiler could use, or would it need an explicit unchecked read? Happy to run any change against these.

Thanks, this is useful — I reproduced the loop on my machine (i7-14700HX, clang 22.1.8, Bend 2.0.39, one thread pinned, three runs):

So the mask is the main part of the CPU gap here too. The and-removal was an unsafe edit of the emitted C (the last read wraps), so it is only an upper bound, not a proposed patch.

The short answer to your question: I do not think the compiler can use the loop's k today. Array<T> carries no length or capacity in its type, and blk_at gets the class from the handle at run time. There is no fact connecting the Nat fuel to the array's class, so a proof written in the source would not reach code generation unless we add a primitive that carries it.

The paths I see, in increasing size:

An explicit unchecked read, e.g. Array.get_unchecked, either behind a proof or marked @unsafe like Array.fork. This is the small one and would remove the and exactly where the caller knows the range. It is a language/API decision, and bend2/bend.ts is human-owned, so I would not add it without the maintainers agreeing on the spelling and the safety story.
Range analysis / loop versioning in the compiler: prove i + left <= 2^class once per loop and run an unmasked copy. Bigger, and it needs the type checker or the compiler to know the array's class; it would help code that does not have an explicit proof.
Leave the wrap and and document the cost; then downstream users can choose an explicit unchecked read when they have the bound.

I agree this should not go into #1820: that PR is the device poll only, and mixing a CPU array-access change into it would make both harder to review. If you want to take (1) or (2), I can open a separate PR and run your SmolLM2 programs against it — the tiled product with cells of 8 and the Bands feed-forward are the two shapes where the numbers would say whether it is worth it.

Which would you prefer? I would start with (1) if the maintainers are open to a checked unchecked-read spelling; otherwise (2) is the only path that helps code that does not have a proof.

A native spin polls the error word every 4096 steps, not every step (b…

Thanks for reproducing it. I'd take (1) first, as @unsafe like Array.fork, and only for reads, with one caveat about who can use it. The loops where the mask shows all know their bound. Their originals are in tensor-array, which carries laws and so can't use @unsafe; their parallel copies in tensor-fork and tensor-gpu are outside the proofs already (they share arrays through Array.fork), and those could take the unchecked read today. For tensor-array itself only (2) would help, or a read that takes a proof of the bound once an Array carries its capacity. So (1) is the small step and (2) is the one my proved code is waiting for. I don't think doing (1) first wastes anything: the copies would move from the unchecked read to the checked one when (2) lands.

The spelling and the safety story are the maintainers' call. What my loops need is a read whose index the caller promises is below the block's capacity, so it skips the wrap; the writes can stay as they are.

When you open the PR I'll run it here and post the tables:

on one CPU thread, with perf counters: the dot loop above, SmolLM2-1.7B's feed-forward matrix-vector products at one token (tensor-array's Bands), and tensor-array's tiled product in cells of 8, each against its C version;
on the RTX 4050: the matmul from this issue (512x512x4096, 4x4 and 8x4 a leaf) against its CUDA twin.

Opened #1880 for the first step: Array.get_unchecked, @unsafe like Array.fork, read-only. It skips blk_at's mask on the C lane and reads $0[$1] on JS; the interpreter keeps Array.get's body. bend2/bend.ts is untouched.

The name and the safety contract are proposals for the maintainers to settle; if you want a different spelling, I will change it. The PR also has tests/run/array_get_unchecked.bend and a local dot-loop check (0.19-0.21 s masked against 0.12-0.16 s unchecked here, same output).

Whenever you have the machine, the tables you offered would be the useful next step. It should be a drop-in for the tensor-fork and tensor-gpu copies; tensor-array itself stays on the checked read until the array carries its capacity.

ms a product	Bend	handwritten	ratio
512x512x4096, 4x4 a leaf	4.62-4.72	1.08-1.23	4.3x
512x512x4096, 8x4 a leaf	3.44-3.54	0.78-0.82	4.4x
256x1536x576, 4x4 a leaf	2.10-2.17	0.224-0.226	9.4x

	wall time
Bend, as emitted	0.13-0.14 s
same emitted C, `and` removed from `blk_at` (kept `blk_cls`)	0.07 s
your C twin	0.05-0.06 s

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Repository navigation

A tiled matmul in Bend runs about 4x slower than the same kernel handwritten in CUDA: where the time goes #1781

What Bend should do

Why

A bang's fixed cost (~1.3 ms empty)

The main pass

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Sunbelt Computer Software

PL/B Language Development and Support

A tiled matmul in Bend runs about 4x slower than the same kernel handwritten in CUDA: where the time goes #1781

Description

What Bend should do

Why

A bang's fixed cost (~1.3 ms empty)

The main pass

Activity

adeerkhan commented on Oct 22, 2026

nuxyel commented on Oct 25, 2026

adeerkhan commented on Oct 26, 2026

nuxyel commented on Oct 27, 2026

adeerkhan commented on Oct 27, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions