Any read of a loop-carried list makes the next mutation copy the whole list

[niclas-ahden]

If a tail-recursive loop reads a loop-carried list anywhere in its body, even just list.len(), a later list.set/list.append in the same body copies the entire list on every iteration instead of mutating in place.

app [main!] {
    pf: platform "https://github.com/lukewilliamboswell/roc-platform-template-zig/releases/download/0.9/8GdFEvQYS3TeAZxKvTzCLVdQiomweGtXcdZkXNDEeABq.tar.zst",
}
import pf.Stdout

loop : List(U64), U64, U64 -> U64
loop = |table, i, acc|
    if i == 0 {
        acc
    } else {
        len = table.len()
        updated = match table.set(0, i) { Ok(t) => t, Err(_) => [] }
        loop(updated, i - 1, acc + len)
    }

main! = |args| {
    Stdout.line!("sum: ${loop(List.repeat(0, 65536), 100000 + args.len(), 0).to_str()}")
    Ok({})
}

Run: roc main.roc or build the binary and run it.

100,000 iterations over a 65,536-element list: 0.91s on 8f7bb2d, 5.93s on 0d86ed8b (current main). I believe it regressed as of ca0b67d908.

I'm implementing DEFLATE in niclas-ahden/roc-zip and noticed my tests went from 0.9s to 37.3s.