test: Add test on skip heights in CBlockIndex #33661

75@@ -76,7 +76,7 @@ CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const
76 int static inline InvertLowestOne(int n) { return n & (n - 1); }
77 
78 /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
79-int static inline GetSkipHeight(int height) {
80+int GetSkipHeight(int height) {

46+    // The test collects and analyses the distribution of the
47+    // skip difference numbers, and checks some properties:
48+    // non-uniform distribution with most values small but
49+    // with some large values as well.
50+
51+    FastRandomContext ctx;

75@@ -76,7 +76,7 @@ CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const
76 int static inline InvertLowestOne(int n) { return n & (n - 1); }
77 
78 /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
79-int static inline GetSkipHeight(int height) {
80+int GetSkipHeight(int height) {
81     if (height < 2)

49+    BOOST_CHECK(GetSkipHeight(0b0001011101101001) == 0b0001011101000001);
50+    BOOST_CHECK(GetSkipHeight(0b0110101101011000) == 0b0110101101010000);
51+    BOOST_CHECK(GetSkipHeight(0b0110101101011001) == 0b0110101101000001);
52+    BOOST_CHECK(GetSkipHeight(0) == 0);
53+    BOOST_CHECK(GetSkipHeight(1) == 0);
54+    BOOST_CHECK(GetSkipHeight(2) == 0);

42@@ -41,6 +43,78 @@ const CBlockIndex* NaiveLastCommonAncestor(const CBlockIndex* a, const CBlockInd
43 
44 } // namespace
45 
46+BOOST_AUTO_TEST_CASE(get_skip_height_test)
47+{
48+    BOOST_CHECK(GetSkipHeight(0b0001011101101000) == 0b0001011101100000);

66+
67+BOOST_AUTO_TEST_CASE(skip_height_properties_test)
68+{
69+    // The test collects and analyses the distribution of the
70+    // skip difference numbers, and checks some properties:
71+    // non-uniform distribution with most values small but

88+        new_index->nHeight = new_index->pprev->nHeight + 1;
89+        new_index->BuildSkip();
90+        block_index.push_back(std::move(new_index));
91+    }
92+
93+    // Analyze the diff (in height) of each element and its pskip

93+    // Analyze the diff (in height) of each element and its pskip
94+    int count_diff_smaller_16 = 0;
95+    int max_diff = 0;
96+    int total_diff = 0;
97+    for(int i = 1; i < n; ++i) {
98+        BOOST_CHECK(block_index[i]->nHeight == i);

75+    std::vector<std::unique_ptr<CBlockIndex>> block_index;
76+
77+    // Create genesis block
78+    auto genesis = std::make_unique<CBlockIndex>();
79+    genesis->nHeight = 0;
80+    block_index.push_back(std::move(genesis));

78+    auto genesis = std::make_unique<CBlockIndex>();
79+    genesis->nHeight = 0;
80+    block_index.push_back(std::move(genesis));
81+
82+    // Build a chain
83+    const auto n{30000};

92+
93+    // Analyze the diff (in height) of each element and its pskip
94+    int count_diff_smaller_16 = 0;
95+    int max_diff = 0;
96+    int total_diff = 0;
97+    for(int i = 1; i < n; ++i) {

42@@ -41,6 +43,113 @@ const CBlockIndex* NaiveLastCommonAncestor(const CBlockIndex* a, const CBlockInd
43 
44 } // namespace
45 
46+BOOST_AUTO_TEST_CASE(get_skip_height_test)
47+{
48+    // Even values: the rightmost bit is zeroed
49+    // Test with variouse even values with at least 2 bits set

68+                                    0b0001011101000001);
69+    BOOST_CHECK_EQUAL(GetSkipHeight(0b0110101101011000),
70+                                    0b0110101101010000);
71+    BOOST_CHECK_EQUAL(GetSkipHeight(0b0110101101011001),
72+                                    0b0110101101000001);
73+    // All values 0--10

138+    // but general enough to be resilient to the exact test
139+    // details and algorithm
140+
141+    // The median skip diff is lower than the average
142+    BOOST_CHECK_LT(median, avg);
143+    // Most skip diffs are small (more than 67% are below 16):

130+        skip_diffs.push_back(i - skip_height);
131+    }
132+
133+    // Analyze the diffs
134+    // Compute the average
135+    const auto avg = double(std::accumulate(skip_diffs.begin(), skip_diffs.end(), 0)) / double(skip_diffs.size());

137+    std::ranges::sort(skip_diffs);
138+    const auto median{skip_diffs[n / 2]};
139+    // Take the maximum
140+    const auto max{skip_diffs[skip_diffs.size() - 1]};
141+
142+    // Assert some parameters of the distribution

134+    // Compute the average
135+    const auto avg = double(std::accumulate(skip_diffs.begin(), skip_diffs.end(), 0)) / double(skip_diffs.size());
136+    // Compute the median
137+    std::ranges::sort(skip_diffs);
138+    const auto median{skip_diffs[n / 2]};
139+    // Take the maximum

112+    block_index.push_back(std::make_unique<CBlockIndex>());
113+    // Build a chain
114+    for(int i{1}; i < n; ++i) {
115+        auto new_index = std::make_unique<CBlockIndex>();
116+        new_index->pprev = block_index.back().get();
117+        BOOST_CHECK(new_index->pprev);

75@@ -70,7 +76,7 @@ CBlockIndex* CChain::FindEarliestAtLeast(int64_t nTime, int height) const
76 int static inline InvertLowestOne(int n) { return n & (n - 1); }
77 
78 /** Compute what height to jump back to with the CBlockIndex::pskip pointer. */
79-int static inline GetSkipHeight(int height) {
80+int GetSkipHeight(int height) {

147+                                        heightSkipPrev >= target_height)))) {
148+                // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
149+                pindexWalk = pindexWalk->pskip;
150+                heightWalk = heightSkip;
151+            } else {
152+                assert(pindexWalk->pprev);

149+                pindexWalk = pindexWalk->pskip;
150+                heightWalk = heightSkip;
151+            } else {
152+                assert(pindexWalk->pprev);
153+                pindexWalk = pindexWalk->pprev;
154+                heightWalk--;

157+        }
158+
159+        // Asserts on the number of iterations:
160+        // always less than 100 and less than 5% of the distance
161+        BOOST_CHECK_LT(iteration_count, 100);
162+        BOOST_REQUIRE(delta > 0);

124+    const auto runs{1000};
125+    const auto min_distance{500};
126+    FastRandomContext ctx(/*fDeterministic =*/true);
127+    for (auto i{0}; i < runs; ++i) {
128+        // pick a height in the second half of the chain
129+        auto start_height = chain_size / 2 + ctx.randrange(chain_size / 2);

126+    FastRandomContext ctx(/*fDeterministic =*/true);
127+    for (auto i{0}; i < runs; ++i) {
128+        // pick a height in the second half of the chain
129+        auto start_height = chain_size / 2 + ctx.randrange(chain_size / 2);
130+        BOOST_REQUIRE(start_height > 0 && start_height < chain_size);
131+        auto& start_p = block_index[start_height];

57+                                    0b00010000);
58+    BOOST_CHECK_EQUAL(GetSkipHeight(0b00011000),
59+                                    0b00010000);
60+    BOOST_CHECK_EQUAL(GetSkipHeight(0b10101010),
61+                                    0b10101000);
62+    // Odd values: the 2nd and 3rd bits are zeroed

125+    const auto min_distance{500};
126+    FastRandomContext ctx(/*fDeterministic =*/true);
127+    for (auto i{0}; i < runs; ++i) {
128+        // pick a height in the second half of the chain
129+        auto start_height = chain_size / 2 + ctx.randrange(chain_size / 2);
130+        BOOST_REQUIRE(start_height > 0 && start_height < chain_size);

133+        auto delta{min_distance + ctx.randrange(start_height - min_distance)};
134+        auto target_height{start_height - delta};
135+        BOOST_REQUIRE(target_height > 0 && target_height < chain_size && target_height < start_height);
136+
137+        // Perform traversal from start to target, skipping, as implemented in `GetAncestor`
138+        const CBlockIndex* pindexWalk = start_p.get();

136+
137+        // Perform traversal from start to target, skipping, as implemented in `GetAncestor`
138+        const CBlockIndex* pindexWalk = start_p.get();
139+        auto heightWalk = start_height;
140+        auto iteration_count{0};
141+        while (heightWalk > target_height) {

155+            }
156+            ++iteration_count;
157+        }
158+
159+        // Asserts on the number of iterations:
160+        // always less than 100 and less than 5% of the distance

138+        const CBlockIndex* pindexWalk = start_p.get();
139+        auto heightWalk = start_height;
140+        auto iteration_count{0};
141+        while (heightWalk > target_height) {
142+            int heightSkip = GetSkipHeight(heightWalk);
143+            int heightSkipPrev = GetSkipHeight(heightWalk - 1);

162+        BOOST_REQUIRE(delta > 0);
163+        auto rel_iter_count = double(iteration_count) / double(delta);
164+        BOOST_CHECK_LT(rel_iter_count, 0.05);
165+
166+        // Since we are at it, we can also check that `GetAncestor` works
167+        // and gives the same result

121+        block_index.push_back(std::move(new_index));
122+    }
123+
124+    const auto runs{1000};
125+    const auto min_distance{500};
126+    FastRandomContext ctx(/*fDeterministic =*/true);

114+    block_index.push_back(std::make_unique<CBlockIndex>());
115+    for(auto i{1}; i < chain_size; ++i) {
116+        auto new_index{std::make_unique<CBlockIndex>()};
117+        new_index->pprev = block_index.back().get();
118+        BOOST_CHECK(new_index->pprev);
119+        new_index->nHeight = new_index->pprev->nHeight + 1;

159+        // Asserts on the number of iterations:
160+        // always less than 100 and less than 5% of the distance
161+        BOOST_CHECK_LT(iteration_count, 100);
162+        BOOST_REQUIRE(delta > 0);
163+        auto rel_iter_count = double(iteration_count) / double(delta);
164+        BOOST_CHECK_LT(rel_iter_count, 0.05);

109+    // Build a chain
110+    const auto chain_size{200'000};
111+    std::vector<std::unique_ptr<CBlockIndex>> block_index;
112+    block_index.reserve(chain_size);
113+    // Create genesis block
114+    block_index.push_back(std::make_unique<CBlockIndex>());

166+        // Since we are at it, we can also check that `GetAncestor` works
167+        // and gives the same result
168+        auto p_ancestor = start_p->GetAncestor(target_height);
169+        BOOST_CHECK_EQUAL(p_ancestor, block_index[target_height].get());
170+    }
171+}

143+            int heightSkipPrev = GetSkipHeight(heightWalk - 1);
144+            if (pindexWalk->pskip != nullptr &&
145+                (heightSkip == target_height ||
146+                (heightSkip > target_height && !(heightSkipPrev < heightSkip - 2 &&
147+                                        heightSkipPrev >= target_height)))) {
148+                // Only follow pskip if pprev->pskip isn't better than pskip->pprev.

120+        new_index->BuildSkip();
121+        block_index.push_back(std::move(new_index));
122+    }
123+
124+    const auto runs{1000};
125+    const auto min_distance{500};

119+        new_index->nHeight = new_index->pprev->nHeight + 1;
120+        new_index->BuildSkip();
121+        block_index.push_back(std::move(new_index));
122+    }
123+
124+    const auto runs{1000};

145+                (heightSkip == target_height ||
146+                (heightSkip > target_height && !(heightSkipPrev < heightSkip - 2 &&
147+                                        heightSkipPrev >= target_height)))) {
148+                // Only follow pskip if pprev->pskip isn't better than pskip->pprev.
149+                pindexWalk = pindexWalk->pskip;
150+                heightWalk = heightSkip;

102+    // and asserts that its properties are suitable for performant
103+    // ancestor search.
104+    // It does so by imitating the `GetAncestor` function to
105+    // look for an ancestor, and ensuring that an arbitrary
106+    // ancestor is found in a number of steps that is much lower
107+    // than simple linear traversal.

94+    BOOST_CHECK_EQUAL(GetSkipHeight(8), 0);
95+    BOOST_CHECK_EQUAL(GetSkipHeight(9), 1);
96+    BOOST_CHECK_EQUAL(GetSkipHeight(10), 8);
97+}
98+
99+BOOST_AUTO_TEST_CASE(skip_height_analysis)

108@@ -108,11 +109,11 @@ BOOST_AUTO_TEST_CASE(skip_height_analysis)
109         // End of copied traversal algorithm
110 
111         // Asserts on the number of iterations:
112-        // always less than 100 and less than 5% of the distance
113-        BOOST_CHECK_LT(iteration_count, 100);
114-        BOOST_REQUIRE_GT(delta, 0);
115-        const auto rel_iter_count{double(iteration_count) / double(delta)};
116-        BOOST_CHECK_LT(rel_iter_count, 0.05);
117+        // Absolute value maximum (derived empirically)

 8@@ -9,6 +9,8 @@
 9 
10 #include <memory>
11 
12+extern int GetSkipHeight(int height);

71@@ -71,11 +72,11 @@ BOOST_AUTO_TEST_CASE(skip_height_analysis)
72         block_index.push_back(std::move(new_index));
73     }
74 
75-    const auto min_distance{500};
76+    const auto min_distance{100};
77     FastRandomContext ctx(/*fDeterministic =*/true);
78     for (auto i{0}; i < 1'000; ++i) {
79         // pick a height in the second half of the chain

103+    // It does so by imitating the `CBlockIndex::GetAncestor()`
104+    // function to look for an ancestor, and ensuring that an arbitrary
105+    // ancestor is found in a number of steps that is much lower
106+    // than simple linear traversal.
107+    // This could be tested by a performance test as well, but here the
108+    // number of iterations can be measured, that gives a more precice

107+    // This could be tested by a performance test as well, but here the
108+    // number of iterations can be measured, that gives a more precice
109+    // metric than CPU time.
110+
111+    // Build a chain
112+    const int chain_size{1'000'000};

112+    const int chain_size{1'000'000};
113+    std::vector<std::unique_ptr<CBlockIndex>> block_index;
114+    block_index.reserve(chain_size);
115+    // Create genesis block
116+    block_index.push_back(std::make_unique<CBlockIndex>());
117+    for(auto i{1}; i < chain_size; ++i) {

45@@ -46,6 +46,7 @@ BOOST_AUTO_TEST_CASE(get_skip_height_test)
46 {
47     // Even values: the rightmost set bit is zeroed
48     // Test with various even values with at least 2 bits set
49+    // clang-format off

261+    // It does so by imitating the `CBlockIndex::GetAncestor()`
262+    // function to look for an ancestor, and ensuring that an arbitrary
263+    // ancestor is found in a number of steps that is much lower
264+    // than simple linear traversal.
265+    // This could be tested by a performance test as well, but here the
266+    // number of iterations can be measured, that gives a more precice

278+    constexpr auto min_distance{100};
279+    FastRandomContext ctx(/*fDeterministic =*/true);
280+    // Repeat iterations. The test should work with much higher numbers as well,
281+    // kept reasonable to keep execution time low
282+    for (auto i{0}; i < 1'000; ++i) {
283+        // pick a height in the second half of the chain