HomePhabricator

addrman: Improve performance of Good

Description

addrman: Improve performance of Good

Summary:

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.

Improving performance of Good_ 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>

This is a partial backport of core#22974
https://github.com/bitcoin/bitcoin/pull/22974/commits/eb2e113df13c7b1ede279878f5cbad877af49f8e

Depends on D10855

The other two commits are not applicable due to a large stack of missing fuzz backports.

Test Plan:
ninja all check-all

Benchmark: ./src/bench/bitcoin-bench -filter=AddrManGood

Before:

|               ns/op |                op/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|       96,564,809.00 |               10.36 |    0.2% |      0.49 | `AddrManGood`

|      100,490,917.00 |                9.95 |    0.8% |      0.51 | `AddrManGood`

|       99,080,029.00 |               10.09 |    0.9% |      0.50 | `AddrManGood`

After:

|               ns/op |                op/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|        1,355,126.00 |              737.94 |    2.1% |      0.01 | `AddrManGood`

|        1,330,379.00 |              751.67 |    5.7% |      0.01 | :wavy_dash: `AddrManGood` (Unstable with ~1.0 iters. Increase `minEpochIterations` to e.g. 10)

|          859,394.00 |            1,163.61 |    1.3% |      0.00 | `AddrManGood`

Reviewers: #bitcoin_abc, Fabien

Reviewed By: #bitcoin_abc, Fabien

Subscribers: Fabien

Differential Revision: https://reviews.bitcoinabc.org/D10857

Details

Provenance
Martin Zumsande <mzumsande@gmail.com>Authored on Sep 9 2021, 19:41
PiRKCommitted on Jan 21 2022, 10:07
PiRKPushed on Jan 21 2022, 10:07
Reviewer
Restricted Project
Differential Revision
D10857: addrman: Improve performance of Good
Parents
rABC594794938f9e: util: Make Assume() usable as unary expression
Branches
Unknown
Tags
Unknown