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

オープン
#57 コメント 0 件 リアクション 0 件 担当者 0 名 GitHub で見る

まだ誰も着手していません。

評価

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

調査の方向性

cel-rust 0.14.6 または 0.15 を待ってから更新し、#45 プロトタイプの bench.py にある cs/c ケースを再実行します。upstream の map の修正で filter、all、exists、exists_one もカバーされるか確認し、tests/test_performance_verification.py に 10,000 要素のパフォーマンスチェックを追加します。大規模なリスト内包表記が依然として遅い場合は、標準ライブラリのリファレンスを更新します。

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

説明

enhancement

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

主要言語
Python
スター
43
フォーク
4
平均マージ
9時間 57分
マージ済み PR(30日)
14

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

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

はじめの一歩

  1. issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
  2. 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
  3. リポジトリをフォークし、ブランチを切って変更します。
  4. issue 番号を参照したプルリクエストを送ります。

hardbyte/python-common-expression-language のほかの issue

hardbyte/python-common-expression-language の issue をすべて見る

似ている issue

Python の issue をもっと見る

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

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