Improve addrman Select() performance when buckets are nearly empty #6530

pull sipa wants to merge 1 commits into bitcoin:master from sipa:fastselect changing 1 files +8 −4

sipa commented at 5:49 PM on August 6, 2015: member

Earlier, when there are only a few entries in the addrman tables, Select() could spin for long periods of time (~200ms), resulting in high CPU usage (up to 40% here). This reduces it to around 0.3ms (0.5% CPU).
sipa force-pushed on Aug 6, 2015
sipa force-pushed on Aug 6, 2015
dgenr8 commented at 3:38 AM on August 7, 2015: contributor

utACK
laanwj added the label P2P on Aug 7, 2015
TheBlueMatt cross-referenced this on Aug 8, 2015 from issue Improve addrman Select() performance when buckets are nearly empty. by sipa
TheBlueMatt commented at 1:37 PM on August 8, 2015: contributor

utACK
gmaxwell commented at 10:05 PM on August 22, 2015: contributor

ACK
Improve addrman Select() performance when buckets are nearly empty c33c11ebac

in src/addrman.cpp:None in 9ddf0fdce3 outdated

 340 | @@ -341,8 +341,11 @@ CAddrInfo CAddrMan::Select_()
 341 |          while (1) {
 342 |              int nKBucket = GetRandInt(ADDRMAN_TRIED_BUCKET_COUNT);
 343 |              int nKBucketPos = GetRandInt(ADDRMAN_BUCKET_SIZE);
 344 | -            if (vvTried[nKBucket][nKBucketPos] == -1)
 345 | -                continue;
 346 | +            while (1) {

laanwj commented at 12:05 PM on August 24, 2015:

Equivalent but maybe slightly more readable:

while(vvTried[nKBucket][nKBucketPos] == -1) {
    nKBucket = (nKBucket + insecure_rand()) % ADDRMAN_TRIED_BUCKET_COUNT;
    nKBucketPos = (nKBucketPos + insecure_rand()) % ADDRMAN_BUCKET_SIZE;
}

sipa commented at 12:01 AM on August 26, 2015:

Nit addressed.

sipa force-pushed on Aug 26, 2015
dcousens commented at 2:07 AM on August 26, 2015: contributor

utACK
laanwj merged this on Aug 26, 2015
laanwj closed this on Aug 26, 2015
laanwj referenced this in commit ea19c2bc3f on Aug 26, 2015
Warrows cross-referenced this on Jan 20, 2019 from issue [Net] Improve addrman Select() performance when buckets are nearly empty by Warrows
bitcoin locked this on Sep 8, 2021

Contributors

Labels