I ran this on a mainnet peers.dat:
addrman size total: 72947
addrman size IPv4: 47252
addrman size IPv6: 11491
addrman size Tor: 13305
addrman size I2P: 893
addrman size CJDNS: 6
<details>
<summary>[patch] How to load /tmp/peers.dat from bench_bitcoin</summary>
diff --git i/src/bench/addrman.cpp w/src/bench/addrman.cpp
index 8a5cab443f..b8ec4a4071 100644
--- i/src/bench/addrman.cpp
+++ w/src/bench/addrman.cpp
@@ -1,17 +1,22 @@
// Copyright (c) 2020-2022 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+#include <addrdb.h>
#include <addrman.h>
#include <bench/bench.h>
+#include <chainparams.h>
+#include <chainparamsbase.h>
#include <netbase.h>
#include <netgroup.h>
#include <random.h>
#include <util/check.h>
+#include <util/system.h>
#include <util/time.h>
+#include <util/translation.h>
#include <optional>
#include <vector>
/* A "source" is a source address from which we have received a bunch of other addresses. */
@@ -21,12 +26,23 @@ static constexpr size_t NUM_ADDRESSES_PER_SOURCE = 256;
static NetGroupManager EMPTY_NETGROUPMAN{std::vector<bool>()};
static constexpr uint32_t ADDRMAN_CONSISTENCY_CHECK_RATIO{0};
static std::vector<CAddress> g_sources;
static std::vector<std::vector<CAddress>> g_addresses;
+std::unique_ptr<AddrMan> LoadAddrmanFromPeersDat()
+{
+ SelectBaseParams("main");
+ SelectParams("main");
+ gArgs.ForceSetArg("-datadir", "/tmp");
+ std::unique_ptr<AddrMan> addrman;
+ auto err = LoadAddrman(EMPTY_NETGROUPMAN, gArgs, addrman);
+ assert(!err.has_value());
+ return addrman;
+}
+
static void CreateAddresses()
{
if (g_sources.size() > 0) { // already created
return;
}
@@ -69,19 +85,12 @@ static void FillAddrMan(AddrMan& addrman)
{
CreateAddresses();
AddAddressesToAddrMan(addrman);
}
-static CNetAddr ResolveIP(const std::string& ip)
-{
- CNetAddr addr;
- LookupHost(ip, addr, false);
- return addr;
-}
-
static CService ResolveService(const std::string& ip, uint16_t port = 0)
{
CService serv;
Lookup(ip, serv, port, false);
return serv;
}
@@ -125,26 +134,24 @@ static void AddrManSelectFromAlmostEmpty(benchmark::Bench& bench)
(void)addrman.Select();
});
}
static void AddrManSelectByNetwork(benchmark::Bench& bench)
{
- AddrMan addrman{EMPTY_NETGROUPMAN, /*deterministic=*/false, ADDRMAN_CONSISTENCY_CHECK_RATIO};
-
- // add single I2P address to new table
- CService i2p_service;
- i2p_service.SetSpecial("udhdrtrcetjm5sxzskjyr5ztpeszydbh4dpl3pl4utgqqw2v4jna.b32.i2p");
- CAddress i2p_address(i2p_service, NODE_NONE);
- i2p_address.nTime = Now<NodeSeconds>();
- CNetAddr source = ResolveIP("252.2.2.2");
- addrman.Add({i2p_address}, source);
-
- FillAddrMan(addrman);
+ auto addrman = LoadAddrmanFromPeersDat();
+ std::cout << "addrman size total: " << addrman->Size() << std::endl
+ << "addrman size IPv4: " << addrman->Size(NET_IPV4) << std::endl
+ << "addrman size IPv6: " << addrman->Size(NET_IPV6) << std::endl
+ << "addrman size Tor: " << addrman->Size(NET_ONION) << std::endl
+ << "addrman size I2P: " << addrman->Size(NET_I2P) << std::endl
+ << "addrman size CJDNS: " << addrman->Size(NET_CJDNS) << std::endl;
bench.run([&] {
- (void)addrman.Select(/*new_only=*/false, NET_I2P);
+ //addrman->Select(/*new_only=*/false);
+ //addrman->Select(/*new_only=*/false, NET_I2P);
+ addrman->Select(/*new_only=*/false, NET_CJDNS);
});
}
static void AddrManGetAddr(benchmark::Bench& bench)
{
AddrMan addrman{EMPTY_NETGROUPMAN, /*deterministic=*/false, ADDRMAN_CONSISTENCY_CHECK_RATIO};
</details>
Results:
Select(/*new_only=*/false): 0.265 microseconds, this is what master is doing before this PR
After this PR:
Select(/*new_only=*/false, NET_IPV4): 0.5 microsecondsSelect(/*new_only=*/false, NET_IPV6): 1.7 microsecondsSelect(/*new_only=*/false, NET_ONION): 3.1 microsecondsSelect(/*new_only=*/false, NET_I2P): 27 microsecondsSelect(/*new_only=*/false, NET_CJDNS): 1600 microseconds
Is this slowdown acceptable? Maybe yes. We don't call Select in a tight loop, so maybe even the 1600 microseconds is ok.
What happens if we mark and subsequently skip buckets we have seen to contain 0 interesting addresses, without the shuffling? I guess that should bring most of the improvement from the above patch without the downside of the shuffling. Here is the change on top of this PR:
<details>
<summary>[patch] Skip boring</summary>
diff --git i/src/addrman.cpp w/src/addrman.cpp
index cdfd079fcd..46f4de99be 100644
--- i/src/addrman.cpp
+++ w/src/addrman.cpp
@@ -747,15 +747,19 @@ std::pair<CAddress, NodeSeconds> AddrManImpl::Select_(bool new_only, std::option
}
const int bucket_count{search_tried ? ADDRMAN_TRIED_BUCKET_COUNT : ADDRMAN_NEW_BUCKET_COUNT};
// Loop through the addrman table until we find an appropriate entry
double chance_factor = 1.0;
+ std::unordered_set<int> already_visited_and_boring_buckets;
while (1) {
// Pick a bucket, and an initial position in that bucket.
int bucket = insecure_rand.randrange(bucket_count);
+ if (already_visited_and_boring_buckets.count(bucket) > 0) {
+ continue;
+ }
int initial_position = insecure_rand.randrange(ADDRMAN_BUCKET_SIZE);
// Iterate over the positions of that bucket, starting at the initial one,
// and looping around.
int i;
for (i = 0; i < ADDRMAN_BUCKET_SIZE; ++i) {
@@ -770,14 +774,19 @@ std::pair<CAddress, NodeSeconds> AddrManImpl::Select_(bool new_only, std::option
} else {
break;
}
}
}
- // If the bucket is entirely empty, start over with a (likely) different one.
- if (i == ADDRMAN_BUCKET_SIZE) continue;
+ // Start over with a different bucket if this one is entirely empty or
+ // specific network was requested and it does not contain any addresses
+ // from that network.
+ if (i == ADDRMAN_BUCKET_SIZE) {
+ already_visited_and_boring_buckets.insert(bucket);
+ continue;
+ }
// Find the entry to return.
int position = (initial_position + i) % ADDRMAN_BUCKET_SIZE;
int nId = GetEntry(search_tried, bucket, position);
const auto it_found{mapInfo.find(nId)};
assert(it_found != mapInfo.end());
</details>
Result for NET_CJDNS where the slowdown is most pronounced: 1200 microseconds (vs 1600). Those numbers are averaged over many runs and they do not tell the whole story. Here are the distributions without "skip boring" (the height of a bar indicates how many addresses were checked before finding the result, e.g. if the bar that spans between 2500 and 3500 is tall 280, it means 280 of the runs checked 2500-3500 addresses before finding the result).
with "skip boring":
