You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Comprehension macros are O(n²) in cel-rust 0.14.5; upstream fix for map is on master #57
Found while benchmarking for #45. Executing items.filter(i, i % 3 == 0).map(i, i * i).size() against a Context holding an int list scales quadratically with the list length (release build, min of repeats):
elements
time per execute
1,000
17 ms
2,000
66 ms
4,000
251 ms
8,000
940 ms
20,000
5.8 s
Each doubling costs ~4×. cel-rust 0.14.5's comprehension macros rebuild the accumulator list on every append (Value::List is an Arc<Vec<_>>, so appending clones the vector), which makes map/filter over anything beyond a few thousand elements unusable. Nothing in this wrapper contributes; a dict context and a Context behave identically.
Upstream already has the fix for map on master, unreleased: cel-rust/cel-rust#341 "perf(macros): map mutates List in place" (merged 2026-09-13, on top of "perf(map): Added mutable List used in map"). It is not clear from the PR title whether filter, all, exists and exists_one got the same treatment.
To do
When the next cel-rust release (0.14.6 or 0.15) ships, bump and re-run the table above; add a test in tests/test_performance_verification.py that pins a comprehension over a 10,000-element list under a generous bound (say 200 ms) so a regression is caught.
If filter is still quadratic after the bump, raise it upstream with the numbers.
Until then the standard-library reference should say that comprehensions over large lists are slow in the current cel-rust, since policy engines routinely filter lists of thousands of records.
Benchmark script: the cs/c cases in the #45 prototype's bench.py (measured on 4 cores).
Activity