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

Offen
#811 0 Kommentare 0 Reaktionen 0 zugewiesene Personen Auf GitHub ansehen

Maintainer antworten meist innerhalb von 6 Tagen

Dieses Issue hat noch niemand übernommen.

Bewertung

Schwierigkeit
4/5
Geschätzter Aufwand
3-5 Tage
Anfängerfreundlichkeit
58/100
Issue-Typ
Bug
Klarheit
Klar beschrieben
Aktivitätsstatus
Aktiv
Tech-Stack
rust
Bereich
backend, performance

Rechercherichtung

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.

Vom Indexierungsmodell aus dem Issue-Text verfasst.

Beschreibung

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.

Vorherrschende Sprache
Rust
Sterne
86
Forks
34
Ø Merge
9 T. 20 Std.
Gemergte PRs (30 T.)
77

Entwicklungsumgebung

Erste Schritte

  1. Lesen Sie das ganze Issue und danach den Beitragsleitfaden des Projekts.
  2. Schreiben Sie ins Issue, dass Sie es übernehmen — das erspart doppelte Arbeit.
  3. Forken Sie das Repository und arbeiten Sie in einem Branch.
  4. Öffnen Sie einen Pull Request, der die Issue-Nummer nennt.

Mehr aus lambdaclass/ethlambda

Alle Issues in lambdaclass/ethlambda

Ähnliche Issues

Weitere Issues zu Rust

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.