addrman: Improve performance of Good

mzumsande commented at 5:54 pm on September 14, 2021: member

Currently, CAddrman::Good() is rather slow because the process of moving an addr from new to tried involves looping over the new tables twice:

In Good_(), there is a loop searching for a new bucket the addr is currently in, but this information is never used except for aborting if it is not found anywhere (since this commit it is no longer passed to MakeTried) This is unnecessary because in a non-corrupted addrman, an address that is not in New must be either in Tried or not at all in addrman, both cases in which we’d return early in Good_() and never get to this point. I removed this loop (and left a check for nRefCount as a belt-and-suspenders check).
In MakeTried(), which is called from Good_(), another loop removes all instances of this address from new. This can be spedup by stopping the search at nRefCount==0. Further reductions in nRefCount would only lead to an assert anyway. Moreover, the search can be started at the bucket determined by the source of the addr for which Good was called, so that if it is present just once in New, no further buckets need to be checked.

While calls to Good() are not that frequent normally, the performance gain is clearly seen in the fuzz target addman_serdeser, where, because of the slowness in creating a decently filled addrman, a shortcut was created that would directly populate the tried tables by reaching into addrman’s internals, bypassing Good() (#21129). I removed this workaround in the second commit: Using Good() is still slower by a factor of 2 (down from a factor of ~60 before), but I think that this compensated by the advantages of not having to reach into the internal structures of addrman (see https://github.com/jnewbery/bitcoin/pull/18#issuecomment-775218676).

[Edit]: For benchmark results see #22974 (comment) and #22974 (comment) - the benchmark AddrManGood shows a significant speedup by a factor >100.

mzumsande commented at 5:55 pm on September 14, 2021: member

cc @vasild

DrahtBot added the label P2P on Sep 14, 2021

jonatack commented at 6:31 pm on September 14, 2021: member

Nice code reduction. Did you see a difference in ./src/bench/bench_bitcoin -filter=AddrManGood?

in src/addrman.cpp:491 in 527641b9e6 outdated

485@@ -486,11 +486,14 @@ void CAddrMan::MakeTried(CAddrInfo& info, int nId)
486     AssertLockHeld(cs);
487 
488     // remove the entry from all new buckets
489-    for (int bucket = 0; bucket < ADDRMAN_NEW_BUCKET_COUNT; bucket++) {
490+    int start_bucket = info.GetNewBucket(nKey, m_asmap);
491+    for (int n = 0; n < ADDRMAN_NEW_BUCKET_COUNT; n++) {
492+        int bucket = (start_bucket + n ) % ADDRMAN_NEW_BUCKET_COUNT;

jonatack commented at 6:33 pm on September 14, 2021:

in general: clang-format, and where useful consider const, and braced initialization for type safety

0        const int bucket{(start_bucket + n) % ADDRMAN_NEW_BUCKET_COUNT};

mzumsande commented at 10:21 pm on September 15, 2021:

done for all variables in this loop.

in src/addrman.cpp:490 in 527641b9e6 outdated

485@@ -486,11 +486,14 @@ void CAddrMan::MakeTried(CAddrInfo& info, int nId)
486     AssertLockHeld(cs);
487 
488     // remove the entry from all new buckets
489-    for (int bucket = 0; bucket < ADDRMAN_NEW_BUCKET_COUNT; bucket++) {
490+    int start_bucket = info.GetNewBucket(nKey, m_asmap);
491+    for (int n = 0; n < ADDRMAN_NEW_BUCKET_COUNT; n++) {

jonatack commented at 6:35 pm on September 14, 2021:

prefer prefix iterator where postfix isn’t needed (per developer-notes.md)

0    for (int n = 0; n < ADDRMAN_NEW_BUCKET_COUNT; ++n) {

mzumsande commented at 10:22 pm on September 15, 2021:

done

in src/addrman.cpp:569 in 527641b9e6 outdated

579-
580-    // if no bucket is found, something bad happened;
581-    // TODO: maybe re-add the node, but for now, just bail out
582-    if (nUBucket == -1)
583+    // if it is not in new, something bad happened
584+    if (info.nRefCount == 0)

jonatack commented at 6:37 pm on September 14, 2021:

while touching this conditional, maybe add the missing brackets we require with conditionals of more than one line (CVE-2014-1266: the Apple “goto fail” vulnerability, https://dwheeler.com/essays/apple-goto-fail)

MarcoFalke commented at 7:21 am on September 15, 2021:

I presume this shouldn’t happen after the sanity checks passed on a deserialized addrman. So, on “bad things” that are caused by internal logic flaws, it might be better to crash in debug/test builds. Otherwise this will be harder to notice or only noticed later on.

0    if (!Assume(info.nRefCount > 0)) {

mzumsande commented at 10:22 pm on September 15, 2021:

added brackets here, thanks

mzumsande commented at 10:23 pm on September 15, 2021:

done as suggested

DrahtBot commented at 6:40 pm on September 14, 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:

#22950 ([p2p] Pimpl AddrMan to abstract implementation details by amitiuttarwar)
#22910 ([RFC] Encapsulate asmap in NetGroupManager by jnewbery)
#22734 (addrman: Avoid crash on corrupt data, Force Check after deserialize by MarcoFalke)

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.

jonatack commented at 6:41 pm on September 14, 2021: member

Building to bench. Some minor comments, feel free to ignore until concept acks and need to retouch.

jonatack commented at 7:04 pm on September 14, 2021: member

Concept ACK. Benches are showing a huge speedup for me locally.

before

 0$ ./src/bench/bench_bitcoin -filter=AddrManGood
 1
 2|               ns/op |                op/s |    err% |     total | benchmark
 3|--------------------:|--------------------:|--------:|----------:|:----------
 4|      801,906,990.00 |                1.25 |    5.7% |      4.26 | AddrManGood
 5|      814,159,543.00 |                1.23 |    6.4% |      4.03 | AddrManGood
 6|      775,065,136.00 |                1.29 |    3.5% |      3.82 | AddrManGood
 7|      795,855,140.00 |                1.26 |    6.8% |      3.98 | AddrManGood
 8|      763,767,446.00 |                1.31 |    1.7% |      3.93 | AddrManGood
 9|      778,016,971.00 |                1.29 |    2.9% |      4.03 | AddrManGood
10|      839,720,704.00 |                1.19 |    8.6% |      4.22 | AddrManGood
11|      777,639,920.00 |                1.29 |    1.8% |      3.92 | AddrManGood
12|      788,152,208.00 |                1.27 |    3.8% |      3.89 | AddrManGood
13|      792,925,660.00 |                1.26 |    3.2% |      3.99 | AddrManGood

after

 0|               ns/op |                op/s |    err% |     total | benchmark
 1|--------------------:|--------------------:|--------:|----------:|:----------
 2|        5,182,474.00 |              192.96 |   13.8% |      0.03 | AddrManGood
 3|        5,525,509.00 |              180.98 |   14.6% |      0.03 | AddrManGood
 4|        7,215,235.00 |              138.60 |    3.7% |      0.04 | AddrManGood
 5|        5,219,675.00 |              191.58 |    7.5% |      0.03 | AddrManGood
 6|        4,163,823.00 |              240.16 |    2.3% |      0.02 | AddrManGood
 7|        6,694,095.00 |              149.39 |   23.0% |      0.05 | AddrManGood
 8|        5,966,011.00 |              167.62 |   11.0% |      0.03 | AddrManGood
 9|        4,861,261.00 |              205.71 |    3.6% |      0.03 | AddrManGood
10|        5,029,188.00 |              198.84 |   16.4% |      0.03 | AddrManGood
11|        5,440,878.00 |              183.79 |   13.1% |      0.03 | AddrManGood

mzumsande commented at 7:09 pm on September 14, 2021: member

Thanks! I didn’t know about this benchmark, will try to confirm locally and add the result to OP!

amitiuttarwar commented at 10:32 pm on September 14, 2021: member

approach ACK, planning to do a more in-depth review later this week

MarcoFalke commented at 7:17 am on September 15, 2021: member

Concept ACK. Maybe also add a commit to allow for shorter fuzz inputs: #21129 (review)

This will allow the fuzz engine to potentially minimize further on crashes, or produce shorter inputs in general.

naumenkogs commented at 10:08 am on September 15, 2021: member

Concept ACK. Code also looks good, but I’m gonna ACK once you resolve all the pending suggestions from other reviewers. I agree with those suggestions.

in src/test/fuzz/addrman.cpp:102 in 527641b9e6 outdated

117-#else
118-                // 261.91 sec to fill.
119                 Add_(addr, source, time_penalty);
120+
121                 if (n > 0 && mapInfo.size() % n == 0) {
122                     Good_(addr, false, GetTime());

MarcoFalke commented at 10:13 am on September 15, 2021:

Completely unrelated, but I was wondering if it makes sense to fuzz the time here

mzumsande commented at 10:24 pm on September 15, 2021:

The comment before this block warns against fuzzing in this loop, some problem with running out of random numbers. Could use insecure_rand though?

mzumsande force-pushed on Sep 15, 2021

addrman: Improve performance of Good

This is done by removing an unnecessary loop in Good_() and looping
through the new tables in MakeTried() more efficiently, choosing a
starting value that allow us to stop early in typical cases.

Co-authored-by: John Newbery <john@johnnewbery.com>

eb2e113df1

fuzz: Use public interface to fill addrman tried tables

After the performance improvement for Good(), the direct method is only 2x faster
as opposed to 60x before.

acf656d540

fuzz: allow lower number of sources 57ce20307e

mzumsande force-pushed on Sep 15, 2021

mzumsande commented at 10:54 pm on September 15, 2021: member

Thanks for the reviews - I addressed all comments. I added a commit to allow for a lower number of sources in the fuzz test as suggested by @MarcoFalke .

I also ran the benchmark and got similar results to @jonatack:

./src/bench/bench_bitcoin -filter=AddrManGood before:

0|               ns/op |                op/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|      840,411,590.00 |                1.19 |    3.3% |      4.23 | `AddrManGood`
3|      871,339,127.00 |                1.15 |    0.1% |      4.35 | `AddrManGood`
4|      880,275,738.00 |                1.14 |    0.8% |      4.45 | `AddrManGood`
5|      874,042,056.00 |                1.14 |    1.7% |      4.34 | `AddrManGood`
6|      877,817,450.00 |                1.14 |    2.1% |      4.34 | `AddrManGood`

after

0|               ns/op |                op/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|        4,889,438.00 |              204.52 |    0.7% |      0.02 | `AddrManGood`
3|        4,831,691.00 |              206.97 |    1.5% |      0.02 | `AddrManGood`
4|        4,847,879.00 |              206.28 |    1.0% |      0.02 | `AddrManGood`
5|        4,745,268.00 |              210.74 |    0.8% |      0.02 | `AddrManGood`
6|        4,932,979.00 |              202.72 |    1.3% |      0.02 | `AddrManGood`

naumenkogs commented at 8:33 am on September 16, 2021: member

ACK 57ce20307e604530f78ef4f0f8d9fb94f80ca81b

jnewbery commented at 10:08 am on September 16, 2021: member

ACK 57ce20307e

Using the public interface to fuzz addrman is a much better approach. As well as being fewer lines of code, the fuzz test is more correct now. The previous code reached into the internals and made changes to private data which invalidated addrman’s invariants. For example, entries were placed into the tried table without setting nLastSuccess, which would cause check() to fail:

https://github.com/bitcoin/bitcoin/blob/87780dfee8c82ea09b84e74d331db2ad6f9e75ab/src/addrman.cpp#L774-L775

I think the next step is to move RandAddr() and Fill() out of CAddrManDeterministic so that they don’t have access to CAddrMan’s private data and methods.

theStack approved

theStack commented at 8:25 pm on September 16, 2021: member

ACK 57ce20307e604530f78ef4f0f8d9fb94f80ca81b

Nice addrman code cleanup and speed-up, taking advantage of nRefCount. Without much surprise, the relative performance gains between PR and master branch, as shown by running the benchmark (./src/bench/bench_bitcoin -filter=AddrManGood), are similar to the results by @jonatack and @mzumsande on my machine (>150x).

master:

0|               ns/op |                op/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|    1,333,812,989.00 |                0.75 |    3.2% |      6.66 | `AddrManGood`
3|    1,289,262,095.00 |                0.78 |    0.9% |      6.47 | `AddrManGood`
4|    1,339,632,431.00 |                0.75 |    1.6% |      6.72 | `AddrManGood`
5|    1,311,484,130.00 |                0.76 |    0.4% |      6.50 | `AddrManGood`
6|    1,326,841,389.00 |                0.75 |    1.6% |      6.59 | `AddrManGood`

PR:

0|               ns/op |                op/s |    err% |     total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2|        8,645,751.00 |              115.66 |    1.7% |      0.04 | `AddrManGood`
3|        8,715,892.00 |              114.73 |    1.2% |      0.04 | `AddrManGood`
4|        8,076,594.00 |              123.81 |    1.7% |      0.04 | `AddrManGood`
5|        8,715,701.00 |              114.74 |    1.2% |      0.04 | `AddrManGood`
6|        8,545,046.00 |              117.03 |    2.2% |      0.04 | `AddrManGood`

(tested on OpenBSD 6.9, amd64)

fanquake requested review from amitiuttarwar on Sep 17, 2021

vasild approved

vasild commented at 2:38 pm on September 17, 2021: member

ACK 57ce20307e604530f78ef4f0f8d9fb94f80ca81b

Impressive 165x boost in the AddrManGood benchmark (tested locally)! (2.3 op/s VS 380 op/s). Notice that it is adding entries with addr != source, so that lucky start_bucket is not playing a role in the benchmark, I guess.

In commit acf656d540 fuzz: Use public interface to fill addrman tried tables, Add_() and Good_() are not public interface, they are private methods.

in src/test/fuzz/addrman.cpp:85 in 57ce20307e

84@@ -85,7 +85,7 @@ class CAddrManDeterministic : public CAddrMan
85         // 0, 1, 2, 3 corresponding to 0%, 100%, 50%, 33%

vasild commented at 2:44 pm on September 17, 2021:

Just above, on line 83 (github does not let me comment on it) is a comment:

0// Add some of the addresses directly to the "tried" table.

I think the word “directly” does not apply anymore since the hackish direct addition is replaced by Add_() (goes to “new”) + Good_() (moved to “tried”).

mzumsande commented at 6:26 pm on September 20, 2021:

Thanks, will fix this in a follow-up!

in src/test/fuzz/addrman.cpp:99 in 57ce20307e

95@@ -96,31 +96,12 @@ class CAddrManDeterministic : public CAddrMan
96             for (size_t j = 0; j < num_addresses; ++j) {
97                 const auto addr = CAddress{CService{RandAddr(), 8333}, NODE_NETWORK};
98                 const auto time_penalty = insecure_rand.randrange(100000001);
99-#if 1

vasild commented at 3:01 pm on September 17, 2021:

I compared this branch with the #else branch, filled addrman with 9k addresses and did not observe any difference in performance. That is - now the high level Add_() + Good_() perform the same way as the hackish direct add to the tried table :racehorse:.

laanwj commented at 5:44 pm on September 20, 2021: member

This is fantastic, faster and less code. Code review ACK 57ce20307e604530f78ef4f0f8d9fb94f80ca81b

laanwj merged this on Sep 20, 2021

laanwj closed this on Sep 20, 2021

mzumsande commented at 6:26 pm on September 20, 2021: member

Notice that it is adding entries with addr != source, so that lucky start_bucket is not playing a role in the benchmark, I guess.

I think it does: The first Add() call creates a CAddrInfo entry in mapInfo and set CAddrInfo.source to the source, no matter if addr==source or not. Then GetNewBucket(uint256, const std::vector<bool>) which is now called from MakeTried uses just that to determine the starting bucket.

In commit acf656d fuzz: Use public interface to fill addrman tried tables, Add_() and Good_() are not public interface, they are private methods.

That’s true - thinking about doing a (fuzz-only) refactoring follow-up, in which this could be switched to Add() and Good().

jnewbery referenced this in commit 00a2c72d52 on Sep 21, 2021

martinus referenced this in commit 153e6860e8 on Sep 21, 2021

jnewbery referenced this in commit a41f097157 on Sep 21, 2021

sidhujag referenced this in commit 07fd7af727 on Sep 21, 2021

jnewbery referenced this in commit 19e2d94ecd on Sep 22, 2021

jnewbery referenced this in commit 0a1eb04590 on Oct 4, 2021

jnewbery referenced this in commit c0555ece92 on Oct 5, 2021

jnewbery referenced this in commit 44452110f0 on Oct 5, 2021

fanquake referenced this in commit 97e2435ac4 on Oct 8, 2021

sidhujag referenced this in commit 79fe0fcfe7 on Oct 8, 2021

rebroad referenced this in commit e242905409 on Oct 13, 2021

rebroad referenced this in commit 6b5030794e on Oct 13, 2021

janus referenced this in commit 7a1785c9f5 on Nov 11, 2021

Fabcien referenced this in commit 934ec8eff8 on Jan 21, 2022

DrahtBot locked this on Oct 30, 2022

mzumsande deleted the branch on Jun 23, 2023

addrman: Improve performance of Good #22974

Conflicts