fork_choice: the filtered block tree costs leaves × depth through get_checkpoint_block
维护者通常 6 天内回复
还没有人认领这个 Issue。
评估
- 难度
- 4/5
- 预计耗时
- 3-5 天
- 新手友好度
- 58/100
- Issue 类型
- 缺陷
- 描述清晰度
- 描述清楚
- 活跃度
- 活跃
- 技术栈
- rust
- 领域
- backend, performance
调研方向
Start in crates/blockchain/state_transition/src/beacon/fork_choice.rs at is_viable_leaf and read the get_checkpoint_block calls alongside the path stack added by #758. Compare the proposed ancestor and partition_point lookup with filter_block_tree_by_scan; the issue identifies a randomized differential test as coverage. Done means checkpoint lookup no longer walks each leaf's ancestry and the differential test passes.
由索引模型根据 Issue 内容生成。
描述
is_viable_leaf (crates/blockchain/state_transition/src/beacon/fork_choice.rs:1989) calls get_checkpoint_block(index, block_root, finalized_checkpoint.epoch) once per leaf of the justified subtree. Each call walks that leaf back to the finalized epoch's start slot. Every head computation therefore costs leaves × depth.
The #746 measurements (https://github.com/lambdaclass/ethlambda/pull/746#issuecomment-6533272351) put that at 74 ms with 14,851 blocks and 451 leaves. During a finality stall the depth grows by a block every slot. Until lambdaclass/ethlambda#758, a stack overflow capped that depth; now nothing does.
This is out of scope for lambdaclass/ethlambda#758, which only replaces the recursion with an explicit stack and keeps the per-leaf check unchanged.
A fix (Pablo's sketch in the #758 review), using the path stack that #758 adds:
- If the justified block's slot is at or above the finalized epoch's start slot, every leaf has the same checkpoint block. One
get_ancestorfrom the justified root answers all of them. - Otherwise the checkpoint block lies on
path, between the justified root and the leaf. Apartition_pointby slot over the frames finds it without walking the index.
The randomized differential test against filter_block_tree_by_scan would cover the change.
- 主要语言
- Rust
- 星标
- 86
- 派生
- 34
- 平均合并
- 9 天 20 小时
- 30 天内合并 PR
- 77
环境准备
- 提供 Dockerfile 或 Docker Compose 文件
- 有 Pull Request 模板
- 阅读贡献指南
从这里开始
- 先读完整个 Issue,再读项目的贡献指南。
- 在 Issue 下留言说明你要接手 —— 这能避免两个人做同样的事。
- Fork 仓库,在一个分支上完成修改。
- 提交 Pull Request,并在描述里引用这个 Issue 编号。
lambdaclass/ethlambda 的其他 Issue
-
难度 2/5 1-3 小时 新手友好度 76/100
lambdaclass/ethlambda#850 ·
维护者通常 6 天内回复
-
难度 2/5 1-3 小时 新手友好度 68/100
lambdaclass/ethlambda#777 · 1 个 reaction ·
维护者通常 6 天内回复
-
Run all gossip validation tests可能重新可做 @dicethedev 于 9 天前认领,目前没有进行中的 PR。 未关闭
难度 2/5 1-3 小时 新手友好度 62/100
lambdaclass/ethlambda#725 · 2 条评论 ·
维护者通常 6 天内回复
-
Handle malformed DB data可能重新可做 @dicethedev 于 115 天前认领,目前没有进行中的 PR。 未关闭
难度 2/5 1-3 小时 新手友好度 76/100
lambdaclass/ethlambda#529 · 4 条评论 ·
维护者通常 6 天内回复
-
Document architectural choices可能重新可做 @dicethedev 于 115 天前认领,目前没有进行中的 PR。 未关闭
难度 2/5 1-3 小时 新手友好度 68/100
lambdaclass/ethlambda#521 · 2 条评论 ·
维护者通常 6 天内回复
查看 lambdaclass/ethlambda 的全部 Issue
相似的 Issue
-
难度 2/5 1-3 小时 新手友好度 84/100
antithesishq/bombadil#473 ·
维护者通常 2 天内回复
-
bug
难度 2/5 1-3 小时 新手友好度 72/100
libracoder/kiri#669 ·
维护者通常 1 天内回复
-
难度 1/5 1 小时以内 新手友好度 88/100
维护者通常 5 天内回复
-
autofixer: follow-up
难度 2/5 1-3 小时 新手友好度 75/100
tursodatabase/turso#12217 ·
维护者通常 1 天内回复
-
Declare the CMS schema library in the optional recipients extra可能已有人在做 关联的 PR 仍在进行中或已合并。 未关闭area:python in-progress
难度 2/5 1-3 小时 新手友好度 82/100
维护者通常 1 天内回复