mempool: use epochs in CalculateDescendants #24942

pull Crypt-iQ wants to merge 1 commits into bitcoin:master from Crypt-iQ:calc_desc_epoch changing 5 files +40 −40

Crypt-iQ commented at 2:01 am on April 22, 2022: contributor
This change allows epochs to be used in CalculateDescendants, which makes the descendant traversal quicker. CalculateDescendants now takes a setEntries parameter so that callers no longer need to call CalculateDescendants in a loop.

The function is basically the same except:
- the single-entry set case is quicker since setDescendants isn’t queried
- the looping calls where setDescendants is used across iterations is removed in favor of just a single call to CalculateDescendants with the set and using an epoch instead of set lookups

mempool: use epochs in CalculateDescendants

This change allows epochs to be used in CalculateDescendants, which
makes the descendant traversal quicker. CalculateDescendants now
takes a setEntries parameter so that callers no longer need to call
CalculateDescendants in a loop.

da15268019

DrahtBot added the label Mempool on Apr 22, 2022
DrahtBot added the label RPC/REST/ZMQ on Apr 22, 2022
DrahtBot added the label TX fees and policy on Apr 22, 2022
vincenzopalazzo commented at 12:48 pm on April 22, 2022: none

Concept ACK
Crypt-iQ commented at 5:40 pm on April 24, 2022: contributor

I don’t see a performance improvement when modifying the complex mempool bench to use Expire (which was replaced here with a single call to CalculateDescendants) and lots of descendants, so I’m not sure if this patch is useful
vincenzopalazzo commented at 9:34 am on April 25, 2022: none

I don’t see a performance improvement when modifying the complex mempool bench to use Expire (which was replaced here with a single call to CalculateDescendants) and lots of descendants, so I’m not sure if this patch is useful

Yeah! because the bottleneck is the set implementation, that uses internally a read black Tree, so in complex mempool the big cost is not the iteration, but the walk of the Tree in the set!

I don’t think here is possible to use the unordered_set, but maybe I’m wrong because I read the code on the flight
Crypt-iQ commented at 12:55 pm on April 25, 2022: contributor

I don’t see a performance improvement when modifying the complex mempool bench to use Expire (which was replaced here with a single call to CalculateDescendants) and lots of descendants, so I’m not sure if this patch is useful

Yeah! because the bottleneck is the set implementation, that uses internally a read black Tree, so in complex mempool the big cost is not the iteration, but the walk of the Tree in the set!

I don’t think here is possible to use the unordered_set, but maybe I’m wrong because I read the code on the flight

This patch walks the rb tree less depending on the “family tree” and the mempool bench can create a very large tree with many descendants. I wonder if the remaining set operations “take over” here even with less lookups
vincenzopalazzo commented at 1:11 pm on April 25, 2022: none

I wonder if the remaining set operations “take over” here even with less lookups

Sounds something to benchmarking the c++ set implementation?
Crypt-iQ commented at 2:00 pm on April 25, 2022: contributor

Closing since this doesn’t actually give a noticeable improvement, maybe if this used a vector there would be some speedup
Crypt-iQ closed this on Apr 25, 2022
Crypt-iQ deleted the branch on Apr 25, 2022
DrahtBot locked this on Apr 25, 2023

Contributors
Crypt-iQ vincenzopalazzo

Labels
TX fees and policy RPC/REST/ZMQ Mempool