Performance - PushGetBlocks slow at high block counts due to inefficient algorithm in CBlockLocator::Set function

Issue #233 new
Woodstock Merkle
created an issue

In several codepaths where a client has determined that a peer likely has blocks that it does not have, the client sends a getblocks message. The message includes a locator: "breadcrumbs" by way of a set of hashes of exponentially increased spacing that are a hint to the peer to determine which blocks to send.

However, the implementation of the function CBlockLocator::Set becomes computationally inefficient with the blockchain at 750k+ blocks. This single operation can take 1 second or more to determine the set of ~30 hashes to send

This is exacerbated that, when a client is connected to multiple parents while downloading, it receives Orphans; for each orphan it receives, it triggers a new PushGetBlocks request, which takes a second and therefore slows blockchain downloads by a factor of about 100.

This code is original Satoshi code that has impact on Nu (and likely Peercoin, Peershares template, and eventually B&C) due to the accelerated blockchain interval.

Extra debugging info shows 2 seconds to compute:

2016-03-11 04:10:06 PushGetBlocks sent to client 777694224, height 776759, hash e80ea3e69389e61d1ee554d9773d1ed0d540d55573244bba64078434fdc00ddf to 15fa2452b2857dc3dbea3c577fface494df590ad414a989541b0c99a3a6de563
2016-03-11 04:10:06 vHave.size() is 1, nStep is 1
2016-03-11 04:10:06 vHave.size() is 2, nStep is 1
2016-03-11 04:10:06 vHave.size() is 3, nStep is 1
2016-03-11 04:10:06 vHave.size() is 4, nStep is 1
2016-03-11 04:10:06 vHave.size() is 5, nStep is 1
2016-03-11 04:10:06 vHave.size() is 6, nStep is 1
2016-03-11 04:10:06 vHave.size() is 7, nStep is 1
2016-03-11 04:10:06 vHave.size() is 8, nStep is 1
2016-03-11 04:10:06 vHave.size() is 9, nStep is 1
2016-03-11 04:10:06 vHave.size() is 10, nStep is 1
2016-03-11 04:10:06 vHave.size() is 11, nStep is 2
2016-03-11 04:10:06 vHave.size() is 12, nStep is 4
2016-03-11 04:10:06 vHave.size() is 13, nStep is 8
2016-03-11 04:10:06 vHave.size() is 14, nStep is 16
2016-03-11 04:10:06 vHave.size() is 15, nStep is 32
2016-03-11 04:10:06 vHave.size() is 16, nStep is 64
2016-03-11 04:10:06 vHave.size() is 17, nStep is 128
2016-03-11 04:10:06 vHave.size() is 18, nStep is 256
2016-03-11 04:10:06 vHave.size() is 19, nStep is 512
2016-03-11 04:10:06 vHave.size() is 20, nStep is 1024
2016-03-11 04:10:06 vHave.size() is 21, nStep is 2048
2016-03-11 04:10:06 vHave.size() is 22, nStep is 4096
2016-03-11 04:10:06 vHave.size() is 23, nStep is 8192
2016-03-11 04:10:06 vHave.size() is 24, nStep is 16384
2016-03-11 04:10:06 vHave.size() is 25, nStep is 32768
2016-03-11 04:10:06 vHave.size() is 26, nStep is 65536
2016-03-11 04:10:06 vHave.size() is 27, nStep is 131072
2016-03-11 04:10:07 vHave.size() is 28, nStep is 262144
2016-03-11 04:10:07 vHave.size() is 29, nStep is 524288
2016-03-11 04:10:08 vHave.size() is 30, nStep is 1048576
2016-03-11 04:10:08 EndMessage (1029 bytes)

Comments (3)

  1. Woodstock Merkle reporter

    I've ported a lot of the CChain code into Nu over the weekend, specifically to get that lookup ability. Still running a 1st test from overnight.

    In the pic below, time to download 1000 blocks in the CChain build (black) is looking very good compared to 2.0.3 (blue) and the 2.1.1 RC (red).

    cchain.PNG

    I basically have this massive PR that is pending -- the CChain port/refactoring, the BlockMap optimizations, and some other stuff. It is broken out across several commits to facilitate review -- I hope to get that posted up in about 12 hours.

  2. Log in to comment