CAddrMan uses std::map internally even though it does not require
that the map's elements are sorted. std::map's access time is
O(log(map size)). std::unordered_map is more suitable as it has a
O(1) access time.
This patch lowers the execution times of CAddrMan's methods as follows
(as per src/bench/addrman.cpp):
AddrMan::Add(): -3.5%
AddrMan::GetAddr(): -76%
AddrMan::Good(): -0.38%
AddrMan::Select(): -45%
Full output from the benchmark (./src/bench/bench_bitcoin -filter="AddrMan.*"):
std::map
| Benchmark | evals | iterations | total | min | max | median |
|---|---|---|---|---|---|---|
| AddrManAdd | 5 | 5 | 4.45807 | 0.176704 | 0.179945 | 0.178443 |
| AddrManGetAddr | 5 | 500 | 4.09847 | 0.00163663 | 0.00164301 | 0.0016392 |
| AddrManGood | 5 | 2 | 4.66502 | 0.460193 | 0.474046 | 0.467368 |
| AddrManSelect | 5 | 1000000 | 2.07299 | 4.12892e-07 | 4.15564e-07 | 4.147e-07 |
std::unordered_map
| Benchmark | evals | iterations | total | min | max | median |
|---|---|---|---|---|---|---|
| AddrManAdd | 5 | 5 | 4.30032 | 0.169753 | 0.1738 | 0.172047 |
| AddrManGetAddr | 5 | 500 | 0.967398 | 0.000384406 | 0.00038996 | 0.000387176 |
| AddrManGood | 5 | 2 | 4.64742 | 0.460599 | 0.471216 | 0.464143 |
| AddrManSelect | 5 | 1000000 | 1.14085 | 2.23899e-07 | 2.36962e-07 | 2.26767e-07 |
<details> <summary>raw output</summary>
map$ ./src/bench/bench_bitcoin -filter="AddrMan.*"
# Benchmark, evals, iterations, total, min, max, median
AddrManAdd, 5, 5, 4.45807, 0.176704, 0.179945, 0.178443
AddrManGetAddr, 5, 500, 4.09847, 0.00163663, 0.00164301, 0.0016392
AddrManGood, 5, 2, 4.66502, 0.460193, 0.474046, 0.467368
AddrManSelect, 5, 1000000, 2.07299, 4.12892e-07, 4.15564e-07, 4.147e-07
unordered_map$ ./src/bench/bench_bitcoin -filter="AddrMan.*"
# Benchmark, evals, iterations, total, min, max, median
AddrManAdd, 5, 5, 4.30032, 0.169753, 0.1738, 0.172047
AddrManGetAddr, 5, 500, 0.967398, 0.000384406, 0.00038996, 0.000387176
AddrManGood, 5, 2, 4.64742, 0.460599, 0.471216, 0.464143
AddrManSelect, 5, 1000000, 1.14085, 2.23899e-07, 2.36962e-07, 2.26767e-07
</details>
181 | @@ -181,14 +182,17 @@ friend class CAddrManTest; 182 | mutable RecursiveMutex cs; 183 | 184 | private: 185 | + typedef std::unordered_map<int, CAddrInfo> mapInfoType; 186 | + typedef std::unordered_map<CNetAddr, int, CNetAddrHash> mapAddrType;
nit: using and capitalize class
20 | @@ -21,6 +21,7 @@ 21 | #include <set> 22 | #include <stdint.h> 23 | #include <streams.h> 24 | +#include <unordered_map>
nit: looks like you can move the <map> include to addrman.cpp now.
Right! And even better - std::map is only used inside CAddrMan::Check_() in a way that fits unordered_map better - we only insert elements, query elements by key and check container size.
So I changed CAddrMan::Check_() to use unordered_(set|map) and removed the #include <map>.
Would it be possible to submit the benchmark upfront as a separate pull, so that https://codespeed.bitcoinperf.com/ can start running it?
Removed the first commit (which introduced the benchmark), now that it is already merged into master and rebased.
106 | @@ -107,6 +107,19 @@ class CNetAddr 107 | } 108 | 109 | friend class CSubNet; 110 | + friend struct CNetAddrHash; 111 | +}; 112 | + 113 | +struct CNetAddrHash
You'll want to use a salted hash here (use CSipHasher from crypto/siphash.h or a specialization; see SaltedOutpointHasher in coins.h for inspiration). Otherwise an attacker may be able to degrade our performance by giving us a bunch of entries that all end up in the same bucket).
Done, thanks for the suggestion!
498 | - it++; 499 | + ++it; 500 | } 501 | } 502 | +#else // pre C++14, drop this once we switch to C++14 or higher 503 | + std::vector<MapInfo::const_iterator> toDelete;
Nit: new code should use the coding style described in doc/developer-.nodes.md (e.g. to_delete instead).
Done
<!--e57a25ab6845829454e8d69fc972939a-->
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
<!--174a7506f384e20aa4161008e828411d-->
Reviewers, this pull request conflicts with the following ones:
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.
utACK 7cc317285f388f0cda974a321761992248257fb8
Concept ACK.
Benchmarking results:
$ ./src/bench/bench_bitcoin -filter="AddrMan.*"
# Benchmark, evals, iterations, total, min, max, median
AddrManAdd, 5, 5, 1.15889, 0.0458257, 0.0469068, 0.0464069
AddrManGetAddr, 5, 500, 1.94467, 0.000772949, 0.000789915, 0.000775272
AddrManGood, 5, 2, 5.69597, 0.563135, 0.57652, 0.570197
AddrManSelect, 5, 1000000, 1.17994, 2.32975e-07, 2.37942e-07, 2.36478e-07
$ ./src/bench/bench_bitcoin -filter="AddrMan.*"
# Benchmark, evals, iterations, total, min, max, median
AddrManAdd, 5, 5, 0.972042, 0.0383488, 0.0396571, 0.0386554
AddrManGetAddr, 5, 500, 0.649199, 0.000256967, 0.000262957, 0.00025942
AddrManGood, 5, 2, 5.35751, 0.531294, 0.540723, 0.534681
AddrManSelect, 5, 1000000, 0.657766, 1.29313e-07, 1.36428e-07, 1.30873e-07
Nice :)
75 | @@ -73,12 +76,12 @@ double CAddrInfo::GetChance(int64_t nNow) const 76 | 77 | CAddrInfo* CAddrMan::Find(const CNetAddr& addr, int* pnId) 78 | { 79 | - std::map<CNetAddr, int>::iterator it = mapAddr.find(addr); 80 | + auto it = mapAddr.find(addr);
const auto it = mapAddr.find(addr);
Right, I will add the const if I end up modifying this PR for some bigger reason. But I think it is not worth invalidating the ACK.
Done.
81 | if (it == mapAddr.end()) 82 | return nullptr; 83 | if (pnId) 84 | *pnId = (*it).second; 85 | - std::map<int, CAddrInfo>::iterator it2 = mapInfo.find((*it).second); 86 | + auto it2 = mapInfo.find((*it).second);
const auto it2 = mapInfo.find((*it).second);
Right, I will add the const if I end up modifying this PR for some bigger reason. But I think it is not worth invalidating the ACK.
Done.
117 | +public: 118 | + size_t operator()(const CNetAddr& a) const noexcept 119 | + { 120 | + CSipHasher hasher(salt_k0, salt_k1); 121 | + hasher.Write(a.ip, sizeof(a.ip)); 122 | + return (size_t)hasher.Finalize();
Is this safe on 32-bit system (e.g., ARM7)?
Yes, I think it is.
Finalize() returns uint64_t and even if size_t is 32 bits, then it will just take "half" of the hash. SaltedOutpointHasher already does such a conversion from uint64_t to size_t and it contains some comment that size_t must be returned.
nit: All calls could be chained:
return CSipHasher(salt_k0, salt_k1).Write(a.ip, sizeof(a.ip)).Finalize();
I actually find the 3-line variant easier to read (that could be subjective). The 3-line variant is more manageable wrt setting a breakpoint or reading a backtrace (e.g. if you only see it crashed on that multi-chained-line it wouldn't be clear whether it crashed in the constructor, in the Write() method or in the Finalize() method).
I would prefer to leave it as is.
Any reason to not include m_net as well?
No. That code is from before m_net existed! I added it now, thanks!
nit: If #includes in addrman.h are already touched, mind moving
#include <fs.h>
#include <hash.h>
#include <streams.h>
into the first group?
nit: If #includes in addrman.h are already touched, mind moving...
Good catch, they should be moved! Given that there is already one ACK, I will move the headers if I alter this PR or as a followup PR if this gets merged as is now.
122 | + return (size_t)hasher.Finalize(); 123 | + } 124 | + 125 | +private: 126 | + const uint64_t salt_k0 = GetRand(std::numeric_limits<uint64_t>::max()); 127 | + const uint64_t salt_k1 = GetRand(std::numeric_limits<uint64_t>::max());
nit: Class member naming convention?
Right! A convention is a convention. Renamed.
Prefixed
salt_k0andsalt_k1withm_to abide to the naming convention. diff.
If some changes are made already, maybe make these ones ((https://github.com/bitcoin/bitcoin/pull/18722#discussion_r440238143), #18722 (review), #18722 (comment)) too?
:)
Updated benchmarking results (now with nanobench, which meant I had to look up what these categories represented). In sum, it looks like a performance upgrade, especially for AddrManGetAddr though the error rate did jump up for me and I had to run the PR version a bunch of times to get something stable while master was stable the first time (though reading through 18011 this may be OS specific - this was run on OSX).
| ns/op | op/s | err% | total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
| 47,378,973.00 | 21.11 | 2.1% | 0.53 | `AddrManAdd`
| 1,585,044.00 | 630.90 | 1.8% | 0.02 | `AddrManGetAddr`
| 427,775,318.00 | 2.34 | 1.0% | 2.13 | `AddrManGood`
| 468.57 | 2,134,157.56 | 1.5% | 0.00 | `AddrManSelect`
| ns/op | op/s | err% | total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
| 42,701,933.00 | 23.42 | 2.6% | 0.47 | `AddrManAdd`
| 572,564.00 | 1,746.53 | 3.8% | 0.01 | `AddrManGetAddr`
| 429,306,009.00 | 2.33 | 2.6% | 2.17 | `AddrManGood`
| 406.60 | 2,459,419.58 | 5.0% | 0.00 | `AddrManSelect`
Rebased to resolve conflicts.
11 | @@ -12,6 +12,8 @@ 12 | #include <attributes.h> 13 | #include <compat.h> 14 | #include <prevector.h> 15 | +#include <crypto/siphash.h>
nit: The latest rebasing destroyed alphabetic order of headers :)
Fixed, someday we may consider to have an automated clang-format enforcement in CI...
re-ACK 1e1cc9d8594b0ffba1173d8e431e351228691536, only rebased.
re-ACK 7dddf330fe9f17e20df7bc7431ad3f7b740a3a9c, only headers got correct order.
191 | @@ -190,6 +192,7 @@ class CNetAddr 192 | } 193 | 194 | friend class CSubNet; 195 | + friend class CNetAddrHash;
nit if you retouch, inverse the order of these two friend class declarements (both for alphabetical order and code order of the two classes, below)
Done
Code review ACK 7dddf330fe9f17e20df7bc7431ad3f7b740a3a9c also: debug build is clean, unit tests are green, ran bitcoind and observed debug log and -netinfo
Concept ACK. I think we can merge this after the next branch off, once we start requiring C++17, and skip the addition of the pre-C++14 code.
concept ACK. Will review after split-off when the pre-C++14 code is removed.
Rebased to resolve conflicts.
... after
-std=c++17becomes mandatory
it is now
d517c9d37...6f0c9f539: rebase due to conflicts
6f0c9f5390...6a1a28f2ad: rebased due to conflicts, plus add m_net to the CNetAddr hashing.
484 | +{ 485 | +public: 486 | + size_t operator()(const CNetAddr& a) const noexcept 487 | + { 488 | + CSipHasher hasher(m_salt_k0, m_salt_k1); 489 | + hasher.Write(reinterpret_cast<const uint8_t*>(&a.m_net), sizeof(a.m_net));
Micronit: this reinterpret cast is a bit ugly. You could avoid it by just doing hasher.Write(a.m_net);; it'll interpret a.m_net as a uint64_t and use the optimized integer hasher.
Done. I hope the implicit conversion from int to uint64_t will not upset some compiler.
The ugliness could maybe be considered a virtue; it's explicit that this is an "on your head be it!" type of cast and highlights that the code could ideally be improved. https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#es49-if-you-must-use-a-cast-use-a-named-cast
Here we can do without a cast since there is Write() method that takes an integer argument (modulo int -> uint64 conversion which is ok because we never pass negative values).
utACK 6a1a28f2ad0d84bf30debbe94c5bd8db80a45702
6a1a28f2ad...c22e98b30d: address review suggestion
ACK c22e98b30d9cd5d84ee3c14488defc25b3f998dd
571 | @@ -569,13 +572,13 @@ friend class CAddrManTest; 572 | 573 | // Prune new entries with refcount 0 (as a result of collisions). 574 | int nLostUnk = 0; 575 | - for (std::map<int, CAddrInfo>::const_iterator it = mapInfo.begin(); it != mapInfo.end(); ) { 576 | + for (MapInfo::const_iterator it = mapInfo.begin(); it != mapInfo.end(); ) {
nit:
for (auto it = mapInfo.cbegin(); it != mapInfo.cend(); ) {
Done. Also, skipping the mention of MapInfo here makes it used in just one place. Dropped it and used std::unordered_map<... directly since there is no repetition of the tedious std::unordered_map<... now. Thanks!
ACK c22e98b30d9cd5d84ee3c14488defc25b3f998dd
c22e98b30d...1f4ee9c905: rebase due to conflicts and address review suggestion
439 | + for (auto it = mapInfo.cbegin(); it != mapInfo.cend(); ) { 440 | if (it->second.fInTried == false && it->second.nRefCount == 0) { 441 | - std::map<int, CAddrInfo>::const_iterator itCopy = it++; 442 | + auto itCopy = it++; 443 | Delete(itCopy->first); 444 | nLostUnk++;
nit
- auto itCopy = it++;
+ const auto itCopy = it++;
Delete(itCopy->first);
- nLostUnk++;
+ ++nLostUnk;
Done
ACK 1f4ee9c90531986f7f045f1987df8b3a8fa60433
`CAddrMan` uses `std::map` internally even though it does not require
that the map's elements are sorted. `std::map`'s access time is
`O(log(map size))`. `std::unordered_map` is more suitable as it has a
`O(1)` access time.
This patch lowers the execution times of `CAddrMan`'s methods as follows
(as per `src/bench/addrman.cpp`):
```
AddrMan::Add(): -3.5%
AddrMan::GetAddr(): -76%
AddrMan::Good(): -0.38%
AddrMan::Select(): -45%
```
1f4ee9c905...a92485b2c2: address review suggestion
ACK a92485b2c250fd18f55d22aa32722bf52ab32bfe
ACK a92485b2c250fd18f55d22aa32722bf52ab32bfe