Add a skiplist to the CBlockIndex structure. #4420

Another piece of logic that is needed in headersfirst: a fast way to determine whether a tip of the header chain is an descendant of what a particular peer has available.

A skip list is easy to add to the existing structure, and allows fast (O(log n)) access to far predecessor blocks.

The current code only uses it to speed up CChain::FindFork and CChain::GetLocator.

You sure this will increase performance? In practice, aren't header chains likely to be just a few blocks long?

If N is typically smaller than a few dozen I'd expect the simpler iterate-prev-pointers (and smaller, more cache-friendly CBlockIndex) to outperform any more complicated code.

Within minutes after starting IBD you'll have a header chain 300000 long, with a few 1000 long blockchain.

Anyway, I'm fine with waiting with this, and developing the code that uses it in parallel.

Just trying to cut it up in nice indidvidually-reviewable pieces.

Code changes look good to me.

This needs a unit test for BuildSkip/GetAncestor.

Added a unit test.

Including #4407 in this, so I don't need to maintain two independent branches and merge them for successor pull requests.

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/p4420_236982c2b6de619f0744c9c17ea7208b64a4afb3/ for binaries and test log. This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/ Contact BlueMatt on freenode if something looks broken.

@gavinandresen Just so there's no misunderstanding: currently this pull has nearly no benefit; I use the new functions where possible because they improve some worst case time and to give the code exposure, but it hardly matters for the current use sites.

The reason for adding is that in a successor patch I need it for finding the next blocks to fetch from a peer (which has a known tip), and there is no pnext pointer as different peers may have different ones. Alternatives are either:

• Building a CChain for each peer with their known blocks (which adds a few megabytes, and takes time to build); O(nBlocks * nPeers) memory cost but O(1) access cost.
• Not building any index structure, and walk back from the tip for each block to be requested, which means O(300000) iterations for every block during early IBD. 0 memory cost, but O(nBlocks) access cost.

A skiplist adds a O(nBlocks) memory cost, but O(log nBlocks) worst-case access cost, which seems a nice compromise.

Ok: code-reviewed-but-untested ACK.