util: add BitSet #30160

sipa · 2024-05-23T15:42:28Z

Extracted from #30126.

This introduces the BitSet data structure, inspired by std::bitset, but with a few features that cannot be implemented on top without efficiency loss:

Finding the first set bit (First)
Finding the last set bit (Last)
Iterating over all set bits (begin and end).

And a few other operators/member functions that help readability for #30126:

operator- for set subtraction
Overlaps() for testing whether intersection is non-empty
IsSupersetOf() for testing (non-strict) supersetness
IsSubsetOf() for testing (non-strict) subsetness
Fill() to construct a set with all numbers from 0 to n-1, inclusive
Singleton() to construct a set with one specific element.

Everything is tested through a simulation-based fuzz test that compares the behavior with normal std::bitset equivalent operations.

DrahtBot · 2024-05-23T15:42:31Z

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

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	instagibbs, cbergqvist, theStack, achow101
Concept ACK	hebasto

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#30126 (Low-level cluster linearization code by sipa)
#29625 (Several randomness improvements by sipa)
#28676 ([WIP] Cluster mempool implementation by sdaftuar)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

src/util/bitset.h

cbergqvist

Looked at 3bc131a

Concept: Bummer that std::countr_zero and std::countl_zero aren't implemented for std::bitset. And for iterating it seems like one would be using std::vector<bool> and hoping for the best in terms of implementation. So makes sense to introduce BitSet.

Summary still mentions operator/ instead of operator-.

(Fuzz-code is too new to me to comment).

src/util/bitset.h

theStack

Concept ACK

src/util/bitset.h

sipa · 2024-05-29T15:46:03Z

Added additional Assume()s to prevent operator++ on iterators past the end:

--- a/src/util/bitset.h
+++ b/src/util/bitset.h
@@ -101,6 +101,7 @@ class IntBitSet
         /** Progress to the next 1 bit (only if != IteratorEnd). */
         constexpr Iterator& operator++() noexcept
         {
+            Assume(m_val != 0);
             m_val &= m_val - I{1U};
             if (m_val != 0) m_pos = std::countr_zero(m_val);
             return *this;
@@ -272,6 +273,7 @@ class MultiIntBitSet
         /** Progress to the next 1 bit (only if != IteratorEnd). */
         constexpr Iterator& operator++() noexcept
         {
+            Assume(m_idx < N);
             m_val &= m_val - I{1U};
             if (m_val == 0) {
                 while (true) {

src/test/fuzz/bitset.cpp

src/util/bitset.h

src/test/fuzz/bitset.cpp

hebasto · 2024-06-04T14:54:00Z

Concept ACK.

instagibbs · 2024-06-04T17:19:38Z

concept ACK

requested changes were included, will continue review

git range-diff master 18ec3fc c99063e

cbergqvist

ACK c99063e

(Ran git range-diff 3bc131a~2..3bc131a c99063e~2..c99063e).

src/util/bitset.h

instagibbs

c99063e seems to need swap fuzz coverage

rest of comments are nits

src/util/bitset.h

src/test/fuzz/bitset.cpp

src/util/bitset.h

instagibbs · 2024-06-07T15:49:30Z

src/util/bitset.h

+    constexpr void Reset(unsigned pos) noexcept
+    {
+        Assume(pos < MAX_SIZE);
+        m_val &= ~I(I{1U} << pos);


maybe just use conditional Set?

I haven't benchmarked or investigated compiled code, but I want to give the compiler every opportunity to use the simpler operation here (the conditional Set is more complex, and inlining will hopefully strength-reduce it, but I prefer not counting on that).

instagibbs · 2024-06-07T15:49:43Z

src/util/bitset.h

+        return *this;
+    }
+    /** Set a bit to 0. */
+    void constexpr Reset(unsigned pos) noexcept


maybe just use conditional Set?

Same reasoning as here

src/util/bitset.h

theStack

Reviewed 1e08ba3 so far, the code looks correct to me. Planning to review and run the fuzz test tomorrow.

src/util/bitset.h

This adds a bitset module that implements a BitSet<N> class, a variant of std::bitset with a few additional features that cannot be implemented in a wrapper without performance loss (specifically, finding first and last bit set, or iterating over all set bits).

sipa · 2024-06-10T11:56:02Z

Made a few small changes still:

@@ -107,7 +107,11 @@ class IntBitSet
             return *this;
         }
         /** Get the current bit position (only if != IteratorEnd). */
-        constexpr const unsigned& operator*() const noexcept { return m_pos; }
+        constexpr unsigned operator*() const noexcept
+        {
+            Assume(m_val != 0);
+            return m_pos;
+        }
     };
 
 public:
@@ -231,6 +235,8 @@ class MultiIntBitSet
     static constexpr unsigned LIMB_BITS = std::numeric_limits<I>::digits;
     /** Number of elements this set type supports. */
     static constexpr unsigned MAX_SIZE = LIMB_BITS * N;
+    // No overflow allowed here.
+    static_assert(MAX_SIZE / LIMB_BITS == N);
     /** Array whose member integers store the bits of the set. */
     std::array<I, N> m_val;
     /** Dummy type to return using end(). Only used for comparing with Iterator. */
@@ -293,7 +299,11 @@ class MultiIntBitSet
             return *this;
         }
         /** Get the current bit position (only if != IteratorEnd). */
-        constexpr const unsigned& operator*() const noexcept { return m_pos; }
+        constexpr unsigned operator*() const noexcept
+        {
+            Assume(m_idx < N);
+            return m_pos;
+        }
     };
 
 public:

instagibbs · 2024-06-10T13:26:22Z

ACK 47f705b

swap coverage added, some of the nits taken, and a couple Assume()s added

reviewed via git range-diff master c99063e 47f705b

cbergqvist

re-ACK 47f705b

Used same range-diff as instagibbs.

theStack

Code-review ACK 47f705b

achow101 · 2024-06-11T21:18:20Z

ACK 47f705b

hebasto · 2024-07-14T06:55:02Z

Ported to the CMake-based build system in hebasto#264.

DrahtBot added the Utils/log/libs label May 23, 2024

sipa mentioned this pull request May 23, 2024

cluster mempool: cluster linearization algorithm #30126

Merged

sipa force-pushed the 202405_bitset branch 2 times, most recently from 0505f4f to aeef8a4 Compare May 23, 2024 18:23

theuni reviewed May 23, 2024

View reviewed changes

src/util/bitset.h Outdated Show resolved Hide resolved

theuni reviewed May 23, 2024

View reviewed changes

src/util/bitset.h Outdated Show resolved Hide resolved

DrahtBot mentioned this pull request May 24, 2024

Several randomness improvements #29625

Merged

sipa force-pushed the 202405_bitset branch from aeef8a4 to d598c71 Compare May 24, 2024 13:48

theuni reviewed May 24, 2024

View reviewed changes

src/util/bitset.h Outdated Show resolved Hide resolved

sipa force-pushed the 202405_bitset branch 2 times, most recently from 692e533 to 3bc131a Compare May 25, 2024 22:07

hebasto added the Needs CMake port label May 27, 2024

cbergqvist reviewed May 28, 2024

View reviewed changes

src/util/bitset.h Show resolved Hide resolved

src/util/bitset.h Show resolved Hide resolved

src/util/bitset.h Outdated Show resolved Hide resolved

theStack reviewed May 28, 2024

View reviewed changes

src/util/bitset.h Outdated Show resolved Hide resolved

sipa force-pushed the 202405_bitset branch 2 times, most recently from f03f3fe to 18ec3fc Compare May 29, 2024 15:44

instagibbs reviewed Jun 3, 2024

View reviewed changes

src/test/fuzz/bitset.cpp Show resolved Hide resolved

src/test/fuzz/bitset.cpp Show resolved Hide resolved

src/util/bitset.h Show resolved Hide resolved

src/util/bitset.h Show resolved Hide resolved

instagibbs reviewed Jun 4, 2024

View reviewed changes

src/test/fuzz/bitset.cpp Outdated Show resolved Hide resolved

sipa force-pushed the 202405_bitset branch from 18ec3fc to c99063e Compare June 4, 2024 15:56

DrahtBot mentioned this pull request Jun 6, 2024

Cluster mempool implementation #28676

Open

8 tasks

cbergqvist approved these changes Jun 6, 2024

View reviewed changes

src/util/bitset.h Show resolved Hide resolved

DrahtBot requested review from instagibbs, theStack and hebasto June 6, 2024 19:29

instagibbs suggested changes Jun 7, 2024

View reviewed changes

DrahtBot requested a review from instagibbs June 7, 2024 16:07

sipa force-pushed the 202405_bitset branch from c99063e to a135ab9 Compare June 7, 2024 17:13

theStack reviewed Jun 10, 2024

View reviewed changes

src/util/bitset.h Outdated Show resolved Hide resolved

sipa added 2 commits June 10, 2024 07:54

util: add BitSet

59a6df6

This adds a bitset module that implements a BitSet<N> class, a variant of std::bitset with a few additional features that cannot be implemented in a wrapper without performance loss (specifically, finding first and last bit set, or iterating over all set bits).

tests: add fuzz tests for BitSet

47f705b

sipa force-pushed the 202405_bitset branch from a135ab9 to 47f705b Compare June 10, 2024 11:55

DrahtBot requested review from cbergqvist and theStack June 10, 2024 13:26

cbergqvist approved these changes Jun 10, 2024

View reviewed changes

theStack approved these changes Jun 10, 2024

View reviewed changes

achow101 merged commit 91e0bee into bitcoin:master Jun 11, 2024

fanquake mentioned this pull request Jun 12, 2024

fuzz: Use std::span in FuzzBufferType #30229

Merged

sipa mentioned this pull request Jun 14, 2024

Cluster mempool tracking issue #30289

Open

22 tasks

hebasto mentioned this pull request Jul 14, 2024

cmake: Regular rebasing of the cmake-staging branch hebasto/bitcoin#264

Closed

hebasto removed the Needs CMake port label Jul 14, 2024

bitcoin locked and limited conversation to collaborators Jul 14, 2025

util: add BitSet #30160

util: add BitSet #30160

Conversation

sipa commented May 23, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented May 23, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Code Coverage

Reviews

Conflicts

Uh oh!

Uh oh!

Uh oh!

Uh oh!

cbergqvist left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

theStack left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

sipa commented May 29, 2024

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

hebasto commented Jun 4, 2024

Uh oh!

instagibbs commented Jun 4, 2024

Uh oh!

cbergqvist left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

instagibbs left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

instagibbs Jun 7, 2024

Choose a reason for hiding this comment

Uh oh!

sipa Jun 7, 2024

Choose a reason for hiding this comment

Uh oh!

instagibbs Jun 7, 2024

Choose a reason for hiding this comment

Uh oh!

sipa Jun 7, 2024

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

theStack left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

sipa commented Jun 10, 2024

Uh oh!

instagibbs commented Jun 10, 2024

Uh oh!

cbergqvist left a comment

Choose a reason for hiding this comment

Uh oh!

theStack left a comment

Choose a reason for hiding this comment

Uh oh!

achow101 commented Jun 11, 2024

Uh oh!

hebasto commented Jul 14, 2024

Uh oh!

sipa commented May 23, 2024 •

edited

Loading

DrahtBot commented May 23, 2024 •

edited

Loading