p2p, refactor: performance improvements to ProtectEvictionCandidatesByRatio() #22284

pull jonatack wants to merge 5 commits into bitcoin:master from jonatack:ProtectEvictionCandidatesByRatio-perf-enhancements changing 6 files +194 −27
  1. jonatack commented at 4:59 pm on June 19, 2021: member

    This follow-up to #21261 improves ProtectEvictionCandidatesByRatio() for better performance.

    Benchmarks are added; the performance improvement is between 2x and 5x for the benchmarked cases (CPU 2.50GHz, Turbo off, performance mode, Debian Clang 11 non-debug build).

    0$ ./src/bench/bench_bitcoin -filter="EvictionProtection*.*"

    The refactored code is well-covered by existing unit tests and also a fuzzer.

    • $ ./src/test/test_bitcoin -t net_peer_eviction_tests
    • $ FUZZ=node_eviction ./src/test/fuzz/fuzz ../qa-assets/fuzz_seed_corpus/node_eviction
  2. DrahtBot added the label P2P on Jun 19, 2021
  3. jonatack force-pushed on Jun 19, 2021
  4. jonatack force-pushed on Jun 19, 2021
  5. jonatack force-pushed on Jun 20, 2021
  6. jonatack commented at 2:39 pm on June 20, 2021: member

    Added benchmarks. This pull speeds up ProtectEvictionCandidatesByRatio() between 2x and 6x for the benchmarked cases. It’s not a hotspot, but the improvement is significant.

    0$ ./src/bench/bench_bitcoin -filter=EvictionProtection*.*

    master

    0|               ns/op |                op/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|    5,403,043,444.00 |                0.19 |    1.8% |     59.74 | `EvictionProtection1Network250Candidates`
3|    2,946,547,379.00 |                0.34 |    2.7% |     33.45 | `EvictionProtection3Networks050Candidates`
4|    2,798,691,071.00 |                0.36 |    2.2% |     30.79 | `EvictionProtection3Networks100Candidates`
5|    7,288,364,370.00 |                0.14 |    0.7% |     80.16 | `EvictionProtection3Networks250Candidates`

    this PR

    0|               ns/op |                op/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|    1,183,198,205.00 |                0.85 |    1.2% |     13.12 | `EvictionProtection1Network250Candidates`
3|    1,151,709,186.00 |                0.87 |    1.7% |     12.67 | `EvictionProtection3Networks050Candidates`
4|    1,261,170,266.00 |                0.79 |    2.9% |     14.26 | `EvictionProtection3Networks100Candidates`
5|    1,157,625,808.00 |                0.86 |    1.0% |     12.95 | `EvictionProtection3Networks250Candidates`

    (intermediate commits)

    p2p: iterate over eviction candidates once instead of thrice

    0|               ns/op |                op/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|    3,952,529,089.00 |                0.25 |    1.8% |     43.47 | `EvictionProtection1Network250Candidates`
3|    2,239,435,919.00 |                0.45 |    3.8% |     25.85 | `EvictionProtection3Networks050Candidates`
4|    2,060,389,113.00 |                0.49 |    1.9% |     22.85 | `EvictionProtection3Networks100Candidates`
5|    5,258,681,959.00 |                0.19 |    1.0% |     58.26 | `EvictionProtection3Networks250Candidates`

    p2p: iterate eviction protection only on networks having candidates

    0|               ns/op |                op/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|    1,224,597,989.00 |                0.82 |    2.2% |     13.60 | `EvictionProtection1Network250Candidates`
  7. klementtan commented at 3:18 pm on June 20, 2021: contributor

    Tested on macOs 11.4 and this PR indeed optimize it by 1.3x to 5x.

    On 272f327fbfcb8bb61f8e1c9d65c665372cd60976(master with benchmarks):

    0|               ns/op |                op/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|      756,331,588.00 |                1.32 |    1.2% |      8.38 | `EvictionProtection1Network250Candidates`
3|    1,579,971,776.00 |                0.63 |    1.1% |     17.45 | `EvictionProtection3Networks050Candidates`
4|    1,395,431,168.00 |                0.72 |    1.0% |     15.70 | `EvictionProtection3Networks100Candidates`
5|    3,716,091,921.00 |                0.27 |    1.0% |     41.32 | `EvictionProtection3Networks250Candidates`

    This PR:

    0|               ns/op |                op/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|      492,425,456.00 |                2.03 |    0.9% |      5.45 | `EvictionProtection1Network250Candidates`
3|      739,073,603.00 |                1.35 |    1.3% |      8.13 | `EvictionProtection3Networks050Candidates`
4|      937,281,186.00 |                1.07 |    0.7% |     10.38 | `EvictionProtection3Networks100Candidates`
5|      828,820,224.00 |                1.21 |    1.6% |      9.10 | `EvictionProtection3Networks250Candidates`

    Not sure if it is an issue on my side but I had to test with ./src/bench/bench_bitcoin -filter="EvictionProtection*.*"(quotes around regex) instead of the command provided by the PR description.

  8. DrahtBot commented at 5:24 pm on June 20, 2021: member

    The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

    Conflicts

    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.

  9. jarolrod commented at 9:39 pm on June 21, 2021: member

    ACK ab2993336fbdff72d125f906c2baec4c5dcb79e3

    This is quite a performance improvement and is a clear change which is easy to follow. My benchmark tests confirm the performance improvement. Thanks for working on this improvement and for adding additional benchmark coverage.

    Ran benchmarks upon each intermediate commit to test performance improvement at every stage. Cherry-picked each commit on top of current master and ran unit tests which each commit cherry-picked.

    Master

    0|               ns/op |                op/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|    2,283,211,027.00 |                0.44 |    0.1% |     25.13 | `EvictionProtection1Network250Candidates`
3|    1,417,424,933.00 |                0.71 |    0.1% |     15.59 | `EvictionProtection3Networks050Candidates`
4|    1,293,719,559.00 |                0.77 |    0.1% |     14.25 | `EvictionProtection3Networks100Candidates`
5|    3,350,000,724.00 |                0.30 |    0.1% |     36.88 | `EvictionProtection3Networks250Candidates`

    PR

    0|               ns/op |                op/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|      778,011,162.00 |                1.29 |    0.3% |      8.56 | `EvictionProtection1Network250Candidates`
3|      811,555,934.00 |                1.23 |    0.1% |      8.93 | `EvictionProtection3Networks050Candidates`
4|      806,194,432.00 |                1.24 |    0.1% |      8.87 | `EvictionProtection3Networks100Candidates`
5|      776,191,251.00 |                1.29 |    0.1% |      8.54 | `EvictionProtection3Networks250Candidates`

    Notes on commits

    • 272f327fbfcb8bb61f8e1c9d65c665372cd60976
      • Definition of test is appropriate and effective in terms of benchmarking what we care about
    • 99a25fb393c791bb6b6edeab3677d39bf6b1d97d
      • the performance boost is from moving away from looping through each network and then interating through all eviction_candidates -> iterate through eviction_candidates once; for each candidate we iterate through add count to appropriate network
      • Still appropriately counts eviction candidates per network
      • Performance improvement at this stage is very modest compared to master+272f327fbfcb8bb61f8e1c9d65c665372cd60976
    • 06b898c3e126ff7f1a17d8d3a5f7c9e1aad0ea06
      • uses lambda expression in std::count_if to efficiently determine networks we have candidates from
      • PR description states that “… increase the number protected per peer iteration”, this would only come into play if there was a descrease in the number of networks to protect because we detected there were no candidates in that network. If you have to retouch, can you document this more clearly?
      • this and 99a25fb393c791bb6b6edeab3677d39bf6b1d97d make up the bulk of the performance improvement
    • 478534340e9b30f4e906da290e3b763dec6c945c
      • makes sense 🥃
    • ab2993336fbdff72d125f906c2baec4c5dcb79e3
      • Is an additional performance improvement
  10. theStack commented at 4:22 pm on June 22, 2021: member
    Concept ACK
  11. in src/bench/peer_eviction.cpp:36 in ab2993336f outdated 
    31+            /* m_is_local */ random_context.randbool(),
32+            /* m_network */ ALL_NETWORKS[random_context.randrange(ALL_NETWORKS.size())],
33+        });
34+    }
35+    return candidates;
36+}
    vasild commented at 9:09 am on June 30, 2021:

    This function already exists in src/test/net_peer_eviction_tests.cpp. Dedup:

     0    test: make GetRandomNodeEvictionCandidates() reusable
 1
 2    Move `GetRandomNodeEvictionCandidates()` from
 3    `src/test/net_peer_eviction_tests.cpp` to `src/test/util/net.h` and
 4    `src/test/util/net.cpp` so that it can be reused by other tests.
 5
 6diff --git a/src/test/net_peer_eviction_tests.cpp b/src/test/net_peer_eviction_tests.cpp
 7index 4bfd487b86..5eb280b498 100644
 8--- a/src/test/net_peer_eviction_tests.cpp
 9+++ b/src/test/net_peer_eviction_tests.cpp
10@@ -14,34 +14,12 @@
11 #include <optional>
12 #include <unordered_set>
13 #include <vector>
14
15 BOOST_FIXTURE_TEST_SUITE(net_peer_eviction_tests, BasicTestingSetup)
16
17-std::vector<NodeEvictionCandidate> GetRandomNodeEvictionCandidates(const int n_candidates, FastRandomContext& random_context)
18-{
19-    std::vector<NodeEvictionCandidate> candidates;
20-    for (int id = 0; id < n_candidates; ++id) {
21-        candidates.push_back({
22-            /* id */ id,
23-            /* nTimeConnected */ static_cast<int64_t>(random_context.randrange(100)),
24-            /* m_min_ping_time */ std::chrono::microseconds{random_context.randrange(100)},
25-            /* nLastBlockTime */ static_cast<int64_t>(random_context.randrange(100)),
26-            /* nLastTXTime */ static_cast<int64_t>(random_context.randrange(100)),
27-            /* fRelevantServices */ random_context.randbool(),
28-            /* fRelayTxes */ random_context.randbool(),
29-            /* fBloomFilter */ random_context.randbool(),
30-            /* nKeyedNetGroup */ random_context.randrange(100),
31-            /* prefer_evict */ random_context.randbool(),
32-            /* m_is_local */ random_context.randbool(),
33-            /* m_network */ ALL_NETWORKS[random_context.randrange(ALL_NETWORKS.size())],
34-        });
35-    }
36-    return candidates;
37-}
38-
39 // Create `num_peers` random nodes, apply setup function `candidate_setup_fn`,
40 // call ProtectEvictionCandidatesByRatio() to apply protection logic, and then
41 // return true if all of `protected_peer_ids` and none of `unprotected_peer_ids`
42 // are protected from eviction, i.e. removed from the eviction candidates.
43 bool IsProtected(int num_peers,
44                  std::function<void(NodeEvictionCandidate&)> candidate_setup_fn,
45diff --git a/src/test/util/net.cpp b/src/test/util/net.cpp
46index 847a490e03..64b70a61f0 100644
47--- a/src/test/util/net.cpp
48+++ b/src/test/util/net.cpp
49@@ -34,6 +34,28 @@ bool ConnmanTestMsg::ReceiveMsgFrom(CNode& node, CSerializedNetMsg& ser_msg) con
50
51     bool complete;
52     NodeReceiveMsgBytes(node, ser_msg_header, complete);
53     NodeReceiveMsgBytes(node, ser_msg.data, complete);
54     return complete;
55 }
56+
57+std::vector<NodeEvictionCandidate> GetRandomNodeEvictionCandidates(const int n_candidates, FastRandomContext& random_context)
58+{
59+    std::vector<NodeEvictionCandidate> candidates;
60+    for (int id = 0; id < n_candidates; ++id) {
61+        candidates.push_back({
62+            /* id */ id,
63+            /* nTimeConnected */ static_cast<int64_t>(random_context.randrange(100)),
64+            /* m_min_ping_time */ std::chrono::microseconds{random_context.randrange(100)},
65+            /* nLastBlockTime */ static_cast<int64_t>(random_context.randrange(100)),
66+            /* nLastTXTime */ static_cast<int64_t>(random_context.randrange(100)),
67+            /* fRelevantServices */ random_context.randbool(),
68+            /* fRelayTxes */ random_context.randbool(),
69+            /* fBloomFilter */ random_context.randbool(),
70+            /* nKeyedNetGroup */ random_context.randrange(100),
71+            /* prefer_evict */ random_context.randbool(),
72+            /* m_is_local */ random_context.randbool(),
73+            /* m_network */ ALL_NETWORKS[random_context.randrange(ALL_NETWORKS.size())],
74+        });
75+    }
76+    return candidates;
77+}
78diff --git a/src/test/util/net.h b/src/test/util/net.h
79index 1b49a671bd..66f6cc61b8 100644
80--- a/src/test/util/net.h
81+++ b/src/test/util/net.h
82@@ -138,7 +138,9 @@ public:
83
84 private:
85     const std::string m_contents;
86     mutable size_t m_consumed;
87 };
88
89+std::vector<NodeEvictionCandidate> GetRandomNodeEvictionCandidates(const int n_candidates, FastRandomContext& random_context);
90+
91 #endif // BITCOIN_TEST_UTIL_NET_H
    jonatack commented at 1:13 pm on July 1, 2021:
    Done (thanks!)
  12. in src/bench/peer_eviction.cpp:73 in ab2993336f outdated 
    68+        std::vector<NodeEvictionCandidate> candidates;
69+        for (int id = 0; id < 60000; ++id) {
70+            candidates = eviction_candidates;
71+            ProtectEvictionCandidatesByRatio(candidates);
72+        }
73+    });
    vasild commented at 9:23 am on June 30, 2021:

    I think nanobench is designed to make such loops unnecessary. It can provide stable results even if the test function is very fast/short, no need to loop 60k times.

    Also, the above benchmarks the copying of the data which could add noise to the test. Given that the input is not huge we can create a separate copy for each iteration of the test, this consumes a few tens of megabytes which is ok. Here is an example (that also uses the de-duplicated GetRandomNodeEvictionCandidates() from test/util/net.h):

      0// Copyright (c) 2021 The Bitcoin Core developers
  1// Distributed under the MIT software license, see the accompanying
  2// file COPYING or http://www.opensource.org/licenses/mit-license.php.
  3
  4#include <bench/bench.h>
  5#include <net.h>
  6#include <netaddress.h>
  7#include <random.h>
  8#include <test/util/net.h>
  9#include <test/util/setup_common.h>
 10
 11#include <algorithm>
 12#include <functional>
 13#include <vector>
 14
 15static void EvictionProtectionCommon(
 16    benchmark::Bench& bench,
 17    int num_candidates,
 18    std::function<void(NodeEvictionCandidate&)> candidate_setup_fn,
 19    size_t epochs,
 20    uint64_t epoch_iterations)
 21{
 22    using Candidates = std::vector<NodeEvictionCandidate>;
 23
 24    FastRandomContext random_context{true};
 25
 26    bench.epochs(epochs).epochIterations(epoch_iterations);
 27
 28    Candidates candidates{GetRandomNodeEvictionCandidates(num_candidates, random_context)};
 29    for (auto& c : candidates) {
 30        candidate_setup_fn(c);
 31    }
 32
 33    std::vector<Candidates> copies{bench.epochs() * bench.epochIterations(), candidates};
 34    size_t i{0};
 35    bench.run([&] {
 36        ProtectEvictionCandidatesByRatio(copies.at(i));
 37        ++i;
 38    });
 39}
 40
 41/* Benchmarks */
 42
 43static void EvictionProtection1Network250Candidates(benchmark::Bench& bench)
 44{
 45    EvictionProtectionCommon(
 46        bench,
 47        250 /* num_candidates */,
 48        [](NodeEvictionCandidate& c) {
 49            c.nTimeConnected = c.id;
 50            c.m_is_local = false;
 51            if (c.id >= 130 && c.id < 240) { // 110 Tor
 52                c.m_network = NET_ONION;
 53            } else {
 54                c.m_network = NET_IPV6;
 55            }
 56        },
 57        10 /* epochs */,
 58        100 /* epoch_iterations */);
 59}
 60
 61static void EvictionProtection3Networks050Candidates(benchmark::Bench& bench)
 62{
 63    EvictionProtectionCommon(
 64        bench,
 65        50 /* num_candidates */,
 66        [](NodeEvictionCandidate& c) {
 67            c.nTimeConnected = c.id;
 68            c.m_is_local = (c.id == 28 || c.id == 47); //  2 localhost
 69            if (c.id >= 30 && c.id < 47) {             // 17 I2P
 70                c.m_network = NET_I2P;
 71            } else if (c.id >= 24 && c.id < 28) { //  4 Tor
 72                c.m_network = NET_ONION;
 73            } else {
 74                c.m_network = NET_IPV4;
 75            }
 76        },
 77        10 /* epochs */,
 78        100 /* epoch_iterations */);
 79}
 80
 81static void EvictionProtection3Networks100Candidates(benchmark::Bench& bench)
 82{
 83    EvictionProtectionCommon(
 84        bench,
 85        100 /* num_candidates */,
 86        [](NodeEvictionCandidate& c) {
 87            c.nTimeConnected = c.id;
 88            c.m_is_local = (c.id >= 55 && c.id < 60); //  5 localhost
 89            if (c.id >= 70 && c.id < 80) {            // 10 I2P
 90                c.m_network = NET_I2P;
 91            } else if (c.id >= 80 && c.id < 96) { // 16 Tor
 92                c.m_network = NET_ONION;
 93            } else {
 94                c.m_network = NET_IPV4;
 95            }
 96        },
 97        10 /* epochs */,
 98        100 /* epoch_iterations */);
 99}
100
101static void EvictionProtection3Networks250Candidates(benchmark::Bench& bench)
102{
103    EvictionProtectionCommon(
104        bench,
105        250 /* num_candidates */,
106        [](NodeEvictionCandidate& c) {
107            c.nTimeConnected = c.id;
108            c.m_is_local = (c.id >= 140 && c.id < 160); // 20 localhost
109            if (c.id >= 170 && c.id < 180) {            // 10 I2P
110                c.m_network = NET_I2P;
111            } else if (c.id >= 190 && c.id < 240) { // 50 Tor
112                c.m_network = NET_ONION;
113            } else {
114                c.m_network = NET_IPV4;
115            }
116        },
117        10 /* epochs */,
118        100 /* epoch_iterations */);
119}
120
121// 1 disadvantaged network (Tor) with 250 eviction candidates.
122BENCHMARK(EvictionProtection1Network250Candidates);
123
124// 3 disadvantaged networks (I2P/localhost/Tor) with 50/100/250 eviction candidates.
125BENCHMARK(EvictionProtection3Networks050Candidates);
126BENCHMARK(EvictionProtection3Networks100Candidates);
127BENCHMARK(EvictionProtection3Networks250Candidates);
    jonatack commented at 1:21 pm on July 1, 2021:

    I tried this, and am playing with your proposal that looks good! but as before when I was trying to use these options, nanobench kept saying it was unstable and to increase the iterations, beyond even the numbers I settled on in my manual loops that yielded slowish but stableish results for me.

    0:wavy_dash: ... (Unstable with ~1,000.0 iters. Increase `minEpochIterations` to e.g. 10000)
1:wavy_dash: ... (Unstable with ~1,000.0 iters. Increase `minEpochIterations` to e.g. 10000)

    So I’m still looking at this and may punt on using the options.

    Yes, I benched the data copying alone, and it seemed insignificant relative to the call under test, not worth messing with by making (potentially many, e.g. 100k) copies instead. That could be ok if we don’t need so many copies, so I understand why you proposed reducing the number of iters.

    vasild commented at 4:18 pm on July 1, 2021:

    Here are some numbers:

    • sizeof(NodeEvictionCandidate) is 64
    • number of candidates is 250
    • the current test contains 60k iterations

    So that would make 64 * 250 * 60000 = 916 MiB.

    In the changes above I suggested 10 epochs * 100 iterations (1000 copies): 64 * 250 * 1000 = 15 MiB.

    so I understand why you proposed reducing the number of iters

    Yes, I was concerned about the memory usage, but also I stopped getting the “unstable results” warning at around 500 iters so I decided to double it to 1000 just in case, since 15 MiB is not too much. I guess a few times more than that would also be ok.

    vasild commented at 12:18 pm on July 5, 2021:

    Two random thoughts:

    1. Do you get “unstable results” warnings when running other benchmarks from src/bench?
    2. Nanobench’s warmup() may help?
    jonatack commented at 3:37 pm on July 6, 2021:

    I’ve tuned my system for benchmarking, and nevertheless, any iterations less than in my original proposal still return bench error rates above 5%, often 10-25%, rendering the benchmark somewhat useless for me.

    I’m going to consider that my system (2 physical cores, 4 logical ones, with an open source coreboot) is unusual and unsuited to running these benchmarks and use this feedback provided that reviewers find the results stable for them.

  13. in src/net.cpp:929 in ab2993336f outdated 
    931+            if (networks[i].is_local ? c.m_is_local : c.m_network == networks[i].id) {
932+                ++networks[i].count;
933+                break;
934+            }
935+        }
936     }
    vasild commented at 9:34 am on June 30, 2021:

    99a25fb393 p2p: iterate over eviction candidates once instead of thrice

    I did not observe any difference in performance due to this commit.

    It changes the complexity from O(num networks * num candidates) to O(num candidates * num networks). The early break optimization maybe makes it O(num candidates * num networks * 0.5) on average, but that is equal to O(num candidates * num networks).

    Just to experiment I made this O(num candidates) which is as fast as it could be (unfortunately a bit hackish due to the hardcoded indexes):

     0--- a/src/net.cpp
 1+++ b/src/net.cpp
 2@@ -918,18 +918,26 @@ void ProtectEvictionCandidatesByRatio(std::vector<NodeEvictionCandidate>& evicti
 3     // array members have first opportunity to recover unused slots from the previous iteration.
 4     struct Net { bool is_local; Network id; size_t count; };
 5     std::array<Net, 3> networks{
 6         {{false, NET_I2P, 0}, {/* localhost */ true, NET_MAX, 0}, {false, NET_ONION, 0}}};
 7 
 8     // Count and store the number of eviction candidates per network.
 9-    for (auto& c : eviction_candidates) {
10-        for (int i{networks.size() - 1}; i >= 0; --i) {
11-            if (networks[i].is_local ? c.m_is_local : c.m_network == networks[i].id) {
12-                ++networks[i].count;
13-                break;
14-            }
15+    for (const auto& c : eviction_candidates) {
16+        const Network net = c.m_is_local ? NET_MAX : c.m_network;
17+        switch (net) {
18+        case NET_I2P:
19+            ++networks[0].count;
20+            break;
21+        case NET_MAX:
22+            ++networks[1].count;
23+            break;
24+        case NET_ONION:
25+            ++networks[2].count;
26+            break;
27+        default:
28+            break;
29         }
30     }
31     // Sort `networks` by ascending candidate count, to give networks having fewer candidates
32     // the first opportunity to recover unused protected slots from the previous iteration.

    No difference in performance either. I guess this is operating on too small amount of data to make any performance impact and so this commit can be dropped if its purpose is to improve performance and we can’t observe any changes.

    vasild commented at 10:44 am on June 30, 2021:

    I did not observe any difference in performance due to this commit.

    Here are the results I get:

    272f327fbf bench: add peer eviction protection benchmarks

     0|               ns/op |                op/s |    err% |     total | benchmark
 1|--------------------:|--------------------:|--------:|----------:|:----------
 2|      706,673,971.00 |                1.42 |    1.7% |      7.79 | `EvictionProtection1Network250Candidates`
 3|    1,299,063,388.00 |                0.77 |    0.7% |     14.30 | `EvictionProtection3Networks050Candidates`
 4|    1,155,171,747.00 |                0.87 |    0.5% |     12.73 | `EvictionProtection3Networks100Candidates`
 5|    2,900,919,398.00 |                0.34 |    1.3% |     31.93 | `EvictionProtection3Networks250Candidates`
 6
 7|               ns/op |                op/s |    err% |     total | benchmark
 8|--------------------:|--------------------:|--------:|----------:|:----------
 9|      714,684,192.00 |                1.40 |    1.0% |      7.91 | `EvictionProtection1Network250Candidates`
10|    1,296,579,234.00 |                0.77 |    0.5% |     14.22 | `EvictionProtection3Networks050Candidates`
11|    1,159,393,440.00 |                0.86 |    0.7% |     12.71 | `EvictionProtection3Networks100Candidates`
12|    2,854,527,930.00 |                0.35 |    0.7% |     31.44 | `EvictionProtection3Networks250Candidates`

    99a25fb393 p2p: iterate over eviction candidates once instead of thrice

     0|               ns/op |                op/s |    err% |     total | benchmark
 1|--------------------:|--------------------:|--------:|----------:|:----------
 2|      709,622,212.00 |                1.41 |    1.0% |      7.79 | `EvictionProtection1Network250Candidates`
 3|    1,310,376,054.00 |                0.76 |    1.2% |     14.39 | `EvictionProtection3Networks050Candidates`
 4|    1,160,800,660.00 |                0.86 |    0.4% |     12.72 | `EvictionProtection3Networks100Candidates`
 5|    2,983,258,845.00 |                0.34 |    0.5% |     32.71 | `EvictionProtection3Networks250Candidates`
 6
 7|               ns/op |                op/s |    err% |     total | benchmark
 8|--------------------:|--------------------:|--------:|----------:|:----------
 9|      711,091,374.00 |                1.41 |    0.5% |      7.82 | `EvictionProtection1Network250Candidates`
10|    1,318,781,548.00 |                0.76 |    0.3% |     14.38 | `EvictionProtection3Networks050Candidates`
11|    1,142,837,118.00 |                0.88 |    0.2% |     12.40 | `EvictionProtection3Networks100Candidates`
12|    2,943,154,182.00 |                0.34 |    0.4% |     32.22 | `EvictionProtection3Networks250Candidates`
    jonatack commented at 1:27 pm on July 1, 2021:
    99a25fb393c791bb6b6edeab3677d39bf6b1d97d I agree that it’s probably not worth it.
    jonatack commented at 3:35 pm on July 6, 2021:
    Dropped.
  14. in src/net.cpp:943 in ab2993336f outdated 
    937@@ -936,27 +938,34 @@ void ProtectEvictionCandidatesByRatio(std::vector<NodeEvictionCandidate>& evicti
938     size_t num_protected{0};
939 
940     while (num_protected < max_protect_by_network) {
941+        // Count the number of disadvantaged networks from which we have peers to protect.
942+        auto num_networks = std::count_if(networks.begin(), networks.end(), [](const Net& n) { return n.count; });
943+        if (num_networks == 0) {
944+            break;
945+        }
    vasild commented at 9:46 am on June 30, 2021:

    06b898c3e1 p2p: iterate eviction protection only on networks having candidates

    Looking at this commit - there is no need to re-calculate num_networks inside the loop because networks is not changed in the loop. It can be calculated just once before the loop:

    0auto num_networks = std::count_if(networks.begin(), networks.end(), [](const Net& n) { return n.count; });
1if (networks > 0) {
2    while (num_protected < max_protect_by_network) {
3        ...

    I did not observe any performance change due to this commit.

    But considering the subsequent ab2993336f p2p: earlier continuation when no remaining eviction candidates (this one brings pefromance boost!) it should be inside the loop because then we change networks[].count in the loop. Maybe squash both commits into one?

    jonatack commented at 3:35 pm on July 6, 2021:
    Reorganized to be step by step, with no anticipatory changes.
  15. fanquake referenced this in commit c609e10545 on Jul 5, 2021
  16. refactor: move GetRandomNodeEvictionCandidates() to test utilities 
    Co-authored-by: Vasil Dimov <vd@FreeBSD.org>
    566357f8f7
  17. jonatack force-pushed on Jul 6, 2021
  18. jonatack commented at 4:46 pm on July 6, 2021: member
    Thank you @vasild, @jarolrod, @klementtan and @theStack; feedback taken (and rebased, apologies).
  19. klementtan commented at 1:41 am on July 7, 2021: contributor

    Tested on 524aa5dc6a6f20f2fd16a63bd1356d577794d510

    • Didn’t notice any significant improvement with c0d658f1806a81ae5bf20355861979eb7f7ea1f4
    • d2bb6231aaa798590b85700e03dac79f32204aec reduced time for EvictionProtection1Network250Candidates by about 40%
    • Didn’t notice any significant improvement with edc59d08fc57f5f10657a044224a0b3ae2d2b9bc
    • 524aa5dc6a6f20f2fd16a63bd1356d577794d510 reduced time for EvictionProtection3Networks050Candidates by about 50%, EvictionProtection3Networks100Candidates by about 40% and EvictionProtection3Networks250Candidates by about 75%
    • Not sure if it is intended but the warning message :wavy_dash: EvictionProtection3Networks100Candidates (Unstable with ~100.0 iters. Increase minEpochIterations to e.g. 1000) seems to be quite flaky

    Note: Results are in reverse chronological order of commits

    0|               ns/op |                op/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|           14,383.08 |           69,526.14 |    5.1% |      0.02 | :wavy_dash: `EvictionProtection1Network250Candidates` (Unstable with ~100.0 iters. Increase `minEpochIterations` to e.g. 1000)
3|            5,818.85 |          171,855.12 |    0.3% |      0.01 | `EvictionProtection3Networks050Candidates`
4|           13,127.23 |           76,177.56 |    1.8% |      0.01 | `EvictionProtection3Networks100Candidates`
5|           92,835.73 |           10,771.71 |    7.0% |      0.09 | :wavy_dash: `EvictionProtection3Networks250Candidates` (Unstable with ~100.0 iters. Increase `minEpochIterations` to e.g. 1000)

    0|               ns/op |                op/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|           13,408.72 |           74,578.36 |    1.7% |      0.01 | `EvictionProtection1Network250Candidates`
3|            5,610.19 |          178,247.08 |    0.1% |      0.01 | `EvictionProtection3Networks050Candidates`
4|           13,536.82 |           73,872.57 |    6.3% |      0.01 | :wavy_dash: `EvictionProtection3Networks100Candidates` (Unstable with ~100.0 iters. Increase `minEpochIterations` to e.g. 1000)
5|           87,720.01 |           11,399.91 |    2.2% |      0.09 | `EvictionProtection3Networks250Candidates`

    0|               ns/op |                op/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|            8,080.88 |          123,748.98 |    2.8% |      0.01 | `EvictionProtection1Network250Candidates`
3|            5,650.52 |          176,974.71 |    0.1% |      0.01 | `EvictionProtection3Networks050Candidates`
4|           13,847.64 |           72,214.45 |   11.6% |      0.01 | :wavy_dash: `EvictionProtection3Networks100Candidates` (Unstable with ~100.0 iters. Increase `minEpochIterations` to e.g. 1000)
5|           88,185.71 |           11,339.71 |    1.8% |      0.09 | `EvictionProtection3Networks250Candidates`

    0|               ns/op |                op/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|            7,854.82 |          127,310.36 |    0.6% |      0.01 | `EvictionProtection1Network250Candidates`
3|            2,774.58 |          360,414.26 |    0.1% |      0.00 | `EvictionProtection3Networks050Candidates`
4|            8,513.58 |          117,459.47 |    0.1% |      0.01 | `EvictionProtection3Networks100Candidates`
5|           22,571.88 |           44,302.90 |   10.1% |      0.02 | :wavy_dash: `EvictionProtection3Networks250Candidates` (Unstable with ~100.0 iters. Increase `minEpochIterations` to e.g. 1000)
  20. jonatack commented at 11:23 am on July 7, 2021: member

    Thanks for testing @klementtan!

    Didn’t notice any significant improvement with c0d658f

    Thanks for pointing this out. The benchmarks don’t test it. Will look at adding a bench with no protected networks.

    Didn’t notice any significant improvement with edc59d0

    This commit doesn’t help performance but fixes an off-by-one in the logic that doesn’t affect the protection currently, but without it, the last commit would fail the node_eviction fuzzer by trying to save (1 - 2) = -1 into Net::count, which is size_t (unsigned long). The CI initially reported this, but I can no longer reproduce it locally (thanks @vasild for testing this) and have dropped the commit.

    Not sure if it is intended but the warning message :wavy_dash: EvictionProtection3Networks100Candidates (Unstable with ~100.0 iters. Increase minEpochIterations to e.g. 1000) seems to be quite flaky

    Thanks for reporting. The benchmark was sped up in the last push, but am looking at maybe increasing the iterations to improve this.

  21. jonatack force-pushed on Jul 8, 2021
  22. jonatack commented at 10:25 am on July 8, 2021: member

    Updated per git diff 524aa5d b1d905c

    • adjusted the benchmarks to use the default Epochs of 11, increased the epochIterations from 100 to 1000, and added a warmup of 100; I didn’t find a magic sweet spot (I have to run it several times) but this seems to improve the err% somewhat while keeping the benchmark fast
    • added two benchmarks, EvictionProtection0Networks250Candidates and EvictionProtection2Networks250Candidates
    • dropped commit https://github.com/bitcoin/bitcoin/commit/edc59d08fc57f5f10657a044224a0b3ae2d2b9bc “p2p: don’t protect more than the network candidates count”
     05adb064 bench: add peer eviction protection benchmarks
 1
 2|               ns/op |                op/s |    err% |     total | benchmark
 3|--------------------:|--------------------:|--------:|----------:|:----------
 4|           74,657.56 |           13,394.49 |    2.5% |      0.85 | `EvictionProtection0Networks250Candidates`
 5|           71,502.14 |           13,985.60 |    1.1% |      0.78 | `EvictionProtection1Networks250Candidates`
 6|           74,242.65 |           13,469.35 |    2.1% |      0.88 | `EvictionProtection2Networks250Candidates`
 7|            9,280.36 |          107,754.43 |    3.0% |      0.11 | `EvictionProtection3Networks050Candidates`
 8|           22,320.52 |           44,801.83 |    2.5% |      0.25 | `EvictionProtection3Networks100Candidates`
 9|          149,821.48 |            6,674.61 |    2.7% |      1.64 | `EvictionProtection3Networks250Candidates`
10
11|               ns/op |                op/s |    err% |     total | benchmark
12|--------------------:|--------------------:|--------:|----------:|:----------
13|           73,715.17 |           13,565.73 |    1.9% |      0.82 | `EvictionProtection0Networks250Candidates`
14|           71,505.03 |           13,985.03 |    1.7% |      0.79 | `EvictionProtection1Networks250Candidates`
15|           74,924.25 |           13,346.81 |    2.6% |      0.86 | `EvictionProtection2Networks250Candidates`
16|            9,493.08 |          105,339.84 |    4.4% |      0.11 | `EvictionProtection3Networks050Candidates`
17|           23,528.00 |           42,502.55 |    2.7% |      0.26 | `EvictionProtection3Networks100Candidates`
18|          148,696.37 |            6,725.11 |    0.6% |      1.68 | `EvictionProtection3Networks250Candidates`
19
20
21b1d905c p2p: earlier continuation when no remaining eviction candidates
22
23|               ns/op |                op/s |    err% |     total | benchmark
24|--------------------:|--------------------:|--------:|----------:|:----------
25|           19,051.62 |           52,488.98 |    2.6% |      0.21 | `EvictionProtection0Networks250Candidates`
26|           25,607.00 |           39,051.82 |    1.9% |      0.28 | `EvictionProtection1Networks250Candidates`
27|           31,392.03 |           31,855.22 |    3.5% |      0.40 | `EvictionProtection2Networks250Candidates`
28|            4,873.49 |          205,191.84 |    2.1% |      0.06 | `EvictionProtection3Networks050Candidates`
29|           13,827.88 |           72,317.64 |    3.9% |      0.16 | `EvictionProtection3Networks100Candidates`
30|           34,605.17 |           28,897.42 |    1.5% |      0.39 | `EvictionProtection3Networks250Candidates`
31
32|               ns/op |                op/s |    err% |     total | benchmark
33|--------------------:|--------------------:|--------:|----------:|:----------
34|           19,255.11 |           51,934.26 |    2.9% |      0.21 | `EvictionProtection0Networks250Candidates`
35|           26,797.82 |           37,316.47 |    3.4% |      0.30 | `EvictionProtection1Networks250Candidates`
36|           31,007.27 |           32,250.50 |    1.8% |      0.35 | `EvictionProtection2Networks250Candidates`
37|            5,075.53 |          197,023.62 |    3.3% |      0.06 | `EvictionProtection3Networks050Candidates`
38|           13,964.15 |           71,611.94 |    3.5% |      0.16 | `EvictionProtection3Networks100Candidates`
39|           34,294.63 |           29,159.08 |    1.6% |      0.39 | `EvictionProtection3Networks250Candidates`

    It looks like the performance gains of 2x-5x will be even higher when additional disadvantaged networks are added.

  23. bench: add peer eviction protection benchmarks 
    Co-authored-by: Vasil Dimov <vd@FreeBSD.org>
    5adb064574
  24. p2p: iterate eviction protection only on networks having candidates 
    in ProtectEvictionCandidatesByRatio().

Thank you to Vasil Dimov, whose suggestions during a post-merge
discussion about PR 21261 reminded me that I had done this in
earlier versions of the PR, e.g. commits like ef411cd2.

Co-authored-by: Vasil Dimov <vd@FreeBSD.org>
    02e411ec45
  25. p2p: process more candidates per protection iteration 
    for the usual case when some of the protected networks
don't have eviction candidates, to reduce the number
of iterations in ProtectEvictionCandidatesByRatio().

Picks up an idea in ef411cd2 that I had dropped.
    c9e8d8f9b1
  26. p2p: earlier continuation when no remaining eviction candidates 
    in ProtectEvictionCandidatesByRatio().

With this change, `if (n.count == 0) continue;` will be true
if a network had candidates protected in the first iterations
and has no candidates remaining to be protected in later iterations.

Co-authored-by: Jon Atack <jon@atack.com>
    b1d905c225
  27. jonatack force-pushed on Jul 8, 2021
  28. klementtan commented at 1:49 pm on July 8, 2021: contributor

    Tested and code review ACK b1d905c2.

    Also no longer seeing ... Unstable with ~100.0 iters. Increase minEpochIterations to e.g. 1000) warning.

    5adb0645:

    0|               ns/op |                op/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|           18,612.89 |           53,726.22 |    1.3% |      0.21 | `EvictionProtection0Networks250Candidates`
3|           15,604.12 |           64,085.64 |    1.1% |      0.17 | `EvictionProtection1Networks250Candidates`
4|           46,098.96 |           21,692.46 |    1.4% |      0.51 | `EvictionProtection2Networks250Candidates`
5|            7,573.28 |          132,043.17 |    2.2% |      0.09 | `EvictionProtection3Networks050Candidates`
6|           16,631.50 |           60,126.87 |    3.2% |      0.18 | `EvictionProtection3Networks100Candidates`
7|           97,775.81 |           10,227.48 |    3.3% |      1.09 | `EvictionProtection3Networks250Candidates`

    02e411ec

    0
1|               ns/op |                op/s |    err% |     total | benchmark
2|--------------------:|--------------------:|--------:|----------:|:----------
3|           18,389.64 |           54,378.44 |    1.7% |      0.20 | `EvictionProtection0Networks250Candidates`
4|           13,869.52 |           72,100.52 |    1.3% |      0.15 | `EvictionProtection1Networks250Candidates`
5|           46,016.06 |           21,731.55 |    3.4% |      0.50 | `EvictionProtection2Networks250Candidates`
6|            6,408.73 |          156,037.13 |    3.6% |      0.07 | `EvictionProtection3Networks050Candidates`
7|           16,160.17 |           61,880.55 |    2.1% |      0.18 | `EvictionProtection3Networks100Candidates`
8|           96,984.48 |           10,310.93 |    4.5% |      1.07 | `EvictionProtection3Networks250Candidates`

    c9e8d8f9

    0
1|               ns/op |                op/s |    err% |     total | benchmark
2|--------------------:|--------------------:|--------:|----------:|:----------
3|           13,422.68 |           74,500.80 |    1.3% |      0.15 | `EvictionProtection0Networks250Candidates`
4|           10,170.63 |           98,322.35 |    1.5% |      0.11 | `EvictionProtection1Networks250Candidates`
5|           17,204.80 |           58,123.30 |    1.0% |      0.19 | `EvictionProtection2Networks250Candidates`
6|            7,508.82 |          133,176.80 |    2.6% |      0.08 | `EvictionProtection3Networks050Candidates`
7|           16,172.34 |           61,833.97 |    1.1% |      0.17 | `EvictionProtection3Networks100Candidates`
8|           95,083.59 |           10,517.06 |    4.0% |      1.05 | `EvictionProtection3Networks250Candidates`

    b1d905c2

    0|               ns/op |                op/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|           23,721.76 |           42,155.39 |    1.2% |      0.27 | `EvictionProtection0Networks250Candidates`
3|           17,557.76 |           56,954.87 |    0.2% |      0.20 | `EvictionProtection1Networks250Candidates`
4|           29,148.45 |           34,307.14 |    0.4% |      0.33 | `EvictionProtection2Networks250Candidates`
5|            6,159.56 |          162,349.31 |    0.1% |      0.07 | `EvictionProtection3Networks050Candidates`
6|           19,989.47 |           50,026.33 |    0.6% |      0.22 | `EvictionProtection3Networks100Candidates`
7|           42,009.48 |           23,804.15 |    0.8% |      0.47 | `EvictionProtection3Networks250Candidates`
  29. vasild approved
  30. vasild commented at 2:59 pm on July 8, 2021: member

    ACK b1d905c225e87a4a289c0cd3593c6c21cea3fba7

    base (5adb06457403f8c1d874e9c6748ecbb78ef8fa2b bench: add peer eviction protection benchmarks)

    ns/op op/s err% total benchmark
    15,636.87 63,951.43 0.6% 0.17 EvictionProtection0Networks250Candidates
    12,885.39 77,607.27 0.5% 0.14 EvictionProtection1Networks250Candidates
    35,732.17 27,985.99 0.3% 0.39 EvictionProtection2Networks250Candidates
    5,514.20 181,349.88 1.9% 0.06 EvictionProtection3Networks050Candidates
    12,243.04 81,679.08 0.2% 0.13 EvictionProtection3Networks100Candidates
    76,015.27 13,155.25 0.4% 0.85 EvictionProtection3Networks250Candidates

    all improvements (b1d905c225e87a4a289c0cd3593c6c21cea3fba7 p2p: earlier continuation when no remaining eviction candidates)

    ns/op op/s err% total benchmark
    10,587.04 94,455.10 0.7% 0.12 EvictionProtection0Networks250Candidates
    8,046.60 124,276.05 0.8% 0.09 EvictionProtection1Networks250Candidates
    12,479.92 80,128.74 1.0% 0.14 EvictionProtection2Networks250Candidates
    2,784.53 359,127.39 4.3% 0.03 EvictionProtection3Networks050Candidates
    8,286.96 120,671.54 0.4% 0.09 EvictionProtection3Networks100Candidates
    18,450.28 54,199.71 0.7% 0.20 EvictionProtection3Networks250Candidates

    Benchmarks complete in ~2 seconds.

  31. jarolrod commented at 5:05 am on July 9, 2021: member

    ACK b1d905c225e87a4a289c0cd3593c6c21cea3fba7

    The way this has progressed since my last review makes sense. This is still a performance and improvement and code looks good.

    I do still run into instability:

    0Unstable with ~1,001.0 iters. Increase `minEpochIterations` to e.g. 10010

    Not sure what to make of it because I’m running the macOS 12 Beta (not a super stable system overall). Just wanted to document that I am running into that, I will have time later today to try on other systems. If no one else is running into it, let’s assume it’s my system.

    The warning is flaky though, here’s the results of my runs where I didn’t run into the warning:

    Base: Master + (566357f8f7471f74729297868917aa32f6d3c390 + 5adb06457403f8c1d874e9c6748ecbb78ef8fa2b)

    ns/op op/s err% total benchmark
    18,439.40 54,231.71 4.0% 0.21 EvictionProtection0Networks250Candidates
    16,029.50 62,384.99 3.1% 0.18 EvictionProtection1Networks250Candidates
    43,125.31 23,188.24 2.6% 0.47 EvictionProtection2Networks250Candidates
    7,225.39 138,400.78 3.1% 0.08 EvictionProtection3Networks050Candidates
    15,869.58 63,013.65 3.5% 0.18 EvictionProtection3Networks100Candidates
    97,586.25 10,247.35 1.1% 1.06 EvictionProtection3Networks250Candidates

    All Improvements: b1d905c225e87a4a289c0cd3593c6c21cea3fba7

    ns/op op/s err% total benchmark
    12,764.72 78,340.94 2.1% 0.14 EvictionProtection0Networks250Candidates
    9,367.04 106,757.28 3.0% 0.10 EvictionProtection1Networks250Candidates
    14,846.86 67,354.33 1.4% 0.16 EvictionProtection2Networks250Candidates
    3,493.85 286,217.28 4.8% 0.04 EvictionProtection3Networks050Candidates
    10,208.73 97,955.35 2.0% 0.11 EvictionProtection3Networks100Candidates
    22,498.62 44,447.18 0.9% 0.25 EvictionProtection3Networks250Candidates
  32. jonatack commented at 3:56 pm on July 9, 2021: member

    Not sure what to make of it because I’m running the macOS 12 Beta (not a super stable system overall).

    Yes, I tuned my system and yet still see that most of the time on at least half of the benchmarks when running all of them with ./src/bench/bench_bitcoin. It came down to the preference of being able to run these new benchmarks 10 times in ~20 seconds rather than once in 30-60 seconds, and having a rapid result that works for the most people. There just seems to be decreasing utility in adding iterations.

  33. laanwj merged this on Jul 15, 2021
  34. laanwj closed this on Jul 15, 2021
  35. jonatack deleted the branch on Jul 15, 2021
  36. sidhujag referenced this in commit 4745a73c52 on Jul 23, 2021
  37. Fabcien referenced this in commit ee65041c34 on Feb 17, 2022
  38. gwillen referenced this in commit 84b41b323a on Jun 1, 2022
  39. DrahtBot locked this on Aug 18, 2022


jonatack klementtan DrahtBot jarolrod theStack vasild

Labels
P2P

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin/bitcoin. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-11-23 18:12 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me