Do not fully sort all nodes for addr relay #8690

pull sipa wants to merge 1 commits into bitcoin:master from sipa:heapaddrsort changing 1 files +16 −7

sipa commented at 12:15 PM on September 9, 2016: member

This is a small optimization, but I have not benchmarked.

Instead of building a hash->node map for each address being relayed, and then picking the top ones, just compute the top 1-2 ones directly.
sipa renamed this:
~~Use a heap to not fully sort all nodes for addr relay~~
Do not fully sort all nodes for addr relay
on Sep 9, 2016
sipa commented at 12:22 PM on September 9, 2016: member

I had an alternative version that used a heap (which needs less iterator arithmetic), but realized that just explicitly keeping track of the top two is faster (and doesn't need any allocations).
rebroad commented at 2:49 PM on September 15, 2016: contributor

@sipa is it worth benchmarking this (since you mentioned benchmarking)?
sipa commented at 1:36 PM on September 19, 2016: member

@rebroad Perhaps, but that will need abstracting this code out so it can be tested in separation from the rest of the p2p message handing.
laanwj added the label P2P on Sep 22, 2016

in src/main.cpp:None in ef8650715c outdated

4741 | @@ -4742,19 +4742,27 @@ static void RelayAddress(const CAddress& addr, bool fReachable, CConnman& connma
4742 |      static const uint64_t salt0 = GetRand(std::numeric_limits<uint64_t>::max());
4743 |      static const uint64_t salt1 = GetRand(std::numeric_limits<uint64_t>::max());
4744 |      uint64_t hashAddr = addr.GetHash();
4745 | -    std::multimap<uint64_t, CNode*> mapMix;
4746 |      const CSipHasher hasher = CSipHasher(salt0, salt1).Write(hashAddr << 32).Write((GetTime() + hashAddr) / (24*60*60));
4747 |  
4748 | -    auto sortfunc = [&mapMix, &hasher](CNode* pnode) {
4749 | +    std::array<std::pair<uint64_t, CNode*>,2> best{{{0, nullptr}, {0, nullptr}}};
4750 | +

gmaxwell commented at 6:47 PM on September 22, 2016:

There should be an assert here that nRelayNodes is <=2, no?

sipa force-pushed on Oct 2, 2016
sipa force-pushed on Oct 2, 2016
sipa force-pushed on Oct 2, 2016
sipa commented at 11:58 PM on October 2, 2016: member

Rebased and addressed @gmaxwell's nit.
gmaxwell commented at 5:28 AM on November 1, 2016: contributor

utACK.

Do not fully sort all nodes for addr relay

As we only need 1 or 2, explicitly keep track of the best ones.

a33b1691f1

sipa force-pushed on Nov 3, 2016
sipa commented at 7:22 AM on November 3, 2016: member

Rebased after #8914.
laanwj commented at 7:19 AM on November 23, 2016: member

I had an alternative version that used a heap (which needs less iterator arithmetic), but realized that just explicitly keeping track of the top two is faster (and doesn't need any allocations).

Yes if you just need the top two, a heap is overkill.

Even if this doesn't speed up the critical path this conceptually makes a lot of sense.

utACK a33b169
laanwj merged this on Nov 23, 2016
laanwj closed this on Nov 23, 2016
laanwj referenced this in commit 791b58d148 on Nov 23, 2016
codablock referenced this in commit 2d87a0fdd7 on Jan 15, 2018
andvgal referenced this in commit 7290da81dc on Jan 6, 2019
CryptoCentric referenced this in commit 1f90dddfa2 on Feb 24, 2019
MarcoFalke locked this on Sep 8, 2021

Contributors

Labels