Stream: contributing

Topic: List.keep_if allocates once per kept item instead of working

pixelsprout (Oct 26 2026 at 19:16):

On current main (and nightly-2026-10-21), keep_if, drop_if, keep_oks and keep_errs are a fold over concat:

keep_if = |list, predicate|
        List.fold(list, [], |acc, item| if predicate(item) { List.concat(acc, [item]) } else { acc })

Each kept item allocates a one-item list, and acc grows by reallocating. Keeping all 12 items of a 12-item list costs 13 allocations and 4 reallocs, even when the input list is unique. The doc comment says a unique list is filtered in place with no allocation, and that a fully kept list comes back unchanged. The code doesn't do either. As far as I can tell, keep_if dates from #8501 and never got the reuse work that List.map got in #9610 and #10594.

I hit this when building examples in the Rocco game engine, where view filters entities every frame. In that frame it accounted for 12 allocations and all 4 reallocs.

Proposed fix (I have a local branch with tests):

• Unique list: after list_map_prepare_reuse and list_owned_unique, the same order sort_impl uses, swap each kept item down with list_swap_unsafe, then List.drop_last the rest. Order is kept, dropped items are freed once, capacity is unchanged, and an all-kept list comes back as it was. No allocation.
• Shared list: if every item is kept, return the list as it is. Otherwise copy the kept items into one List.with_capacity(len) buffer, allocated only when the first kept item needs a place.
• drop_if becomes keep_if with the predicate negated.
• keep_oks and keep_errs use the single-buffer copy. They don't work in place, because Try(a, e) and a rarely share a layout.

Results: 12 of 12 kept goes from 13/4 to 1/0 (allocs/reallocs), and a unique list filtered in step goes from 13/4 to 1/0. The full eval suite and rc_conformance pass. The new tests cover a shared list reused afterwards and a predicate that captures the list being filtered, the #10368 shape.

Unlike map's extract/write loop, the in-place path only uses list_swap_unsafe and drop_last, which copy a shared list unless the call is marked in-place. So a wrong uniqueness answer should cost a copy, not a wrong result.

Questions:

1. Is this the direction you'd want, or is there a plan to filters, for example via #9775?
2. Should the in-place path be gated off in dev builds and the interpreter, as map's reuse is?
3. Should the "return a shared list unchanged when all of the same PR, or a separate one?

Happy to open an issue and PR with this optimisation.

Richard Feldman (Oct 26 2026 at 19:46):

yeah this is what we always should have been doing :sweat_smile:

Richard Feldman (Oct 26 2026 at 19:46):

I think that implementation is probably a very old "just get it working to unblock people" impl that we never got around to revising

Richard Feldman (Oct 26 2026 at 19:46):

PR welcome!

pixelsprout (Oct 26 2026 at 20:13):

Cool I have put up a PR #12645

Last updated: Nov 04 2026 at 18:54 UTC