Comprehension macros are O(n²) in cel-rust 0.14.5; upstream fix for `map` is on master
Nobody has claimed this yet.
Assessment
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Newbie friendliness
- 45/100
- Issue type
- Bug
- Clarity
- Mostly clear
- Activity status
- Active
- Domain
- documentation, performance, release, testing
Research direction
Wait for cel-rust 0.14.6 or 0.15, then bump it and rerun the cs/c cases in the #45 prototype's bench.py. Check whether the upstream map fix also covers filter, all, exists, and exists_one; add the 10,000-element performance check in tests/test_performance_verification.py and update the standard-library reference if large-list comprehensions remain slow.
Written by the indexing model from the issue text.
Description
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.pythat pins a comprehension over a 10,000-element list under a generous bound (say 200 ms) so a regression is caught. - If
filteris 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).
- Dominant language
- Python
- Stars
- 43
- Forks
- 4
- Avg merge
- 9h 57m
- Merged PRs (30d)
- 14
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from hardbyte/python-common-expression-language
-
enhancement
Difficulty 2/5 1-3 hours Newbie friendliness 78/100
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
-
enhancement
Difficulty 4/5 3-5 days Newbie friendliness 48/100
-
enhancement
Difficulty 5/5 Over a week Newbie friendliness 45/100
-
enhancement
Difficulty 4/5 3-5 days Newbie friendliness 48/100
All issues in hardbyte/python-common-expression-language
Similar issues
-
enhancement
Difficulty 2/5 1-3 hours Newbie friendliness 70/100
canonical/paas-charm#368 · 1 comment ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 75/100
-
tech debt
Difficulty 2/5 1-3 hours Newbie friendliness 75/100
-
Difficulty 1/5 Under an hour Newbie friendliness 90/100
StevenBlack/hosts#3256 ·
-
Difficulty 1/5 Under an hour Newbie friendliness 90/100
qualcomm/qai-appbuilder#275 ·