Dzmitry Misiuk (Jul 16 2026 at 08:12): Dzmitry Misiuk (Jul 16 2026 at 08:12):Hi! I'm new here and getting familiar with the new Zig compiler (built it from source on zig 0.16.0). I'd like to pick up a small builtin from #9596 as a first contribution: List.join : List(List(a)) -> List(a) — the one Anton-4 flagged in the issue comment ([[1, 2], [3], [], [4, 5]].join() == [1, 2, 3, 4, 5]).
I've got a draft ready — implemented in pure Roc in Builtin.roc on top of List.fold + List.concat, with ## expect doctests and a repl snapshot under test/snapshots/. Before I open a PR: is that approach OK, would you want capacity reservation for performance, and any preference on snapshot type (expr vs repl)? Thanks!
Dzmitry Misiuk (Jul 16 2026 at 16:20):Quick follow-up before the PR: the naive fold + concat version is actually O(n²) — List.concat reserves exactly len_a + len_b, and calculateCapacity only grows geometrically on +1 appends, so the accumulator gets reallocated and the prefix recopied each step. Going two-pass instead: sum the lengths, List.with_capacity(total), then concat each sublist in — one allocation, O(n).
Dzmitry Misiuk (Jul 16 2026 at 18:59):Opened it as a draft: https://github.com/roc-lang/roc/pull/10179 — went with the two-pass with_capacity version (O(n)). Left it as draft for now; feedback on the snapshot type or anything else very welcome. :folded_hands:
Dzmitry Misiuk (Jul 17 2026 at 08:56):Correction on List.join: my O(n) claim above was wrong, and I've pushed a fix.
List.with_capacity(total) + List.concat in a loop is not O(n). listConcat early-returns when its first argument is empty, and isEmpty() checks length, not capacity — so on the first iteration the reserved buffer is just freed and list_b is returned. After that the accumulator has capacity == length at every step, so each concat reallocates and recopies the prefix. My "optimized" version was exactly as quadratic as the naive fold + concat it was meant to beat — on List.join(List.repeat([1, 2], N)) at N = 50k that's 14.5 s, against 0.24 s for the fixed version.
Fixed by filling the reservation with list_append_unsafe, the same way List.rev / List.map / List.from_iter do. Details and numbers in #10179.
Dzmitry Misiuk (Jul 17 2026 at 11:29):Windows zig-minici on #10179 timed out rather than failed: the job was cancelled at 2h00m34s against its 120-minute limit, with Run MiniCI cancelled mid-step. macOS and Linux both passed, and local zig build minici is 62/62. It took 1h54m on the previous head, so it's been running close to the ceiling.
I can't re-run it from a fork — could someone kick that job whenever it's convenient? :folded_hands:
Dzmitry Misiuk (Jul 17 2026 at 18:14):Update: #10179 is green on all three platforms now and I've marked it ready for review. :folded_hands:
Last updated: Jul 23 2026 at 13:15 UTC