Understanding the `bmc-depth` bottleneck
まだ誰も着手していません。
評価
- 難易度
- 4/5
- 見積もり時間
- 3〜5日
- 初心者へのやさしさ
- 35/100
- issue の種類
- バグ
- 明瞭さ
- おおむね明確
- 活発さ
- 停滞
- 技術スタック
- python
- 領域
- performance
調査の方向性
Start in pyk/src/pyk/proof/reachability.py at the linked shortest_path and same_loop locations, and reproduce bmc-depth on a proof with 1000+ nodes and parallel threads. Profile the Python and kore-rpc-booster processes while comparing runs with and without bmc-depth. Done means identifying which computation causes the slowdown and documenting measured evidence for the bottleneck.
索引モデルが issue の本文から書いたものです。
説明
In real-world proofs that use bmc-depth and are sufficiently large (1000+ nodes), there is a massive slowdown introduced by the associated computations, to the point that a Kontrol proof that passes without bmc-depth in ~1h45m does not finish after more than a day with bmc-depth activated. The manifestation of this, at least on my machine and with 6 parallel threads, is a python process that is constantly at 100% and a kore-rpc-booster process that is way below its maximal throughput. The reasons for this could be:
- the computation of
shortest_pathwhen understanding the next steps, which needs to traverse the KCFG and does not appear to rely on dynamic programming and may be forcing thread synchronisation: https://github.com/runtimeverification/k/blob/76c534f16df17febd4560e9b492cfa024d82e9b0/pyk/src/pyk/proof/reachability.py#L182 - the computation of
same_loop, which extracts and examines cells in aCTerm, which could be costly: https://github.com/runtimeverification/k/blob/76c534f16df17febd4560e9b492cfa024d82e9b0/pyk/src/pyk/proof/reachability.py#L793
- 主要言語
- Python
- スター
- 598
- フォーク
- 164
- PR マージ指標
- 30日以内にマージされた PR はありません
環境構築
- Dockerfile・Docker Compose ファイルなし
- プルリクエストのテンプレートなし
- コントリビューションガイドを読む
はじめの一歩
- issue を最後まで読み、次にプロジェクトのコントリビューションガイドを読みます。
- 着手することを issue にコメントします — 二人が同じ作業をするのを防げます。
- リポジトリをフォークし、ブランチを切って変更します。
- issue 番号を参照したプルリクエストを送ります。
runtimeverification/k のほかの issue
-
難易度 4/5 3〜5日 初心者へのやさしさ 43/100
runtimeverification/k#4942 ·
-
bug
難易度 3/5 半日 初心者へのやさしさ 75/100
runtimeverification/k#4941 ·
-
Introduce composable symbolic execution interface in pyx再び着手できるかも @Stevengre が 125 日前に担当しましたが、オープン中のプルリクエストはありません。 オープン
runtimeverification/k#4939 · 担当者 1 名 ·
-
Concolic Explorerオープン
難易度 5/5 1週間以上 初心者へのやさしさ 32/100
runtimeverification/k#4937 ·
-
難易度 5/5 1週間以上 初心者へのやさしさ 30/100
runtimeverification/k#4936 ·
runtimeverification/k の issue をすべて見る
似ている issue
-
area/config comp/tools P2 platform/telegram type/bug
難易度 2/5 1〜3時間 初心者へのやさしさ 74/100
NousResearch/hermes-agent#145412 ·
メンテナーはふだん 1 日以内に返信
-
[oblt-aw][autodoc] Update docs for security org scaffolding and Docs AI menu permission changes対応中かも @github-actions が今日担当しました。 オープン
難易度 2/5 1〜3時間 初心者へのやさしさ 75/100
メンテナーはふだん 1 日以内に返信
-
Community project: hosted MOSS-Image studio with a visual JSON layout builder (no ComfyUI needed)オープン
難易度 1/5 1〜3時間 初心者へのやさしさ 65/100
OpenMOSS/MOSS-Image#27 · コメント 1 件 ·
メンテナーはふだん 1 日以内に返信
-
難易度 2/5 1〜3時間 初心者へのやさしさ 76/100
deepspeedai/DeepSpeed#8925 · コメント 1 件 ·
メンテナーはふだん 3 日以内に返信
-
external integration integration-submission
難易度 2/5 1〜3時間 初心者へのやさしさ 68/100
langchain-ai/docs#7077 ·
メンテナーはふだん 1 日以内に返信