Repository navigation
Fast Array Initialization #1890
Description
What Bend should do
Bend should initialize arrays faster, or enable users to discharge to a proof of initialization before access.
Why
I'm currently modeling a language runtime in Bend, using arrays to model stacks/continuations. Array initialization and resizing (to double size) is currently running about 8 instructions per word, or about 15% of my current benchmark loads.
Array initialization should not be the performance bottleneck.
Activity
raramos9 commentedon Oct 28, 2026
Hello i'd like to take this on. I'll start by investigating the current array initialization implementation and benchmarking the overhead to identify potential optimizations.
raramos9 commentedon Oct 28, 2026
I investigated this on an Apple M1 using the C backend and found a potential optimization opportunity in
blk_new.A standalone
Array.new(U32, 24n, value)is already efficient (~0.27 instructions/cell), but repeatedly doubling an array throughANode{a, Array.new(...)}costs ~5.76 instructions/cell of the final array.Looking at the generated assembly, the inlined
blk_newinitialization loop remains scalar (~5 instructions per U32 cell), while the subsequentblk_fillcopies are vectorized.The relevant code appears to be in
bend2/comp.ts, around lines 4354–4372.I'm planning to investigate whether simplifying the fill loop (particularly the index conversion and modulo operations) allows the compiler to vectorize it in the growth case.
I'll benchmark the change against the current implementation and run the existing correctness tests.
YidaWeng commentedon Oct 29, 2026
Following up on the multi-field case left open in #1928.
I'd like to take the next slice of #1890: reshape
blk_new's fill forlgs >= 1so clang can vectorize growth of multi-word elements (theArray<Pt>/ two-U32-field case from #1928's benches, which stayed ~13–15 instr/cell after the trip-count fix).Plan:
lgs == 1 && n == 2shape (hoist the two words, no per-cell modulo)comp.tsunder the 66k ttok cap (shed first if needed)Array.newinside a bang fills the new block in one loop on one lane (~4.6 ns a cell) #1778) and proof-backed init out of scope for this PR@raramos9 — if you're already working that follow-on, say so and I'll stand down or help on a different slice. Otherwise I'll claim this piece and report back with numbers.
raramos9 commentedon Oct 29, 2026
Thanks for picking this up @YidaWeng ! I saw you already have #1938 in draft so feel free to continue with the follow-up. Happy to help review or benchmark it once it's ready!!