moonbitlang / core / 6283

91%

Build Type

push

github

Committed by bobzhang

Commit Message

perf(immut): keep from_iter streaming instead of bulk-building

Bulk-building from an iterator required `iter.to_array()` first, which changed
live auxiliary memory from O(distinct elements) to O(input length). Folding a
large duplicate-heavy stream into a small set — 10M items with 10 distinct
values, say — went from holding a 10-node tree to holding a 10M-element array.

Restore the fold for both `SortedMap::from_iter` and `SortedSet::from_iter`.
The array constructors keep the bulk build, so callers who want that path and
can afford the buffer can still write `SortedSet(iter.to_array())` and choose
the trade-off explicitly.

With the iterator entry points folding again, the set's `keep_first` plumbing
had only one reachable value, so it is dropped from
`sorted_set_compact_ordered_array`, `sorted_set_from_unsorted_buffer` and
`sorted_set_dedupe_in_place`, along with the two now-unreachable
`sorted_set_from_iter_array*` helpers.

Measured (native, n=10000). The array constructors are unaffected — SortedMap
ordered 182.61 us and SortedSet ordered 197.63 us, against 4.02 ms and 5.20 ms
on main; their slowest shape, random input, is 985.59 us and 391.65 us against
3.12 ms and 3.06 ms. from_iter returns to the main baseline across every shape,
3.04-5.20 ms here against 3.01-5.23 ms on main.

Signed-off-by: Codex CLI <codex@openai.com>

Coverage Stats

9 of 9 new or added lines in 3 files covered. (100.0%)

6 existing lines in 1 file now uncovered.

16745 of 18428 relevant lines covered (90.87%)

306435.52 hits per line