Make FindBlockByHeight constant-time #2644
Conversation
Remove the pnext pointer in CBlockIndex, and replace it with a vBlockIndexByHeight vector (no effect on memory usage). pnext can now be replaced by vBlockIndexByHeight[nHeight+1], but FindBlockByHeight becomes constant-time. This also means the entire mapBlockIndex structure and the block index entries in it become purely blocktree-related data, and independent from the currently active chain, potentially allowing them to be protected by separate mutexes in the future.
|
Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/0fe8010a10bafd67f9131b2da034fb9cd7fc5024 for binaries and test log. |
|
Code looks sane and ACK-worthy. The concept is similar to something I did in pynode. Did you actually instrument "no effect on memory usage", or is that a guess? I would like to see before and after numbers proving that :) |
|
@jgarzik Just reasoning. For each CBlockIndex representing a node in the active chain, we remove 8 bytes from the CBlockIndex, and add 8 bytes to vBlockIndexByHeight. Actually, it should reduce memory usage slightly, as non-best-chain nodes also lose 8 bytes. |
Make FindBlockByHeight constant-time
3 participants
Remove the pnext pointer in CBlockIndex, and replace it with a vBlockIndexByHeight vector (no effect on memory usage). pnext can now be replaced by vBlockIndexByHeight[nHeight+1], but FindBlockByHeight becomes constant-time.
This also means the entire mapBlockIndex structure and the block index entries in it become purely blocktree-related data, and independent from the currently active chain, potentially allowing them to be protected by separate mutexes in the future.