prevector: simplify operator==

purpleKarrot commented at 2:23 pm on November 3, 2025: contributor

The reduced amount of code reduces maintenance.

DrahtBot commented at 2:23 pm on November 3, 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/33772.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	l0rinc, sedited, stickies-v, maflcko

If your review is incorrectly listed, please copy-paste <!–meta-tag:bot-skip–> into the comment that the bot should ignore.

Conflicts

No conflicts as of last run.

fanquake commented at 3:23 pm on November 3, 2025: member

As indicated by the CI, the macOS SDK we are targeting doesn’t (yet) support lexicographical_compare_three_way. A Guix build will fail the same way:

 0In file included from /distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/chainparams.cpp:6:
 1In file included from /distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/chainparams.h:9:
 2In file included from /distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/kernel/chainparams.h:11:
 3In file included from /distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/primitives/block.h:9:
 4In file included from /distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/primitives/transaction.h:12:
 5In file included from /distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/script/script.h:11:
 6/distsrc-base/distsrc-21318e8b5df5-arm64-apple-darwin/src/prevector.h:446:21: error: no member named 'lexicographical_compare_three_way' in namespace 'std'; did you mean 'lexicographical_compare'?
 7  446 |         return std::lexicographical_compare_three_way(begin(), end(), other.begin(), other.end());
 8      |                ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 9      |                     lexicographical_compare
10/root/SDKs/Xcode-15.0-15A240d-extracted-SDK-with-libcxx-headers/usr/include/c++/v1/__algorithm/lexicographical_compare.h:42:1: note: 'lexicographical_compare' declared here
11   42 | lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
12      | ^

DrahtBot added the label CI failed on Nov 3, 2025

purpleKarrot force-pushed on Nov 3, 2025

DrahtBot removed the label CI failed on Nov 3, 2025

stickies-v commented at 11:19 pm on November 3, 2025: contributor

I like the idea, and it would be an improvement to both simplify the prevector implementation and move it closer to being a std::vector drop-in. However, the different operator< implementation has a lot of potential behaviour change (not just direct comparison such as in CNoDestination::operator<, but also in e.g. all maps and sets of CScript), and assuring myself the changes are safe is going to take more time than seems worth it for the stated benefits. So: Concept ACK, but Priority NACK for me.

laanwj added the label Utils/log/libs on Nov 4, 2025

DrahtBot added the label Needs rebase on Dec 8, 2025

maflcko commented at 11:22 am on February 2, 2026: member

are you still working on this?

purpleKarrot force-pushed on Feb 3, 2026

purpleKarrot commented at 10:00 pm on February 3, 2026: contributor

are you still working on this? @maflcko, I have rebased on master and removed the fallback for lexicographical_compare_three_way. The first commit should not be controversial; only the second one involves a breaking change. Do you want me to split the PR in two?

DrahtBot removed the label Needs rebase on Feb 3, 2026

DrahtBot added the label CI failed on Feb 3, 2026

DrahtBot removed the label CI failed on Feb 4, 2026

maflcko commented at 9:22 am on February 4, 2026: member

Yeah, I guess you can split up the first commit

fanquake commented at 1:49 pm on March 4, 2026: member

@purpleKarrot are you planning on doing the split / just dropping the second commit from this PR?

prevector: simplify `operator==` 2678abe902

purpleKarrot force-pushed on Mar 4, 2026

purpleKarrot renamed this:
~~prevector: simplify implementation of comparison operators and match behavior of `std::vector`~~
prevector: simplify operator==
on Mar 4, 2026

purpleKarrot commented at 2:13 pm on March 4, 2026: contributor

@fanquake, @stickies-v, I have dropped the controversial commit.

in src/prevector.h:430 in 2678abe902

440-            ++b1;
441-            ++b2;
442-        }
443-        return true;
444+    constexpr bool operator==(const prevector& other) const {
445+        return std::ranges::equal(*this, other);

l0rinc commented at 2:25 pm on March 4, 2026:

We don’t seem to have proper unit tests for this, prevector_tests passes with:

0constexpr bool operator==(const prevector& other) const { return true; }

Can you please add a unit test commit before the change that exercises the current behavior, and a second commit that changes the implementation without changing the tests? Maybe something simple like:

 0diff --git a/src/test/prevector_tests.cpp b/src/test/prevector_tests.cpp
 1--- a/src/test/prevector_tests.cpp	(revision 2678abe902c69ab5af5450d6fdf40ead834b1e26)
 2+++ b/src/test/prevector_tests.cpp	(date 1772635055198)
 3@@ -313,4 +313,21 @@
 4     }
 5 }
 6 
 7+BOOST_AUTO_TEST_CASE(PrevectorEqualityRegression)
 8+{
 9+    using pretype = prevector<8, int>;
10+
11+    const pretype empty{};
12+    const pretype one_a{1, 42};
13+    const pretype one_b{1, 42};
14+    const pretype one_c{1, 43};
15+    const pretype two{2, 42}; // Same prefix as one_a, but longer.
16+
17+    BOOST_CHECK((empty == empty) && !(empty != empty));
18+    BOOST_CHECK((one_a == one_b) && !(one_a != one_b));
19+    BOOST_CHECK(!(empty == one_a) && (empty != one_a));
20+    BOOST_CHECK(!(one_a == one_c) && (one_a != one_c));
21+    BOOST_CHECK(!(one_a == two) && (one_a != two));
22+}
23+
24 BOOST_AUTO_TEST_SUITE_END()

I was curious about the performance, so I added a local benchmark (I don’t think we should commit this, though). I was expecting the new version to perform better:

 0diff --git a/src/bench/prevector.cpp b/src/bench/prevector.cpp
 1--- a/src/bench/prevector.cpp	(revision 01dcb2fcc5834071eb3cc1c1ad2f8c931d80e741)
 2+++ b/src/bench/prevector.cpp	(revision 61567d548957ea3167088347b9db8332102522d1)
 3@@ -5,11 +5,16 @@
 4 #include <prevector.h>
 5 
 6 #include <bench/bench.h>
 7+#include <random.h>
 8 #include <script/script.h>
 9 #include <serialize.h>
10 #include <streams.h>
11+#include <util/check.h>
12 
13+#include <algorithm>
14+#include <cstdint>
15 #include <type_traits>
16+#include <utility>
17 #include <vector>
18 
19 struct nontrivial_t
20@@ -111,6 +116,71 @@
21     });
22 }
23 
24+static void PrevectorEqualScriptMix(benchmark::Bench& bench)
25+{
26+    static constexpr size_t BASE_SCRIPTS{2048};
27+    static constexpr size_t DUPLICATES{256};
28+    static constexpr size_t PREFIX_VARIANTS{256};
29+    static constexpr size_t RANDOM_COMPARISONS{4096};
30+
31+    FastRandomContext rng{/*fDeterministic=*/true};
32+    std::vector<CScriptBase> scripts;
33+    scripts.reserve(BASE_SCRIPTS + DUPLICATES + PREFIX_VARIANTS);
34+
35+    for (size_t i = 0; i < BASE_SCRIPTS; ++i) {
36+        const size_t size = 4 + rng.randrange(257);
37+        CScriptBase script(size, 0);
38+        for (auto& byte : script) byte = rng.randbits(8);
39+        // Stamp with a unique id so base scripts are distinct.
40+        script[size - 4] = static_cast<uint8_t>(i);
41+        script[size - 3] = static_cast<uint8_t>(i >> 8);
42+        script[size - 2] = static_cast<uint8_t>(i >> 16);
43+        script[size - 1] = static_cast<uint8_t>(i >> 24);
44+        scripts.emplace_back(std::move(script));
45+    }
46+
47+    std::vector<std::pair<size_t, size_t>> comparisons;
48+    comparisons.reserve(DUPLICATES + PREFIX_VARIANTS + RANDOM_COMPARISONS);
49+
50+    for (size_t i = 0; i < DUPLICATES; ++i) {
51+        const size_t src_idx = (i * 13) % BASE_SCRIPTS;
52+        const size_t dup_idx = scripts.size();
53+        scripts.push_back(scripts[src_idx]);
54+        comparisons.emplace_back(src_idx, dup_idx);
55+    }
56+
57+    for (size_t i = 0; i < PREFIX_VARIANTS; ++i) {
58+        const size_t src_idx = (i * 29) % BASE_SCRIPTS;
59+        const CScriptBase& src = scripts[src_idx];
60+        const size_t trim = std::min<size_t>(src.size() - 1, 1 + (i % 8));
61+        const size_t prefix_size = src.size() - trim;
62+        const size_t prefix_idx = scripts.size();
63+        scripts.emplace_back(src.begin(), src.begin() + prefix_size);
64+        comparisons.emplace_back(src_idx, prefix_idx);
65+    }
66+
67+    for (size_t i = 0; i < RANDOM_COMPARISONS; ++i) {
68+        const size_t lhs = rng.randrange(BASE_SCRIPTS);
69+        size_t rhs = rng.randrange(BASE_SCRIPTS);
70+        if (rhs == lhs) rhs = (rhs + 1) % BASE_SCRIPTS;
71+        comparisons.emplace_back(lhs, rhs);
72+    }
73+
74+    const auto count_equal_pairs = [&] {
75+        size_t true_count{0};
76+        for (const auto& [lhs_idx, rhs_idx] : comparisons) {
77+            true_count += scripts[lhs_idx] == scripts[rhs_idx];
78+        }
79+        return true_count;
80+    };
81+    const size_t expected_true{DUPLICATES};
82+
83+    bench.batch(comparisons.size()).run([&] {
84+        const size_t true_count{count_equal_pairs()};
85+        Assert(true_count == expected_true);
86+    });
87+}
88+
89 #define PREVECTOR_TEST(name)                                         \
90     static void Prevector##name##Nontrivial(benchmark::Bench& bench) \
91     {                                                                \
92@@ -129,3 +199,4 @@
93 PREVECTOR_TEST(Deserialize)
94 PREVECTOR_TEST(FillVectorDirect)
95 PREVECTOR_TEST(FillVectorIndirect)
96+BENCHMARK(PrevectorEqualScriptMix);

Before

ns/op	op/s	err%	total	benchmark
3.29	304,289,453.44	0.3%	1.10	`PrevectorEqualScriptMix`

After

ns/op	op/s	err%	total	benchmark
0.86	1,166,437,816.26	0.2%	1.10	`PrevectorEqualScriptMix`

l0rinc approved

l0rinc commented at 2:58 pm on March 4, 2026: contributor

Tested ACK 2678abe902c69ab5af5450d6fdf40ead834b1e26

I would prefer adding a unit test for this so that we don’t just rely on fuzzers. The speedup is a nice (and expected) bonus.

sedited approved

sedited commented at 4:04 pm on March 4, 2026: contributor

ACK 2678abe902c69ab5af5450d6fdf40ead834b1e26

stickies-v approved

stickies-v commented at 1:21 am on March 5, 2026: contributor

ACK 2678abe902c69ab5af5450d6fdf40ead834b1e26

Double checked that prevector iterators models the std::sized_sentinel_for concept so that the size optimization isn’t lost.

 0diff --git a/src/prevector.h b/src/prevector.h
 1index 91be488039..5cad83ba89 100644
 2--- a/src/prevector.h
 3+++ b/src/prevector.h
 4@@ -103,6 +103,9 @@ public:
 5         auto operator<=>(const_iterator x) const { return ptr <=> x.ptr; }
 6     };
 7 
 8+    static_assert(std::sized_sentinel_for<iterator, iterator>);
 9+    static_assert(std::sized_sentinel_for<const_iterator, const_iterator>);
10+
11 private:
12 #pragma pack(push, 1)
13     union direct_or_indirect {

maflcko added this to the milestone 32.0 on Mar 5, 2026

maflcko commented at 7:54 am on March 5, 2026: member

lgtm ACK 2678abe902c69ab5af5450d6fdf40ead834b1e26

I’ve scheduled this for after the branch-off (in about 5 days) for now

sedited merged this on Mar 11, 2026

sedited closed this on Mar 11, 2026

prevector: simplify operator== #33772

Code Coverage & Benchmarks

Reviews

Conflicts