bench: test select for a new table with only one address

the addrman select function will demonstrate it's worst case performance when
it is almost empty, because it might have to linearly search several buckets.
add a bench test to cover this case

Co-authored-by: Martin Zumsande <mzumsande@gmail.com>

1 files changed, 24 insertions, 0 deletions

diff --git a/src/bench/addrman.cpp b/src/bench/addrman.cpp
index b8c69d0a63..8a5cab443f 100644
--- a/src/bench/addrman.cpp
+++ b/src/bench/addrman.cpp
@@ -79,6 +79,13 @@ static CNetAddr ResolveIP(const std::string& ip)
     return addr;
 }
 
+static CService ResolveService(const std::string& ip, uint16_t port = 0)
+{
+    CService serv;
+    Lookup(ip, serv, port, false);
+    return serv;
+}
+
 /* Benchmarks */
 
 static void AddrManAdd(benchmark::Bench& bench)
@@ -103,6 +110,22 @@ static void AddrManSelect(benchmark::Bench& bench)
     });
 }
 
+// The worst case performance of the Select() function is when there is only
+// one address on the table, because it linearly searches every position of
+// several buckets before identifying the correct bucket
+static void AddrManSelectFromAlmostEmpty(benchmark::Bench& bench)
+{
+    AddrMan addrman{EMPTY_NETGROUPMAN, /*deterministic=*/false, ADDRMAN_CONSISTENCY_CHECK_RATIO};
+
+    // Add one address to the new table
+    CService addr = ResolveService("250.3.1.1", 8333);
+    addrman.Add({CAddress(addr, NODE_NONE)}, ResolveService("250.3.1.1", 8333));
+
+    bench.run([&] {
+        (void)addrman.Select();
+    });
+}
+
 static void AddrManSelectByNetwork(benchmark::Bench& bench)
 {
     AddrMan addrman{EMPTY_NETGROUPMAN, /*deterministic=*/false, ADDRMAN_CONSISTENCY_CHECK_RATIO};
@@ -162,6 +185,7 @@ static void AddrManAddThenGood(benchmark::Bench& bench)
 
 BENCHMARK(AddrManAdd, 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);