Repository: bitcoin/bitcoin
File: src/addrman.cpp (C++)

Code before:
    AddrInfo* pinfo = Find(addr);

    // if not found, bail out
    if (!pinfo)
        return;

    AddrInfo& info = *pinfo;

    // update info
    info.m_last_try = time;
    if (fCountFailure && info.m_last_count_attempt < m_last_good) {
        info.m_last_count_attempt = time;
        info.nAttempts++;
    }
}

std::pair<CAddress, NodeSeconds> AddrManImpl::Select_(bool new_only, std::optional<Network> network) const
{
    AssertLockHeld(cs);

    if (vRandom.empty()) return {};

    size_t new_count = nNew;
    size_t tried_count = nTried;

    if (network.has_value()) {
        auto it = m_network_counts.find(*network);
        if (it == m_network_counts.end()) return {};

        auto counts = it->second;
        new_count = counts.n_new;
        tried_count = counts.n_tried;
    }

    if (new_only && new_count == 0) return {};
    if (new_count + tried_count == 0) return {};

    // Decide if we are going to search the new or tried table
    // If either option is viable, use a 50% chance to choose
    bool search_tried;
    if (new_only || tried_count == 0) {
        search_tried = false;
    } else if (new_count == 0) {
        search_tried = true;
    } else {
        search_tried = insecure_rand.randbool();
    }

    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

Review comment (bug):
I am trying to understand better the performance of this. Posting here to avoid cluttering the PR's main discussion thread.

https://github.com/bitcoin/bitcoin/pull/29436#pullrequestreview-1891096814:
> I tried to test the performance impact on the "normal" case of an addrman that only has addrs for reachable nets:
If I change the AddrManSelect benchmark to use addrman.Select(false, g_reachable_nets.All()); the performance goes down by a factor of ~5 for me

One thing to note here is that the benchmark fills addrman solely with IPv6 addresses. That's not representative. So I borrowed the `peers.dat` from my mainnet node and ran the tests below.

As a start I began from 7edb07ca80 (this PR before the performance related tweaks). My aim was to 1. confirm that there is indeed a performance issue and 2. to understand where exactly it comes from so it can be addressed in the best way. Then I compared with the PR and then I compared with the PR + a change to make the last argument of `Select()` const ref.

addrman size:
```
IPV4: 49123
IPV6: 11071
ONION:15096
I2P:   1863
CJDNS:    2
```

Numbers in ns/op (bigger number => slower).

\ | Baseline (master @ `7edb07ca80~3`) | PR (`7edb07ca80`) | PR (`7edb07ca80`) + const ref argument
 --- | ---: | ---: | ---:
any (empty optional or empty map) | 130  | 140 <sup>A</sup> | 135
IPV4 or {IPV4} | 190 | 320 | 200
IPV6 or {IPV6} | 490 | 640 | 510
ONION or {ONION} | 1200 | 1370 | 1270
I2P or {I2P} | 2500 | 2650 | 2550
CJDNS or {CJDNS} | 1500000 | 1700000 | 1600000
{IPV4, IPV6, ONION, I2P, CJDNS} | - | 550 <sup>B</sup> | 150 <sup>C</sup>

<sup>A</sup> vs <sup>B</sup> is probably what @mzumsande observed in https://github.com/bitcoin/bitcoin/pull/29436#pullrequestreview-1891096814. But fixing the arg changes that to <sup>A</sup> vs <sup>C</sup>.

Based on the above, I think that it is best to go back to `7edb07ca80` and only fix the `Select()` argument.

<details>
<summary>benchmark for Select() to read real peers.dat</summary>

```diff
diff --git a/src/bench/addrman.cpp b/src/bench/addrman.cpp
index f044feebba..dd45b9e69b 100644
--- a/src/bench/addrman.cpp
+++ b/src/bench/addrman.cpp
@@ -1,12 +1,15 @@
 // 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 <common/args.h>
 #include <netbase.h>
 #include <netgroup.h>
 #include <random.h>
 #include <util/check.h>
 #include <util/time.h>
 
@@ -81,12 +84,37 @@ static void AddrManAdd(benchmark::Bench& bench)
     bench.run([&] {
         AddrMan addrman{EMPTY_NETGROUPMAN, /*deterministic=*/false, ADDRMAN_CONSISTENCY_CHECK_RATIO};
         AddAddressesToAddrMan(addrman);
     });
 }
 
+static void AddrManSelectMain(benchmark::Bench& bench)
+{
+    SelectParams(ChainType::MAIN);
+    gArgs.ForceSetArg("checkaddrman", "0");
+    gArgs.ForceSetArg("datadir", "/tmp");
+    auto result = LoadAddrman(EMPTY_NETGROUPMAN, gArgs);
+    AddrMan& addrman = *(*result).get();
+
+    std::cout << "addrman size:\n";
+    std::cout << "IPv4: " << addrman.Size(NET_IPV4) << "\n";
+    std::cout << "IPv6: " << addrman.Size(NET_IPV6) << "\n";
+    std::cout << "Tor:  " << addrman.Size(NET_ONION) << "\n";
+    std::cout << "I2P:  " << addrman.Size(NET_I2P) << "\n";
+    std::cout << "CJDNS:" << addrman.Size(NET_CJDNS) << "\n";
+
+    //const std::optional<Network> n{NET_CJDNS};
+    //const std::unordered_set<Network> n{NET_IPV4, NET_IPV6, NET_ONION, NET_I2P, NET_CJDNS};
+    //const std::unordered_set<Network> n{};
+    //const std::unordered_set<Network> n{g_reachable_nets.All()};
+    bench.run([&] {
+        const auto& address = addrman.Select(/*new_only=*/false, n);
+        assert(address.first.IsValid());
+    });
+}
+
 static void AddrManSelect(benchmark::Bench& bench)
 {
     AddrMan addrman{EMPTY_NETGROUPMAN, /*deterministic=*/false, ADDRMAN_CONSISTENCY_CHECK_RATIO};
 
     FillAddrMan(addrman);
 
@@ -167,11 +195,12 @@ static void AddrManAddThenGood(benchmark::Bench& bench)
 
         markSomeAsGood(addrman);
     });
 }
 
 BENCHMARK(AddrManAdd, benchmark::PriorityLevel::HIGH);
+BENCHMARK(AddrManSelectMain, benchmark::PriorityLevel::HIGH);
 BENCHMARK(AddrManSelect, benchmark::PriorityLevel::HIGH);
 BENCHMARK(AddrManSelectFromAlmostEmpty, benchmark::PriorityLevel::HIGH);
 BENCHMARK(AddrManSelectByNetwork, benchmark::PriorityLevel::HIGH);
 BENCHMARK(AddrManGetAddr, benchmark::PriorityLevel::HIGH);
 BENCHMARK(AddrManAddThenGood, benchmark::PriorityLevel::HIGH);
```
</details>

<details>
<summary>Fix Select() argument</summary>

```diff
diff --git i/src/addrman.cpp w/src/addrman.cpp
index 4e551e81c3..bde2d90ef2 100644
--- i/src/addrman.cpp
+++ w/src/addrman.cpp
@@ -705,13 +705,13 @@ void AddrManImpl::Attempt_(const CService& addr, bool fCountFailure, NodeSeconds
     if (fCountFailure && info.m_last_count_attempt < m_last_good) {
         info.m_last_count_attempt = time;
         info.nAttempts++;
     }
 }
 
-std::pair<CAddress, NodeSeconds> AddrManImpl::Select_(bool new_only, std::unordered_set<Network> networks) const
+std::pair<CAddress, NodeSeconds> AddrManImpl::Select_(bool new_only, const std::unordered_set<Network>& networks) const
 {
     AssertLockHeld(cs);
 
     if (vRandom.empty()) return {};
 
     size_t new_count = nNew;
@@ -1208,13 +1208,13 @@ std::pair<CAddress, NodeSeconds> AddrManImpl::SelectTriedCollision()
     Check();
     auto ret = SelectTriedCollision_();
     Check();
     return ret;
 }
 
-std::pair<CAddress, NodeSeconds> AddrManImpl::Select(bool new_only, std::unordered_set<Network> networks) const
+std::pair<CAddress, NodeSeconds> AddrManImpl::Select(bool new_only, const std::unordered_set<Network>& networks) const
 {
     LOCK(cs);
     Check();
     auto addrRet = Select_(new_only, networks);
     Check();
     return addrRet;
@@ -1315,13 +1315,13 @@ void AddrMan::ResolveCollisions()
 
 std::pair<CAddress, NodeSeconds> AddrMan::SelectTriedCollision()
 {
     return m_impl->SelectTriedCollision();
 }
 
-std::pair<CAddress, NodeSeconds> AddrMan::Select(bool new_only, std::unordered_set<Network> networks) const
+std::pair<CAddress, NodeSeconds> AddrMan::Select(bool new_only, const std::unordered_set<Network>& networks) const
 {
     return m_impl->Select(new_only, networks);
 }
 
 std::vector<CAddress> AddrMan::GetAddr(size_t max_addresses, size_t max_pct, std::optional<Network> network, const bool filtered) const
 {
diff --git i/src/addrman.h w/src/addrman.h
index 2d2846993a..b6fdb07f82 100644
--- i/src/addrman.h
+++ w/src/addrman.h
@@ -157,13 +157,13 @@ public:
      *                     guarantee a tried entry).
      * @param[in] networks Select only addresses of these networks (empty = all). Passing networks may
      *                     slow down the search.
      * @return    CAddress The record for the selected peer.
      *            seconds  The last time we attempted to connect to that peer.
      */
-    std::pair<CAddress, NodeSeconds> Select(bool new_only = false, std::unordered_set<Network> networks = {}) const;
+    std::pair<CAddress, NodeSeconds> Select(bool new_only = false, const std::unordered_set<Network>& networks = {}) const;
 
     /**
      * Return all or many randomly selected addresses, optionally by network.
      *
      * @param[in] max_addresses  Maximum number of addresses to return (0 = all).
      * @param[in] max_pct        Maximum percentage of addresses to return (0 = all).
diff --git i/src/addrman_impl.h w/src/addrman_impl.h
index bb89213bb7..2a4596e81f 100644
--- i/src/addrman_impl.h
+++ w/src/addrman_impl.h
@@ -123,13 +123,13 @@ public:
         EXCLUSIVE_LOCKS_REQUIRED(!cs);
 
     void ResolveCollisions() EXCLUSIVE_LOCKS_REQUIRED(!cs);
 
     std::pair<CAddress, NodeSeconds> SelectTriedCollision() EXCLUSIVE_LOCKS_REQUIRED(!cs);
 
-    std::pair<CAddress, NodeSeconds> Select(bool new_only, std::unordered_set<Network> networks) const
+    std::pair<CAddress, NodeSeconds> Select(bool new_only, const std::unordered_set<Network>& networks) const
         EXCLUSIVE_LOCKS_REQUIRED(!cs);
 
     std::vector<CAddress> GetAddr(size_t max_addresses, size_t max_pct, std::optional<Network> network, const bool filtered = true) const
         EXCLUSIVE_LOCKS_REQUIRED(!cs);
 
     std::vector<std::pair<AddrInfo, AddressPosition>> GetEntries(bool from_tried) const
@@ -250,13 +250,13 @@ private:
     bool Good_(const CService& addr, bool test_before_evict, NodeSeconds time) EXCLUSIVE_LOCKS_REQUIRED(cs);
 
     bool Add_(const std::vector<CAddress>& vAddr, const CNetAddr& source, std::chrono::seconds time_penalty) EXCLUSIVE_LOCKS_REQUIRED(cs);
 
     void Attempt_(const CService& addr, bool fCountFailure, NodeSeconds time) EXCLUSIVE_LOCKS_REQUIRED(cs);
 
-    std::pair<CAddress, NodeSeconds> Select_(bool new_only, std::unordered_set<Network> networks) const EXCLUSIVE_LOCKS_REQUIRED(cs);
+    std::pair<CAddress, NodeSeconds> Select_(bool new_only, const std::unordered_set<Network>& networks) const EXCLUSIVE_LOCKS_REQUIRED(cs);
 
     /** Helper to generalize looking up an addrman entry from either table.
      *
      *  @return  int The nid of the entry. If the addrman position is empty or not found, returns -1.
      * */
     int GetEntry(bool use_tried, size_t bucket, size_t position) const EXCLUSIVE_LOCKS_REQUIRED(cs);
```
</details>

Code after:
    AddrInfo* pinfo = Find(addr);

    // if not found, bail out
    if (!pinfo)
        return;

    AddrInfo& info = *pinfo;

    // update info
    info.m_last_try = time;
    if (fCountFailure && info.m_last_count_attempt < m_last_good) {
        info.m_last_count_attempt = time;
        info.nAttempts++;
    }
}

std::pair<CAddress, NodeSeconds> AddrManImpl::Select_(bool new_only, const std::unordered_set<Network>& networks) const
{
    AssertLockHeld(cs);

    if (vRandom.empty()) return {};

    size_t new_count = nNew;
    size_t tried_count = nTried;

    if (!networks.empty()) {
        new_count = 0;
        tried_count = 0;
        for (auto& network : networks) {
            auto it = m_network_counts.find(network);
            if (it == m_network_counts.end()) {
                continue;
            }
            auto counts = it->second;
            new_count += counts.n_new;
            tried_count += counts.n_tried;
        }
    }

    if (new_only && new_count == 0) return {};
    if (new_count + tried_count == 0) return {};

    // Decide if we are going to search the new or tried table
    // If either option is viable, use a 50% chance to choose
    bool search_tried;
    if (new_only || tried_count == 0) {
        search_tried = false;
    } else if (new_count == 0) {
        search_tried = true;
    } else {
        search_tried = insecure_rand.randbool();