Page MenuHomePhabricator

mempool & mining: Use the topological ordering to break ties
ClosedPublic

Authored by Fabien on Feb 20 2023, 10:44.

Details

Reviewers
PiRK
Group Reviewers
Restricted Project
Commits
rABC38a461f1bd4a: mempool & mining: Use the topological ordering to break ties
Summary
This MR affects the "modified feerate" sorter used by mining code.

This MR makes it so that "ties" between entries are "broken" by their
topological ordering, such that parents come before children if their
fee rates are identical.  This allows mining code to be faster so that
it doesn't have to backtrack as much in CreateNewBlock.

Previous to this MR, GetTime() was used for this purpose which is a
rough approximation of topological ordering, but is not guaranteed for
this purpose (reorgs make it so that parents may have a later time than
their children in the case of resurrected block tx's showing up in the
mempool again!).

The original intent behind the mining code that we merged in !1078 and
!1079 was to sort by fee, but then by parent->child ordering, hence the
tie-breaker logic.

Using GetEntryId() for this purpose, rather than GetTime() accomplishes
this intent in a guaranteed way.

Port of bchn#1147.

Depends on D13141.

Test Plan
ninja all check-all

Diff Detail

Repository
rABC Bitcoin ABC
Lint
Lint Not Applicable
Unit
Tests Not Applicable