addrman: improve performance by using more suitable containers #18722

vasild · 2020-04-21T13:17:05Z

CAddrMan uses std::map internally even though it does not require
that the map's elements are sorted. std::map's access time is
O(log(map size)). std::unordered_map is more suitable as it has a
O(1) access time.

This patch lowers the execution times of CAddrMan's methods as follows
(as per src/bench/addrman.cpp):

AddrMan::Add(): -3.5%
AddrMan::GetAddr(): -76%
AddrMan::Good(): -0.38%
AddrMan::Select(): -45%

vasild · 2020-04-21T13:17:32Z

Full output from the benchmark (./src/bench/bench_bitcoin -filter="AddrMan.*"):

std::map

Benchmark	evals	iterations	total	min	max	median
AddrManAdd	5	5	4.45807	0.176704	0.179945	0.178443
AddrManGetAddr	5	500	4.09847	0.00163663	0.00164301	0.0016392
AddrManGood	5	2	4.66502	0.460193	0.474046	0.467368
AddrManSelect	5	1000000	2.07299	4.12892e-07	4.15564e-07	4.147e-07

std::unordered_map

Benchmark	evals	iterations	total	min	max	median
AddrManAdd	5	5	4.30032	0.169753	0.1738	0.172047
AddrManGetAddr	5	500	0.967398	0.000384406	0.00038996	0.000387176
AddrManGood	5	2	4.64742	0.460599	0.471216	0.464143
AddrManSelect	5	1000000	1.14085	2.23899e-07	2.36962e-07	2.26767e-07

raw output

map$ ./src/bench/bench_bitcoin -filter="AddrMan.*"
# Benchmark, evals, iterations, total, min, max, median
AddrManAdd, 5, 5, 4.45807, 0.176704, 0.179945, 0.178443
AddrManGetAddr, 5, 500, 4.09847, 0.00163663, 0.00164301, 0.0016392
AddrManGood, 5, 2, 4.66502, 0.460193, 0.474046, 0.467368
AddrManSelect, 5, 1000000, 2.07299, 4.12892e-07, 4.15564e-07, 4.147e-07

unordered_map$ ./src/bench/bench_bitcoin -filter="AddrMan.*"
# Benchmark, evals, iterations, total, min, max, median
AddrManAdd, 5, 5, 4.30032, 0.169753, 0.1738, 0.172047
AddrManGetAddr, 5, 500, 0.967398, 0.000384406, 0.00038996, 0.000387176
AddrManGood, 5, 2, 4.64742, 0.460599, 0.471216, 0.464143
AddrManSelect, 5, 1000000, 1.14085, 2.23899e-07, 2.36962e-07, 2.26767e-07

src/addrman.h

maflcko · 2020-04-22T14:53:32Z

Would it be possible to submit the benchmark upfront as a separate pull, so that https://codespeed.bitcoinperf.com/ can start running it?

vasild · 2020-04-24T09:40:05Z

Done: #18754

vasild · 2020-04-27T10:25:30Z

Removed the first commit (which introduced the benchmark), now that it is already merged into master and rebased.

src/netaddress.h

src/addrman.h

DrahtBot · 2020-05-20T21:52:32Z

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

refactor: Make CAddrMan::cs non-recursive #19238 (refactor: Make CAddrMan::cs non-recursive by hebasto)

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.

`CAddrMan` uses `std::map` internally even though it does not require that the map's elements are sorted. `std::map`'s access time is `O(log(map size))`. `std::unordered_map` is more suitable as it has a `O(1)` access time. This patch lowers the execution times of `CAddrMan`'s methods as follows (as per `src/bench/addrman.cpp`): ``` AddrMan::Add(): -3.5% AddrMan::GetAddr(): -76% AddrMan::Good(): -0.38% AddrMan::Select(): -45% ``` Github-Pull: bitcoin#18722 Rebased-From: 7cc3172

sipa · 2020-06-10T06:00:17Z

utACK 7cc3172

hebasto · 2020-06-12T18:27:20Z

Concept ACK.

hebasto

Benchmarking results:

master (8c97780)

$ ./src/bench/bench_bitcoin -filter="AddrMan.*"
# Benchmark, evals, iterations, total, min, max, median
AddrManAdd, 5, 5, 1.15889, 0.0458257, 0.0469068, 0.0464069
AddrManGetAddr, 5, 500, 1.94467, 0.000772949, 0.000789915, 0.000775272
AddrManGood, 5, 2, 5.69597, 0.563135, 0.57652, 0.570197
AddrManSelect, 5, 1000000, 1.17994, 2.32975e-07, 2.37942e-07, 2.36478e-07

master + this PR

$ ./src/bench/bench_bitcoin -filter="AddrMan.*"
# Benchmark, evals, iterations, total, min, max, median
AddrManAdd, 5, 5, 0.972042, 0.0383488, 0.0396571, 0.0386554
AddrManGetAddr, 5, 500, 0.649199, 0.000256967, 0.000262957, 0.00025942
AddrManGood, 5, 2, 5.35751, 0.531294, 0.540723, 0.534681
AddrManSelect, 5, 1000000, 0.657766, 1.29313e-07, 1.36428e-07, 1.30873e-07

Nice :)

hebasto

nit: If #includes in addrman.h are already touched, mind moving

#include <fs.h>
#include <hash.h>
#include <streams.h>

into the first group?

src/addrman.cpp

src/netaddress.h

vasild · 2020-06-15T15:00:19Z

nit: If #includes in addrman.h are already touched, mind moving...

Good catch, they should be moved! Given that there is already one ACK, I will move the headers if I alter this PR or as a followup PR if this gets merged as is now.

hebasto

ACK 7cc3172

@vasild feel free to ignore my nits :)

hebasto · 2020-06-25T10:01:32Z

src/netaddress.h

+        CSipHasher hasher(salt_k0, salt_k1);
+        hasher.Write(a.ip, sizeof(a.ip));
+        return (size_t)hasher.Finalize();


nit: All calls could be chained:

Suggested change

CSipHasher hasher(salt_k0, salt_k1);

hasher.Write(a.ip, sizeof(a.ip));

return (size_t)hasher.Finalize();

return CSipHasher(salt_k0, salt_k1).Write(a.ip, sizeof(a.ip)).Finalize();

I actually find the 3-line variant easier to read (that could be subjective). The 3-line variant is more manageable wrt setting a breakpoint or reading a backtrace (e.g. if you only see it crashed on that multi-chained-line it wouldn't be clear whether it crashed in the constructor, in the Write() method or in the Finalize() method).

I would prefer to leave it as is.

src/netaddress.h

vasild · 2020-06-25T11:47:59Z

Prefixed salt_k0 and salt_k1 with m_ to abide to the naming convention. diff.

vasild · 2021-05-21T11:25:54Z

6f0c9f5390...6a1a28f2ad: rebased due to conflicts, plus add m_net to the CNetAddr hashing.

sipa · 2021-05-21T17:29:05Z

src/netaddress.h

+    size_t operator()(const CNetAddr& a) const noexcept
+    {
+        CSipHasher hasher(m_salt_k0, m_salt_k1);
+        hasher.Write(reinterpret_cast<const uint8_t*>(&a.m_net), sizeof(a.m_net));


Micronit: this reinterpret cast is a bit ugly. You could avoid it by just doing hasher.Write(a.m_net);; it'll interpret a.m_net as a uint64_t and use the optimized integer hasher.

Done. I hope the implicit conversion from int to uint64_t will not upset some compiler.

The ugliness could maybe be considered a virtue; it's explicit that this is an "on your head be it!" type of cast and highlights that the code could ideally be improved. https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#es49-if-you-must-use-a-cast-use-a-named-cast

Here we can do without a cast since there is Write() method that takes an integer argument (modulo int -> uint64 conversion which is ok because we never pass negative values).

sipa · 2021-05-21T17:43:35Z

utACK 6a1a28f

vasild · 2021-05-24T08:40:00Z

6a1a28f2ad...c22e98b30d: address review suggestion

jonatack

ACK c22e98b

hebasto

ACK c22e98b

src/addrman.h

vasild · 2021-05-28T11:16:37Z

c22e98b30d...1f4ee9c905: rebase due to conflicts and address review suggestion

jonatack

ACK 1f4ee9c

src/addrman.h

`CAddrMan` uses `std::map` internally even though it does not require that the map's elements are sorted. `std::map`'s access time is `O(log(map size))`. `std::unordered_map` is more suitable as it has a `O(1)` access time. This patch lowers the execution times of `CAddrMan`'s methods as follows (as per `src/bench/addrman.cpp`): ``` AddrMan::Add(): -3.5% AddrMan::GetAddr(): -76% AddrMan::Good(): -0.38% AddrMan::Select(): -45% ```

vasild · 2021-05-28T14:42:03Z

1f4ee9c905...a92485b2c2: address review suggestion

jonatack · 2021-05-28T17:30:45Z

ACK a92485b

hebasto

re-ACK a92485b, only suggested changes and rebased since my previous review.

achow101 · 2021-06-11T19:24:39Z

ACK a92485b

…ble con…

fanquake added the P2P label Apr 21, 2020

vasild changed the title ~~addrman: use unordered_map instead of map~~ addrman: improve performance by using more suitable containers Apr 21, 2020

Empact reviewed Apr 21, 2020

View reviewed changes

src/addrman.h Outdated Show resolved Hide resolved

src/addrman.h Show resolved Hide resolved

vasild force-pushed the addrman_map branch from 52faf86 to 0c3becc Compare April 21, 2020 19:43

fanquake requested a review from sipa April 22, 2020 08:45

vasild mentioned this pull request Apr 24, 2020

bench: add CAddrMan benchmarks #18754

Merged

vasild force-pushed the addrman_map branch from 0c3becc to 4591c3d Compare April 27, 2020 10:24

sipa reviewed Apr 27, 2020

View reviewed changes

src/netaddress.h Outdated Show resolved Hide resolved

src/addrman.h Outdated Show resolved Hide resolved

vasild force-pushed the addrman_map branch 2 times, most recently from 2225590 to 7cc3172 Compare May 5, 2020 09:50

DrahtBot mentioned this pull request May 20, 2020

Implement ADDRv2 support (part of BIP155) #19031

Closed

11 tasks

DrahtBot mentioned this pull request May 28, 2020

refactor: Cleanup thread ctor calls #19064

Merged

This was referenced Jun 10, 2020

refactor: Make CAddrMan::cs non-recursive #19238

Merged

[Do Not Merge] ci: Temporary Test Case for negative capabilities in the Clang Thread Safety annotations #19251

Closed

hebasto reviewed Jun 13, 2020

View reviewed changes

src/addrman.cpp Outdated Show resolved Hide resolved

src/addrman.cpp Outdated Show resolved Hide resolved

src/netaddress.h Outdated Show resolved Hide resolved

hebasto approved these changes Jun 15, 2020

View reviewed changes

hebasto reviewed Jun 25, 2020

View reviewed changes

src/netaddress.h Outdated Show resolved Hide resolved

vasild force-pushed the addrman_map branch from 7cc3172 to a72fee6 Compare June 25, 2020 11:46

DrahtBot removed the Needs rebase label Feb 10, 2021

DrahtBot mentioned this pull request Mar 7, 2021

net, refactor: pass uint16 CService::port as uint16 #21328

Merged

DrahtBot mentioned this pull request May 4, 2021

p2p, rpc: enable GetAddr, GetAddresses, and getnodeaddresses by network #21843

Merged

DrahtBot added the Needs rebase label May 20, 2021

vasild force-pushed the addrman_map branch from 6f0c9f5 to 6a1a28f Compare May 21, 2021 11:23

DrahtBot removed the Needs rebase label May 21, 2021

sipa reviewed May 21, 2021

View reviewed changes

DrahtBot mentioned this pull request May 23, 2021

refactor: Group and re-order CAddrMan members by access type #22025

Merged

vasild force-pushed the addrman_map branch from 6a1a28f to c22e98b Compare May 24, 2021 08:39

jonatack reviewed May 24, 2021

View reviewed changes

hebasto approved these changes May 24, 2021

View reviewed changes

src/addrman.h Outdated Show resolved Hide resolved

DrahtBot added the Needs rebase label May 27, 2021

vasild force-pushed the addrman_map branch from c22e98b to 1f4ee9c Compare May 28, 2021 11:16

DrahtBot removed the Needs rebase label May 28, 2021

jonatack reviewed May 28, 2021

View reviewed changes

src/addrman.h Outdated Show resolved Hide resolved

vasild force-pushed the addrman_map branch from 1f4ee9c to a92485b Compare May 28, 2021 14:41

hebasto approved these changes May 29, 2021

View reviewed changes

fanquake merged commit 1a369f0 into bitcoin:master Jun 12, 2021

vasild deleted the addrman_map branch June 13, 2021 07:14

sidhujag pushed a commit to syscoin/syscoin that referenced this pull request Jun 13, 2021

Merge bitcoin#18722: addrman: improve performance by using more suita…

37a5ba0

…ble con…

gwillen pushed a commit to ElementsProject/elements that referenced this pull request Jun 1, 2022

Merge 1a369f0 into merged_master (Bitcoin PR bitcoin/bitcoin#18722)

fdeeae4

bitcoin locked as resolved and limited conversation to collaborators Aug 16, 2022

addrman: improve performance by using more suitable containers #18722

addrman: improve performance by using more suitable containers #18722

Uh oh!

Conversation

vasild commented Apr 21, 2020

Uh oh!

vasild commented Apr 21, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

maflcko commented Apr 22, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

vasild commented Apr 24, 2020

Uh oh!

vasild commented Apr 27, 2020

Uh oh!

Uh oh!

Uh oh!

DrahtBot commented May 20, 2020 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Conflicts

Uh oh!

sipa commented Jun 10, 2020

Uh oh!

hebasto commented Jun 12, 2020

Uh oh!

hebasto left a comment

Choose a reason for hiding this comment

Uh oh!

hebasto left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

vasild commented Jun 15, 2020

Uh oh!

hebasto left a comment

Choose a reason for hiding this comment

Uh oh!

hebasto Jun 25, 2020

Choose a reason for hiding this comment

Uh oh!

vasild Jun 25, 2020

Choose a reason for hiding this comment

Uh oh!

Uh oh!

vasild commented Jun 25, 2020

Uh oh!

vasild commented May 21, 2021

Uh oh!

sipa May 21, 2021

Choose a reason for hiding this comment

Uh oh!

vasild May 24, 2021

Choose a reason for hiding this comment

Uh oh!

jonatack May 24, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

vasild May 24, 2021

Choose a reason for hiding this comment

Uh oh!

sipa commented May 21, 2021

Uh oh!

vasild commented May 24, 2021

Uh oh!

jonatack left a comment

Choose a reason for hiding this comment

Uh oh!

hebasto left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

vasild commented May 28, 2021

Uh oh!

jonatack left a comment

vasild commented Apr 21, 2020 •

edited

Loading

maflcko commented Apr 22, 2020 •

edited

Loading

DrahtBot commented May 20, 2020 •

edited

Loading

jonatack May 24, 2021 •

edited

Loading