diff options
author | fanquake <fanquake@gmail.com> | 2021-06-12 11:40:34 +0800 |
---|---|---|
committer | fanquake <fanquake@gmail.com> | 2021-06-12 11:41:27 +0800 |
commit | 1a369f006fd0bec373b95001ed84b480e852f191 (patch) | |
tree | fb7a7e831bac9cac859e1b26b783c78596a2cc5b /src | |
parent | 9795e8ec8c279e0df34aee7241bc3b5720a5b380 (diff) | |
parent | a92485b2c250fd18f55d22aa32722bf52ab32bfe (diff) | |
download | bitcoin-1a369f006fd0bec373b95001ed84b480e852f191.tar.xz |
Merge bitcoin/bitcoin#18722: addrman: improve performance by using more suitable containers
a92485b2c250fd18f55d22aa32722bf52ab32bfe addrman: use unordered_map instead of map (Vasil Dimov)
Pull request description:
`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%
```
ACKs for top commit:
jonatack:
ACK a92485b2c250fd18f55d22aa32722bf52ab32bfe
achow101:
ACK a92485b2c250fd18f55d22aa32722bf52ab32bfe
hebasto:
re-ACK a92485b2c250fd18f55d22aa32722bf52ab32bfe, only suggested changes and rebased since my [previous](https://github.com/bitcoin/bitcoin/pull/18722#pullrequestreview-666663681) review.
Tree-SHA512: d82959a00e6bd68a6c4c5a265dd08849e6602ac3231293b7a3a3b7bf82ab1d3ba77f8ca682919c15c5d601b13e468b8836fcf19595248116635f7a50d02ed603
Diffstat (limited to 'src')
-rw-r--r-- | src/addrman.cpp | 10 | ||||
-rw-r--r-- | src/addrman.h | 22 | ||||
-rw-r--r-- | src/netaddress.h | 19 |
3 files changed, 36 insertions, 15 deletions
diff --git a/src/addrman.cpp b/src/addrman.cpp index 14b412a038..b9fee8f627 100644 --- a/src/addrman.cpp +++ b/src/addrman.cpp @@ -12,6 +12,8 @@ #include <cmath> #include <optional> +#include <unordered_map> +#include <unordered_set> int CAddrInfo::GetTriedBucket(const uint256& nKey, const std::vector<bool> &asmap) const { @@ -77,12 +79,12 @@ double CAddrInfo::GetChance(int64_t nNow) const CAddrInfo* CAddrMan::Find(const CNetAddr& addr, int* pnId) { - std::map<CNetAddr, int>::iterator it = mapAddr.find(addr); + const auto it = mapAddr.find(addr); if (it == mapAddr.end()) return nullptr; if (pnId) *pnId = (*it).second; - std::map<int, CAddrInfo>::iterator it2 = mapInfo.find((*it).second); + const auto it2 = mapInfo.find((*it).second); if (it2 != mapInfo.end()) return &(*it2).second; return nullptr; @@ -408,8 +410,8 @@ CAddrInfo CAddrMan::Select_(bool newOnly) #ifdef DEBUG_ADDRMAN int CAddrMan::Check_() { - std::set<int> setTried; - std::map<int, int> mapNew; + std::unordered_set<int> setTried; + std::unordered_map<int, int> mapNew; if (vRandom.size() != (size_t)(nTried + nNew)) return -7; diff --git a/src/addrman.h b/src/addrman.h index 41994288db..4929fd2ecf 100644 --- a/src/addrman.h +++ b/src/addrman.h @@ -8,22 +8,22 @@ #include <clientversion.h> #include <config/bitcoin-config.h> +#include <fs.h> +#include <hash.h> #include <netaddress.h> #include <protocol.h> #include <random.h> +#include <streams.h> #include <sync.h> #include <timedata.h> #include <tinyformat.h> #include <util/system.h> -#include <fs.h> -#include <hash.h> #include <iostream> -#include <map> #include <optional> #include <set> #include <stdint.h> -#include <streams.h> +#include <unordered_map> #include <vector> /** @@ -251,7 +251,7 @@ public: int nUBuckets = ADDRMAN_NEW_BUCKET_COUNT ^ (1 << 30); s << nUBuckets; - std::map<int, int> mapUnkIds; + std::unordered_map<int, int> mapUnkIds; int nIds = 0; for (const auto& entry : mapInfo) { mapUnkIds[entry.first] = nIds; @@ -435,13 +435,13 @@ public: // Prune new entries with refcount 0 (as a result of collisions). int nLostUnk = 0; - for (std::map<int, CAddrInfo>::const_iterator it = mapInfo.begin(); it != mapInfo.end(); ) { + for (auto it = mapInfo.cbegin(); it != mapInfo.cend(); ) { if (it->second.fInTried == false && it->second.nRefCount == 0) { - std::map<int, CAddrInfo>::const_iterator itCopy = it++; + const auto itCopy = it++; Delete(itCopy->first); - nLostUnk++; + ++nLostUnk; } else { - it++; + ++it; } } if (nLost + nLostUnk > 0) { @@ -662,10 +662,10 @@ private: int nIdCount GUARDED_BY(cs); //! table with information about all nIds - std::map<int, CAddrInfo> mapInfo GUARDED_BY(cs); + std::unordered_map<int, CAddrInfo> mapInfo GUARDED_BY(cs); //! find an nId based on its network address - std::map<CNetAddr, int> mapAddr GUARDED_BY(cs); + std::unordered_map<CNetAddr, int, CNetAddrHash> mapAddr GUARDED_BY(cs); //! randomly-ordered vector of all nIds std::vector<int> vRandom GUARDED_BY(cs); diff --git a/src/netaddress.h b/src/netaddress.h index 0d04ab88fb..dd47ab5749 100644 --- a/src/netaddress.h +++ b/src/netaddress.h @@ -11,7 +11,9 @@ #include <attributes.h> #include <compat.h> +#include <crypto/siphash.h> #include <prevector.h> +#include <random.h> #include <serialize.h> #include <tinyformat.h> #include <util/strencodings.h> @@ -251,6 +253,7 @@ class CNetAddr } } + friend class CNetAddrHash; friend class CSubNet; private: @@ -464,6 +467,22 @@ class CNetAddr } }; +class CNetAddrHash +{ +public: + size_t operator()(const CNetAddr& a) const noexcept + { + CSipHasher hasher(m_salt_k0, m_salt_k1); + hasher.Write(a.m_net); + hasher.Write(a.m_addr.data(), a.m_addr.size()); + return static_cast<size_t>(hasher.Finalize()); + } + +private: + const uint64_t m_salt_k0 = GetRand(std::numeric_limits<uint64_t>::max()); + const uint64_t m_salt_k1 = GetRand(std::numeric_limits<uint64_t>::max()); +}; + class CSubNet { protected: |