Skip to content

cluster mempool: optimized candidate search

Part of cluster mempool: #30289

Depends on #30126, and was split off from it.

This improves the candidate search algorithm introduced in the previous PR with a variety of optimizations.

The resulting search algorithm largely follows Section 2 of How to linearize your cluster, though with a few changes:

  • Connected component analysis is performed inside the search algorithm (creating initial work items per component for each candidate), rather than once at a higher level. This duplicates some work but is significantly simpler in implementation.
  • No ancestor-set based presplitting inside the search is performed; instead, the best value is initialized with the best topologically valid set known to the LIMO algorithm before search starts: the better one out of the highest-feerate remaining ancestor set, and the highest-feerate prefix of remaining transactions in old_linearization.
  • Work items are represented using an included set inc and an undefined set und, rather than included and excluded.
  • Potential sets pot are not computed for work items with empty inc.

At a high level, the only missing optimization from that post is bottleneck analysis; my thinking is that it only really helps with clusters that are already relatively cheap to linearize (doing so would need to be done at a higher level, not inside the search algorithm).


Overview of the impact of each commit here on linearize performance:

Merge request reports

Loading