Issue #595: Build ADR-342: a chain over a list runs element by element; an overflow in it may stop it at the end; a filter without a branch

Open and answer this issue on GitHub.

performance, ready · opened 2026-10-12 · updated 2026-10-12 · 0 comments

How it came up

An outside proposal (generated by Gemini) suggested four kinds of “pipeline fusion” so that Nikaia reaches Mojo’s speed:

• fuse map/filter chains into one loop;
• merge filter conditions;
• vectorize the fused loop;
• fuse producer and consumer tasks.

Its premises were partly wrong. It assumed an arena that is built (ADR-327 decides one, but it is not built, see #490), and it claimed that && is “one decision point”. The owner asked what can be taken from it. The goal: Nikaia should compete with Mojo where the plain chain a model writes is as fast as the loop an expert tunes, with every check kept. Mojo gets its speed from written SIMD and vectorize, and does not check overflow.

What was checked (0.0.854)

• Chains over a sequence are one loop already. xs.iter().map(…).filter(…) lowers to Rust’s iterator adapters (ADR-293 D20). LLVM fuses those, so a separate fusion pass would add nothing there.
• A list’s map is eager. xs.map fn(x) { x * 2 }.map fn(y) { y + 1 } lowers to xs.map(|x| …).map(|y| …) on nikaia_std::list::ListExt, which is into_iter().map(f).collect(). That is two passes. Rust reuses the buffer where the element sizes match; elsewhere a new list is built. Under ADR-327 the list between the steps takes room in the task’s block.
• A list has no filter. It is xs.iter().filter. Part III’s paragraph on Seq said xs.map fn … hands back a sequence, which contradicts Part I 5.3 and #517. It now says xs.iter().map fn ….
• a && b stays two branches after inlining, because of the short circuit. One branch needs &, which is only allowed where the second condition cannot panic.
• The overflow checks block vectorization: each one is a branch per element. They are the reason a checked chain is not vectorized, more than where the data lies.
• Fusing tasks would remove concurrency the program wrote. Not done. What a value costs when it moves between tasks is ADR-327 D9 (#490).
• Found on the way: #594. A filter after map over a sequence fails in rustc.

Decision

ADR-342, with the rule in Part I 4.5 and Part III A.2:

• D1: a list’s map whose result goes straight into the next step runs element by element with it, where every lambda touches nothing and changes no name outside it. A chain with I/O or a lock runs as written.
• D2: in such a chain, the order of the lambdas is not fixed, and neither is which panic stops it.
• D3: an overflow may stop the chain after its last element, and still names its own line.
• D4: a filter’s conditions may be joined with &, or the filter may run without a branch.
• D5: what can only be faster is built without a measurement. What can be slower (D3, D4, and D1 in one shape) is measured first, and emitted only for the chain shapes where it is not slower than today.

To build

1. D1, the fusion. In the emitter, a list’s map whose result is not named and goes into another map, iter(), a for or len() is lowered as into_iter().map(f).map(g)…, with one collect where a list is wanted. The condition is the one par_iter lambdas meet (touches empty, no NK2107), without the demand not to pause.
   • Test: xs.map(f).map(g) gives the same output as today.
   • Test: a chain whose first lambda printlns keeps today’s order: all of f, then all of g.
2. D1, the one measurement it owes. A fused loop where one step is vectorized on its own and the other is not, against two passes. Count it with callgrind (instructions and mispredicted branches), output byte for byte the same. Where fusion is slower for that shape, that shape is not fused.
3. D3, measure first. A chain map/sum over i64, three ways:
   • today’s code;
   • overflowing_* with the flags OR-ed and one check after the loop;
   • the same, per run of elements.

   Then the same chain where LLVM does not vectorize. Emit D3 only where it is not slower. A value that overflowed must reach no index, division or condition before the check.

   • Test: an overflow in such a chain stops the task with src/main.nika:N: … attempt to add with overflow, naming the line of the +.
4. D4, measure first. A filter with two cheap conditions, on random data and on sorted data:
   • && (today);
   • &;
   • without a branch (write every element, move the end by the condition).

   Emit each form only where it is not slower.

   • Test: a filter whose second condition can panic keeps &&.
5. Specification: nothing left. Part I 4.5 and Part III A.2 already say it.

Not decided here (ADR-342 §6)

• filter as a method of a list.
• D3 per piece in par_iter.
• Vector types for code that is not a chain.

Back to Open Issues