fork_choice: the filtered block tree costs leaves × depth through get_checkpoint_block

Đang mở
#811 0 bình luận 0 reaction 0 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 6 ngày

Chưa có ai nhận issue này.

Đánh giá

Độ khó
4/5
Thời gian dự kiến
3-5 ngày
Mức phù hợp với người mới
58/100
Loại issue
Lỗi
Độ rõ ràng
Đặc tả rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
rust
Lĩnh vực
backend, performance

Hướng nghiên cứu

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.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

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_ancestor from the justified root answers all of them.
  • Otherwise the checkpoint block lies on path, between the justified root and the leaf. A partition_point by slot over the frames finds it without walking the index.

The randomized differential test against filter_block_tree_by_scan would cover the change.

Ngôn ngữ chính
Rust
Star
86
Fork
34
Merge trung bình
9 ngày 20 giờ
Pull request đã merge (30 ngày)
77

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của lambdaclass/ethlambda

Tất cả issue của lambdaclass/ethlambda

Issue tương tự

Thêm issue về Rust

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.