hardbyte / hardbyte/python-common-expression-language

Comprehension macros are O(n²) in cel-rust 0.14.5; upstream fix for `map` is on master

オープン
#57 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る
enhancement
主要言語
Python
スター
43
フォーク
4
平均マージ
9時間 57分
マージ済み PR(30日)
14

説明

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>`, 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).

コントリビューションガイド

コントリビューションガイドを開く

調査の方向性

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.

索引モデルが issue の本文から書いたものです。

評価

技術スタック
python, rust
領域
documentation, performance, release, testing
issue の種類
バグ
難易度
4/5
見積もり時間
3〜5日
活発さ
活発
明瞭さ
おおむね明確
初心者へのやさしさ
45/100

新しい issue をメールで受け取る

初心者向けの GitHub issue を短くまとめたダイジェスト。