Improve LastCommonAncestor performance + add tests #33515

1. 
   sipa commented at 6:06 pm on October 1, 2025: member

   In theory, the LastCommonAncestor function in chain.cpp can take $\mathcal{O}(n)$ time, walking over the entire chain, if the forking point is very early, which could take ~milliseconds. I expect this to be very rare in normal occurrences, but it seems nontrivial to reason about worst cases as it’s accessible from several places in net_processing.

   This PR modifies the algorithm to make use of the CBlockIndex::pskip skip pointers to find the forking point in sublinear time (a simulation shows that for heights up to $34 \cdot 4^k - 2$ and $k \geq 8$, no more than $k^2 + 10k + 13$ steps are ever needed), in a way that should be nearly free - at worst the same number of memory accesses should be made, with a tiny increase in computation.

   As it appears we didn’t really have tests for this function, unit tests are added for that function as well as CBlockIndex::GetAncestor().

   This is inspired by #32180 (review)

2. 
   DrahtBot commented at 6:06 pm on October 1, 2025: contributor

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

   Code Coverage & Benchmarks

   For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/33515.

   Reviews

   See the guideline for information on the review process.

   Type	Reviewers
   ACK	vasild, mzumsande, furszy, optout21, stratospher, achow101

   If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

3. sipa force-pushed on Oct 1, 2025
4. 
   furszy commented at 7:15 pm on October 1, 2025: member

   Code review ACK 4fe3de2
5. in src/chain.cpp:177 in 4fe3de2aa7 outdated

   171+        // Jump back until pa and pb have a common "skip" ancestor.
   172+        while (pa->pskip != pb->pskip) {
   173+            Assume(pa->nHeight == pb->nHeight);
   174+            pa = pa->pskip;
   175+            pb = pb->pskip;
   176+        }
   

   ---

   ---

   

   vasild commented at 1:12 pm on October 2, 2025:

   This assumes that all blocks at the same height have equal pskip height. This is true currently, but if changed, then this code will trigger the Assume in debug and will do null pointer dereference in release builds. Looking at GetSkipHeight(), it derives its result deterministically from height only (good).

   Is it worth here, if pa->pskip->nHeight != pb->pskip->nHeight, then to fall back to one-by-one iterating?

   ---

   

   sipa commented at 2:03 pm on October 2, 2025:

   I don’t think so - that eventuality (pskip depending on more than just height) is dealt with through the Assume(). I guess I can add a comment to clarify that.
6. in src/test/chain_tests.cpp:21 in 4fe3de2aa7

   16+const CBlockIndex* NaiveGetAncestor(const CBlockIndex* a, int height)
   17+{
   18+    while (a->nHeight > height) {
   19+        a = a->pprev;
   20+    }
   21+    BOOST_CHECK_EQUAL(a->nHeight, height);
   

   ---

   ---

   

   vasild commented at 1:14 pm on October 2, 2025:

   nit: I guess that if this check fails, then the test should be interrupted without performing further checks. If so, maybe use BOOST_REQUIRE_EQUAL()?

   ---

   

   sipa commented at 2:34 pm on October 2, 2025:

   Done.
7. in src/test/chain_tests.cpp:34 in 4fe3de2aa7

   29+    }
   30+    while (b->nHeight > a->nHeight) {
   31+        b = b->pprev;
   32+    }
   33+    while (a != b) {
   34+        BOOST_CHECK_EQUAL(a->nHeight, b->nHeight);
   

   ---

   ---

   

   vasild commented at 1:15 pm on October 2, 2025:

   nit: similar as above: BOOST_REQUIRE_EQUAL()?

   ---

   

   sipa commented at 2:34 pm on October 2, 2025:

   Done.
8. in src/test/chain_tests.cpp:38 in 4fe3de2aa7

   33+    while (a != b) {
   34+        BOOST_CHECK_EQUAL(a->nHeight, b->nHeight);
   35+        a = a->pprev;
   36+        b = b->pprev;
   37+    }
   38+    BOOST_CHECK(a == b);
   

   ---

   ---

   

   vasild commented at 1:17 pm on October 2, 2025:

   nit: similar as above: BOOST_REQUIRE(a == b) or BOOST_REQUIRE_EQUAL(a, b)

   ---

   

   sipa commented at 2:34 pm on October 2, 2025:

   Done.
9. 
   vasild commented at 1:27 pm on October 2, 2025: contributor

   Approach ACK 4fe3de2aa7fda58d5c56987aee13ae87191da1c6
10. tests: add unit tests for CBlockIndex::GetAncestor and LastCommonAncestor 2e09d66fbb
11. chain: make use of pskip in LastCommonAncestor (optimization)

    By using the pskip pointer, which regularly allows jumping back much faster
    than pprev, the forking point between two CBlockIndex entries can be found
    much faster.
    
    A simulation shows that no more than 136 steps are needed to jump anywhere
    within the first 2^20 block heights, and on average 65 jumps for uniform
    forking points around that height.

    3635d62f5a
12. sipa force-pushed on Oct 2, 2025
13. vasild approved
14. 
    vasild commented at 8:59 am on October 3, 2025: contributor

    ACK 3635d62f5a935801e26a0d5fa2cb5e2dbbb42f9b
15. DrahtBot requested review from furszy on Oct 3, 2025
16. in src/chain.cpp:174 in 3635d62f5a

    171+        // Jump back until pa and pb have a common "skip" ancestor.
    172+        while (pa->pskip != pb->pskip) {
    173+            // This logic relies on the property that equal-height blocks have equal-height skip
    174+            // pointers.
    175+            Assume(pa->nHeight == pb->nHeight);
    176+            Assume(pa->pskip->nHeight == pb->pskip->nHeight);
    

    ---

    ---

    

    mzumsande commented at 6:56 pm on October 3, 2025:

    If I understand it correctly, we don’t have to worry about dereferencing a nullptr here, because pskip is only nullptr for genesis, and if one of the blocks was genesis, we couldn’t get to this spot.
17. 
    mzumsande commented at 6:59 pm on October 3, 2025: contributor

    Code Review ACK 3635d62f5a935801e26a0d5fa2cb5e2dbbb42f9b The added test is slightly faster with the changes.

    I expect this to be very rare in normal occurrences, but it seems nontrivial to reason about worst cases as it’s accessible from several places in net_processing.

    I think it would require really long forked chains for this to become relevant, so basically in consensus split scenarios?!

18. 
    furszy commented at 3:25 pm on October 5, 2025: member

    ACK 3635d62f5a935801e26a0d5fa2cb5e2dbbb42f9b
19. in src/chain.cpp:173 in 3635d62f5a

    182         pa = pa->pprev;
    183         pb = pb->pprev;
    184     }
    185-
    186-    // Eventually all chain branches meet at the genesis block.
    187-    assert(pa == pb);
    

    ---

    ---

    

    optout21 commented at 11:53 am on October 6, 2025:

    Why remove this? Is it just too obvious after the while (pa != pb)?
20. in src/chain.cpp:172 in 3635d62f5a

    169-    while (pa != pb && pa && pb) {
    170+    while (pa != pb) {
    171+        // Jump back until pa and pb have a common "skip" ancestor.
    172+        while (pa->pskip != pb->pskip) {
    173+            // This logic relies on the property that equal-height blocks have equal-height skip
    174+            // pointers.
    

    ---

    ---

    

    optout21 commented at 11:54 am on October 6, 2025:

    I think what is meant here is that equal-height blocks have equal-height skip values, the pointer can be different (if on different forks). I suggest changing to “height skip values”
21. 
    optout21 commented at 12:26 pm on October 6, 2025: none

    ACK 3635d62f5a935801e26a0d5fa2cb5e2dbbb42f9b

    With the new chain_test test, this optimization reduces the number of steps in LastCommonAncestor by at least 5-fold (e.g. from 5898713 to 1119703), an obvious optimization. However, timing the tests (pre and post optimization) I could not measure a difference. I’ve left two non-blocking nit comments.

22. 
    optout21 commented at 12:36 pm on October 6, 2025: none

    However, timing the tests (pre and post optimization) I could not measure a difference.

    Most of the CPU time in the test is taken by the NaiveGetAncestor and NaiveLastCommonAncestor naive implementations. Taken out calls to those, I have measured a 47% speedup in the execution of the test (user time).

23. 
    stratospher commented at 1:44 pm on October 7, 2025: contributor

    ACK 3635d62f5a935801e26a0d5fa2cb5e2dbbb42f9b.

    Seems to work better when there are fewer but deeper forks.

    Got this when running each LCA algorithm 10,000 times on the same block pairs in the same block constellation:

    • No forks - kind of same LastCommonAncestor : 962us NaiveLastCommonAncestor : 986us

    • 0.1% forks - 18x slower LastCommonAncestor : 1103us NaiveLastCommonAncestor : 20481us

    • 0.5% forks - 11x slower LastCommonAncestor : 1030us NaiveLastCommonAncestor : 11591us

    • 1% forks - 8x slower LastCommonAncestor : 1023us NaiveLastCommonAncestor : 8580us

    • 5% forks - 3.44x slower LastCommonAncestor : 781us NaiveLastCommonAncestor : 2688us

    Though it doesn’t matter much since deep forks are a rare scenario.

24. 
    achow101 commented at 8:45 pm on October 7, 2025: member

    ACK 3635d62f5a935801e26a0d5fa2cb5e2dbbb42f9b
25. achow101 merged this on Oct 7, 2025
26. achow101 closed this on Oct 7, 2025

    ---

Contributors
sipa DrahtBot furszy vasild mzumsande optout21 stratospher achow101