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):
0AddrMan::Add(): -3.5%
1AddrMan::GetAddr(): -76%
2AddrMan::Good(): -0.38%
3AddrMan::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 |
0map$ ./src/bench/bench_bitcoin -filter="AddrMan.*"
1# Benchmark, evals, iterations, total, min, max, median
2AddrManAdd, 5, 5, 4.45807, 0.176704, 0.179945, 0.178443
3AddrManGetAddr, 5, 500, 4.09847, 0.00163663, 0.00164301, 0.0016392
4AddrManGood, 5, 2, 4.66502, 0.460193, 0.474046, 0.467368
5AddrManSelect, 5, 1000000, 2.07299, 4.12892e-07, 4.15564e-07, 4.147e-07
6
7unordered_map$ ./src/bench/bench_bitcoin -filter="AddrMan.*"
8# Benchmark, evals, iterations, total, min, max, median
9AddrManAdd, 5, 5, 4.30032, 0.169753, 0.1738, 0.172047
10AddrManGetAddr, 5, 500, 0.967398, 0.000384406, 0.00038996, 0.000387176
11AddrManGood, 5, 2, 4.64742, 0.460599, 0.471216, 0.464143
12AddrManSelect, 5, 1000000, 1.14085, 2.23899e-07, 2.36962e-07, 2.26767e-07
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;
using and capitalize class
20@@ -21,6 +21,7 @@
21 #include <set>
22 #include <stdint.h>
23 #include <streams.h>
24+#include <unordered_map>
<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>.
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
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;
to_delete instead).
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
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.
Benchmarking results:
0$ ./src/bench/bench_bitcoin -filter="AddrMan.*"
1# Benchmark, evals, iterations, total, min, max, median
2AddrManAdd, 5, 5, 1.15889, 0.0458257, 0.0469068, 0.0464069
3AddrManGetAddr, 5, 500, 1.94467, 0.000772949, 0.000789915, 0.000775272
4AddrManGood, 5, 2, 5.69597, 0.563135, 0.57652, 0.570197
5AddrManSelect, 5, 1000000, 1.17994, 2.32975e-07, 2.37942e-07, 2.36478e-07
0$ ./src/bench/bench_bitcoin -filter="AddrMan.*"
1# Benchmark, evals, iterations, total, min, max, median
2AddrManAdd, 5, 5, 0.972042, 0.0383488, 0.0396571, 0.0386554
3AddrManGetAddr, 5, 500, 0.649199, 0.000256967, 0.000262957, 0.00025942
4AddrManGood, 5, 2, 5.35751, 0.531294, 0.540723, 0.534681
5AddrManSelect, 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);
0 const auto it = mapAddr.find(addr);
const if I end up modifying this PR for some bigger reason. But I think it is not worth invalidating the ACK.
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);
0 const auto it2 = mapInfo.find((*it).second);
const if I end up modifying this PR for some bigger reason. But I think it is not worth invalidating the ACK.
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();
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:
0 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.
m_net as well?
m_net existed! I added it now, thanks!
nit: If #includes in addrman.h are already touched, mind moving
0#include <fs.h>
1#include <hash.h>
2#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());
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).
0| ns/op | op/s | err% | total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2| 47,378,973.00 | 21.11 | 2.1% | 0.53 | `AddrManAdd`
3| 1,585,044.00 | 630.90 | 1.8% | 0.02 | `AddrManGetAddr`
4| 427,775,318.00 | 2.34 | 1.0% | 2.13 | `AddrManGood`
5| 468.57 | 2,134,157.56 | 1.5% | 0.00 | `AddrManSelect`
0| ns/op | op/s | err% | total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2| 42,701,933.00 | 23.42 | 2.6% | 0.47 | `AddrManAdd`
3| 572,564.00 | 1,746.53 | 3.8% | 0.01 | `AddrManGetAddr`
4| 429,306,009.00 | 2.33 | 2.6% | 2.17 | `AddrManGood`
5| 406.60 | 2,459,419.58 | 5.0% | 0.00 | `AddrManSelect`
11@@ -12,6 +12,8 @@
12 #include <attributes.h>
13 #include <compat.h>
14 #include <prevector.h>
15+#include <crypto/siphash.h>
191@@ -190,6 +192,7 @@ class CNetAddr
192 }
193
194 friend class CSubNet;
195+ friend class CNetAddrHash;
friend class declarements (both for alphabetical order and code order of the two classes, below)
… after
-std=c++17becomes mandatory
it is now
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));
hasher.Write(a.m_net);; it’ll interpret a.m_net as a uint64_t and use the optimized integer hasher.
int to uint64_t will not upset some compiler.
Write() method that takes an integer argument (modulo int -> uint64 conversion which is ok because we never pass negative values).
6a1a28f2ad...c22e98b30d: address review suggestion
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:
0 for (auto it = mapInfo.cbegin(); it != mapInfo.cend(); ) {
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!
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
0- auto itCopy = it++;
1+ const auto itCopy = it++;
2 Delete(itCopy->first);
3- nLostUnk++;
4+ ++nLostUnk;
`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
