Skip to content

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

Open

Description

@MegaRedHand

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 (#746 (comment)) 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 #758, a stack overflow capped that depth; now nothing does.

This is out of scope for #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.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions