Skip to content

mempool & mining: Use the topological ordering to break ties

Calin Culianu requested to merge cculianu/bitcoin-cash-node:mempool/2.1_entry_id_tie_breaker into master

Summary

This closes issue #267 (closed).

This MR affects the "modified feerate" sorter used by mining code.

This MR makes it so that "ties" between sorted 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 (merged) and !1079 (merged) 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.

Test Plan

The mempool unit test that tests this subsystem was modified to test the change.

  • ninja all check-all

No externally-observable behavioral or other changes are introduced by this MR. This MR is just a performance optimization to avoid extra backtracking in CreateNewBlock.

Closes #267 (closed)

Edited by Calin Culianu

Merge request reports