util: add VecDeque

sipa commented at 5:21 pm on May 23, 2024: member

Extracted from #30126.

This adds a VecDeque data type, inspired by std::deque, but backed by a single allocated memory region used as a ring buffer instead of a linked list of arrays. This gives better memory locality and less allocation overhead, plus better guarantees (some C++ standard library implementations, though not libstdc++ and libc++, use a separate allocation per element in a deque).

It is intended for the candidate set search queue in #30126, but may be useful as a replacement for std::deque in other places too. It’s not a full drop-in replacement, as I did not add iteration support which is unnecessary for the intended use case, but nothing prevents adding that if needed.

Everything is tested through a simulation-based fuzz test that compares the behavior with normal std::deque equivalent operations, both for trivially-copyable/destructible types and others.

sipa added the label Utils/log/libs on May 23, 2024

in src/test/fuzz/ringbuffer.cpp:58 in 017272dff1 outdated

53+        }
54+    };
55+
56+    LIMITED_WHILE(provider.remaining_bytes(), MAX_OPERATIONS) {
57+        auto cmd_byte = provider.ConsumeIntegral<uint8_t>();
58+        unsigned idx = real.empty() ? 0 : (unsigned{cmd_byte} * real.size()) >> 8;

glozow commented at 2:31 pm on May 24, 2024:

nit: Seems like this would be easier?

0        unsigned idx = real.empty() ? 0 : provider.ConsumeIntegralInRange<unsigned>(0, real.size() - 1);

sipa commented at 4:42 pm on May 24, 2024:

“Integral in Rage” sounds like a high-school metal band.

sipa commented at 5:08 pm on May 24, 2024:

Done.

in src/test/fuzz/ringbuffer.cpp:61 in 017272dff1 outdated

56+    LIMITED_WHILE(provider.remaining_bytes(), MAX_OPERATIONS) {
57+        auto cmd_byte = provider.ConsumeIntegral<uint8_t>();
58+        unsigned idx = real.empty() ? 0 : (unsigned{cmd_byte} * real.size()) >> 8;
59+        int command = cmd_byte % 32;
60+        const size_t num_buffers = sim.size();
61+        // Loop until command reaches 0 (not all commands are always applicable, and this approach

glozow commented at 2:44 pm on May 24, 2024:

0        // Pick one operation based on value of command. Not all operations are always applicable.
1        // Loop through the applicable ones until command reaches 0 (avoids the need to compute
2        // the number of applicable commands ahead of time).

sipa commented at 5:08 pm on May 24, 2024:

Done.

in src/util/ringbuffer.h:34 in 017272dff1 outdated

29+    /** Number of objects in the container. m_size < m_capacity. */
30+    size_t m_size{0};
31+    /** The size of m_buffer, expressed as a multiple of the size of T. */
32+    size_t m_capacity{0};
33+
34+    inline size_t FirstPart() const noexcept { return std::min(m_capacity - m_offset, m_size); }

maflcko commented at 2:52 pm on May 24, 2024:

0    size_t FirstPart() const noexcept { return std::min(m_capacity - m_offset, m_size); }

style-nit: I think inline can be dropped, according to https://en.cppreference.com/w/cpp/language/inline

A function defined entirely inside a class/struct/union definition, whether it’s a member function or a non-member friend function, is implicitly an inline function […]

sipa commented at 3:37 pm on May 24, 2024:

Fixed.

inline does have an effect beyond making it an inline function (in GCC and Clang it increases the eagerness of the compiler to actually inline the function), but that’s the sort of optimization one should only do guided by benchmarks, which I haven’t done, so I dropped the inline here.

DrahtBot commented at 2:53 pm on May 24, 2024: contributor

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	cbergqvist, hebasto, instagibbs, glozow

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)

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.

in src/test/fuzz/ringbuffer.cpp:70 in 017272dff1 outdated

58+        unsigned idx = real.empty() ? 0 : (unsigned{cmd_byte} * real.size()) >> 8;
59+        int command = cmd_byte % 32;
60+        const size_t num_buffers = sim.size();
61+        // Loop until command reaches 0 (not all commands are always applicable, and this approach
62+        // avoids the need to compute the number of applicable commands ahead of time).
63+        while (true) {

glozow commented at 3:13 pm on May 24, 2024:

There’s an assumption that at least one of the operations is applicable every time. Pretty obviously true but I assigned variables to all the possible conditions while reviewing and used it to add an assertion. Might be easier to read so I figured I’d leave a comment.

0        const bool non_empty{num_buffers != 0};
1        const bool non_full{num_buffers < MAX_BUFFERS};
2        const bool partially_full{num_buffers > 0 && num_buffers < MAX_BUFFERS};
3        const bool multiple_exist{num_buffers > 1};
4        const bool existing_buffer_nonfull{non_empty && sim[idx].size() < MAX_BUFFER_SIZE};
5        const bool existing_buffer_nonempty{non_empty && !sim[idx].empty()};
6        assert(non_full || non_empty || partially_full);
7        
8        while (true) {

sipa commented at 5:08 pm on May 24, 2024:

Done.

in src/test/fuzz/ringbuffer.cpp:313 in 017272dff1 outdated

300+        for (size_t i = 0; i < Size; ++i) {
301+            assert(m_track_entry[i] == it);
302+        }
303+    }
304+
305+    void Register()

glozow commented at 3:31 pm on May 24, 2024:

0    // Create entry for this object in g_tracker and populate m_track_entry
1    void Register()

sipa commented at 5:09 pm on May 24, 2024:

Done.

in src/test/fuzz/ringbuffer.cpp:333 in 017272dff1 outdated

319+        for (size_t i = 0; i < Size; ++i) {
320+            m_track_entry[i] = g_tracker.end();
321+        }
322+    }
323+
324+    std::optional<uint64_t>& Deref()

glozow commented at 3:31 pm on May 24, 2024:

0    // Get value corresponding to this object in g_tracker
1    std::optional<uint64_t>& Deref()

sipa commented at 5:08 pm on May 24, 2024:

Done.

in src/test/fuzz/ringbuffer.cpp:404 in 017272dff1 outdated

399+    // Run the test with simple uints (which are std::is_trivially_copyable_v).
400+    TestType<uint8_t, false>(buffer, 1);
401+    TestType<uint16_t, false>(buffer, 2);
402+    TestType<uint32_t, false>(buffer, 3);
403+    TestType<uint64_t, false>(buffer, 4);
404+    // Run the test with TrackedObjs (which are not).

glozow commented at 3:32 pm on May 24, 2024:

static_assert(!std::is_trivially_copyable_v<TrackedObj<1>>) ?

sipa commented at 5:09 pm on May 24, 2024:

Done (and more).

sipa force-pushed on May 24, 2024

in src/util/ringbuffer.h:23 in c2a4915257 outdated

18+ * - Supports reserve(), capacity(), shrink_to_fit() like vectors.
19+ * - No iterator support.
20+ * - Data is not stored in a single contiguous block, so no data().
21+ */
22+template<typename T>
23+class RingBuffer

glozow commented at 3:57 pm on May 24, 2024:

I was slightly confused that this was called RingBuffer since the data structure itself doesn’t act like a ring buffer i.e. will reallocate if adding items beyond capacity (I wrote vExtraTxnForCompact to use it before looking at the implementation and then realized I misunderstood the interface). But I now have read that m_buffer is the ring buffer - oops.

sipa commented at 4:33 pm on May 24, 2024:

Hmm, this is a good point. The RingBuffer class’ interface isn’t a ring buffer, but a deque; the implementation happens to use a ring buffer. Suggestions/bikeshedding for a better name welcome.

theStack commented at 5:08 pm on May 24, 2024:

In Rust they call it VecDeque, maybe that’s a naming option? (It even rhymes!)

sipa commented at 5:32 pm on May 24, 2024:

Renamed!

sipa force-pushed on May 24, 2024

sipa renamed this:
~~util: add RingBuffer~~
util: add VecDeque
on May 24, 2024

sipa force-pushed on May 24, 2024

DrahtBot added the label CI failed on May 24, 2024

DrahtBot commented at 5:35 pm on May 24, 2024: contributor

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

Debug: https://github.com/bitcoin/bitcoin/runs/25390426376

in src/util/vecdeque.h:186 in f4d6f4a854 outdated

166+    VecDeque(const VecDeque& other) { *this = other; }
167+    VecDeque(VecDeque&& other) noexcept { swap(other); }
168+
169+    bool friend operator==(const VecDeque& a, const VecDeque& b)
170+    {
171+        if (a.m_size != b.m_size) return false;

theuni commented at 7:17 pm on May 24, 2024:

Could do (i think 3?) memcmp here if is_trivially_copyable_v, but maybe it’s not worth the complexity of differing offsets.

sipa commented at 7:19 pm on May 24, 2024:

Trivially copyable does not imply a trivial operator!=, I think.

theuni commented at 7:22 pm on May 24, 2024:

From https://en.cppreference.com/w/cpp/types/is_trivially_copyable: “Objects of trivially-copyable types that are not potentially-overlapping subobjects are the only C++ objects that may be safely copied with std::memcpy or serialized to/from binary files with std::ofstream::write() / std::ifstream::read().”

I assume anything that can be memcpy’d can be memcmp’d.

sipa commented at 7:31 pm on May 24, 2024:

I certainly see why it’s reasonable why trivial types would have a trivial comparison operator, but there is no guarantee for that. I think you can have a trivially-constructible type with an complex operator== (for such a type you’d expect that something that was memcpy’d you end up with a result that satisfies ==, but I don’t think that’s required, and it also doesn’t work the other way around: objects could satisfy == without being bitwise identical).

theuni commented at 7:34 pm on May 24, 2024:

Ok, yeah, agreed.

theuni commented at 9:14 pm on May 24, 2024:

Just adding for posterity because I went down a rabbit hole for this:

It seems clang’s __is_trivially_equality_comparable builtin would do what we want here:

Returns true if comparing two objects of the provided type is known to be equivalent to comparing their object representations. Note that types containing padding bytes are never trivially equality comparable.

From libc++:

0// A type is_trivially_equality_comparable if the expression `a == b` is equivalent to `std::memcmp(&a, &b, sizeof(T))`
1// (with `a` and `b` being of type `T`).

Not that it’s worth using here.

sipa commented at 9:56 pm on May 24, 2024:

Interesting!

DrahtBot removed the label CI failed on May 24, 2024

sipa force-pushed on May 25, 2024

sipa commented at 0:01 am on May 26, 2024: member

Apparently std::is_trivially_default_constructible_v<T> does not imply you can just memset 0 to construct the objects (or at least, I can’t find evidence of that). So I’ve dropped that branch.

hebasto added the label Needs CMake port on May 27, 2024

hebasto commented at 12:12 pm on May 27, 2024: member

Concept ACK.

hebasto commented at 12:59 pm on May 27, 2024: member

It’s not a full drop-in replacement…

Then, perhaps, it’s a good chance to avoid size_t for parameter and return types in the interface?

See: Signed and Unsigned Types in Interfaces

sipa commented at 4:04 pm on May 27, 2024: member

@hebasto I do prefer to stay compatible with the std::deque interface, even if just for matching behavior users would expect.

in src/util/vecdeque.h:29 in 82258f0fd0 outdated

24+{
25+    /** Pointer to allocated memory. Can contain constructed and uninitialized T objects. */
26+    T* m_buffer{nullptr};
27+    /** m_buffer + m_offset points to first object. m_offset < m_capacity. */
28+    size_t m_offset{0};
29+    /** Number of objects in the container. m_size < m_capacity. */

hebasto commented at 9:30 am on May 28, 2024:

nit:

0    /** Number of objects in the container. m_size <= m_capacity. */

sipa commented at 12:48 pm on May 28, 2024:

Fixed.

in src/util/vecdeque.h:39 in 82258f0fd0 outdated

34+    size_t FirstPart() const noexcept { return std::min(m_capacity - m_offset, m_size); }
35+
36+    void Reallocate(size_t capacity)
37+    {
38+        Assume(capacity >= m_size);
39+        Assume(m_capacity == 0 || m_offset < m_capacity);

hebasto commented at 9:55 am on May 28, 2024:

What is the purpose of this line here? It doesn’t look like a pre-condition for the function arguments. It seems it should be used as a post-condition for m_capacity mutators (including this function) and m_offset mutators, no?

sipa commented at 12:49 pm on May 28, 2024:

It’s an invariant, but it was poorly described, which I’ve hopefully addressed now (see m_offset docstring).

in src/util/vecdeque.h:58 in 82258f0fd0 outdated

52+            } else {
53+                // Otherwise move-construct in place in the new buffer, and destroy old buffer objects.
54+                size_t old_pos = m_offset;
55+                for (size_t new_pos = 0; new_pos < m_size; ++new_pos) {
56+                    std::construct_at<T>(new_buffer + new_pos, std::move(*(m_buffer + old_pos)));
57+                    std::destroy_at<T>(m_buffer + old_pos);

hebasto commented at 10:24 am on May 28, 2024:

Does it make sense to skip this call if std::is_trivially_destructible_v<T>?

sipa commented at 12:50 pm on May 28, 2024:

I don’t think so, since that case doesn’t let us avoid the loop.

in src/util/vecdeque.h:117 in 82258f0fd0 outdated

112+                ++m_size;
113+            }
114+        }
115+    }
116+
117+    void clear() { ResizeDown(0); }

hebasto commented at 10:33 am on May 28, 2024:

Both functions clear() and ResizeDown() could be declared noexcept.

sipa commented at 12:50 pm on May 28, 2024:

Good catch, done.

in src/util/vecdeque.h:139 in 82258f0fd0 outdated

123+    }
124+
125+    VecDeque& operator=(const VecDeque& other)
126+    {
127+        clear();
128+        Reallocate(other.m_size);

hebasto commented at 10:44 am on May 28, 2024:

The move assignment operator preserves the capacity. Maybe do the same here for consistency?

sipa commented at 12:52 pm on May 28, 2024:

I think it’s better to match std::vector behavior here (technically, spec doesn’t say anything about the capacity of a copied element, but common implementations make it just big enough to hold the copied data, I believe).

in src/test/fuzz/vecdeque.cpp:407 in 82258f0fd0 outdated

402+    }
403+};
404+
405+} // namespace
406+
407+FUZZ_TARGET(ringbuffer)

cbergqvist commented at 12:06 pm on May 28, 2024:

*FUZZ_TARGET(vecdeque)

sipa commented at 12:52 pm on May 28, 2024:

Fixed.

in src/test/fuzz/vecdeque.cpp:10 in 82258f0fd0 outdated

 5+#include <span.h>
 6+#include <test/fuzz/util.h>
 7+#include <test/util/xoroshiro128plusplus.h>
 8+#include <util/vecdeque.h>
 9+
10+#include <iostream>

cbergqvist commented at 12:13 pm on May 28, 2024:

Appears to be unused? Compiled without it on Clang.

sipa commented at 12:55 pm on May 28, 2024:

Fixed!

sipa force-pushed on May 28, 2024

in src/util/vecdeque.h:192 in 03cfb86736 outdated

187+    {
188+        if (m_capacity > m_size) Reallocate(m_size);
189+    }
190+
191+    template<typename U>
192+    void push_back(U&& elem)

hebasto commented at 2:50 pm on May 29, 2024:

Using this approach instead of two distinct signatures – void push_back(const T&) and void push_back(T&&) – can lead to some confusion in error messages.

Consider this:

 0struct A { int m_a{0}; } a;
 1struct B { int m_b{0}; } b;
 2
 3std::vector<A> v;
 4v.push_back(a);
 5// ERROR:
 6// no known conversion for argument 1 from ‘B’ to ‘const std::vector<A>::value_type&’ {aka ‘const A&’}
 7// no known conversion for argument 1 from ‘B’ to ‘std::vector<A>::value_type&&’ {aka ‘A&&’}
 8// v.push_back(b);  
 9
10
11VecDeque<A> vd;
12vd.push_back(a);
13// ERROR:
14// cannot convert ‘B’ to ‘int’ in initialization
15// vd.push_back(b);

sipa commented at 3:26 pm on May 29, 2024:

Your code here doesn’t use B anywhere, so I suspect the comments don’t match the code.

sipa commented at 7:58 pm on May 29, 2024:

I think I understand though; the argument to push_back or push_front should not be inferred but be fixed to be (a reference to) T. Done.

sipa force-pushed on May 29, 2024

in src/util/vecdeque.h:206 in a5a27bae11 outdated

198+    void push_back(const T& elem)
199+    {
200+        if (m_size == m_capacity) Reallocate((m_size + 1) * 2);
201+        std::construct_at(m_buffer + Index(m_size), std::move(elem));
202+        ++m_size;
203+    }

hebasto commented at 1:32 pm on May 30, 2024:

Does std::move(const T&) make sense here? The std::construct_at won’t be able to modify elem due to its constness, right?

sipa commented at 1:55 pm on May 30, 2024:

That depends on T’s move constructor. Typically, this won’t do anything, but it’s not impossible for a T::T(const T&&) constructor to exist (and this may make sense if T has mutable member variables).

sipa commented at 1:56 pm on May 30, 2024:

Actually, no, you’re right. Even if this does anything, it won’t be the desired behavior. Will remove.

sipa force-pushed on May 30, 2024

in src/util/vecdeque.h:213 in 0eba7219a2 outdated

183+        if (capacity > m_capacity) Reallocate(capacity);
184+    }
185+
186+    void shrink_to_fit()
187+    {
188+        if (m_capacity > m_size) Reallocate(m_size);

theuni commented at 3:27 pm on May 30, 2024:

It’s a shame that this triggers a reallocation when m_offset == 0. Might it be worth optimizing for that case?

theuni commented at 3:41 pm on May 30, 2024:

Actually, same comment for operator= as well. Maybe it’d be worth a special case in Reallocate() itself instead.

sipa commented at 3:44 pm on May 30, 2024:

Are you imagining something like realloc on the buffer? AFAIK that just doesn’t exist in C++; if you want to shrink an object, you need to construct a new object of smaller size and copy over.

theuni commented at 4:08 pm on May 30, 2024:

Grr, right.

hebasto approved

hebasto commented at 4:01 pm on May 30, 2024: member

ACK ecb278bb19c53b007380e262fa86d809255eeb49, I have reviewed the code and it looks OK.

It seems worth considering to add a couple of edge cases to the src/test/fuzz/vecdeque.cpp like self-assignment and self-swap.

in src/util/vecdeque.h:27 in 0eba7219a2 outdated

22+template<typename T>
23+class VecDeque
24+{
25+    /** Pointer to allocated memory. Can contain constructed and uninitialized T objects. */
26+    T* m_buffer{nullptr};
27+    /** m_buffer + m_offset points to first object. m_offset = 0 if m_capacity is 0; otherwise

instagibbs commented at 3:00 pm on June 4, 2024:

you can ignore this if you don’t like it

0    /** m_buffer + m_offset points to first object in queue. m_offset = 0 if m_capacity is 0; otherwise

sipa commented at 8:40 pm on June 4, 2024:

Done.

in src/util/vecdeque.h:73 in 0eba7219a2 outdated

68+        m_capacity = capacity;
69+        Assume((m_offset == 0 && m_capacity == 0) || m_offset < m_capacity);
70+    }
71+
72+    /** What index in the buffer does logical entry number pos have? */
73+    size_t Index(size_t pos) const noexcept

instagibbs commented at 4:19 pm on June 4, 2024:

s/Index/BufferIndex/ reduces my mental load fwiw

sipa commented at 8:40 pm on June 4, 2024:

Done.

in src/test/fuzz/vecdeque.cpp:180 in ecb278bb19 outdated

160+                size_t old_size = real[idx].size();
161+                size_t old_cap = real[idx].capacity();
162+                real[idx].push_back(*tmp);
163+                sim[idx].push_back(*tmp);
164+                assert(real[idx].size() == old_size + 1);
165+                if (old_cap > old_size) assert(real[idx].capacity() == old_cap);

instagibbs commented at 4:43 pm on June 4, 2024:

Putting bounds on the capacity growth seems useful here and a few other spots, even if it doesn’t necessarily have to be this tight.

0                if (old_cap > old_size) {
1                    assert(real[idx].capacity() == old_cap);
2                } else {
3                    assert(real[idx].capacity() > old_cap);
4                    assert(real[idx].capacity() <= 2 * (old_cap + 1));
5                }

sipa commented at 8:40 pm on June 4, 2024:

Done.

in src/test/fuzz/vecdeque.cpp:70 in ecb278bb19 outdated

65+        const bool multiple_exist{num_buffers > 1};
66+        const bool existing_buffer_non_full{non_empty && sim[idx].size() < MAX_BUFFER_SIZE};
67+        const bool existing_buffer_non_empty{non_empty && !sim[idx].empty()};
68+        assert(non_full || non_empty);
69+        while (true) {
70+            if (non_full && command-- == 0) {

instagibbs commented at 5:01 pm on June 4, 2024:

Calling compare_fn here seems more complete than picking and choosing when to call it before the final check

0            if (!real.empty()) compare_fn(real[idx], sim[idx]);
1            if (non_full && command-- == 0) {

sipa commented at 8:41 pm on June 4, 2024:

I didn’t take this suggestion. The current code should be invoking compare_fn whenever an element is destructed or destructively overwritten; that’s not necessarily number idx though.

in src/util/vecdeque.h:36 in 0eba7219a2 outdated

30+    /** Number of objects in the container. m_size <= m_capacity. */
31+    size_t m_size{0};
32+    /** The size of m_buffer, expressed as a multiple of the size of T. */
33+    size_t m_capacity{0};
34+
35+    size_t FirstPart() const noexcept { return std::min(m_capacity - m_offset, m_size); }

instagibbs commented at 5:35 pm on June 4, 2024:

gave an attempt

0    /** Returns the number of populated objects from m_offset to end of allocated memory. */
1    size_t FirstPart() const noexcept { return std::min(m_capacity - m_offset, m_size); }

sipa commented at 8:41 pm on June 4, 2024:

Done.

in src/util/vecdeque.h:48 in 0eba7219a2 outdated

42+        T* new_buffer = capacity ? std::allocator<T>().allocate(capacity) : nullptr;
43+        if (capacity) {
44+            if constexpr (std::is_trivially_copyable_v<T>) {
45+                // When T is trivially copyable, just copy the data over from old to new buffer.
46+                size_t first_part = FirstPart();
47+                if (first_part != 0) {

instagibbs commented at 5:42 pm on June 4, 2024:

double checking: first_part == 0 implies m_size == 0?

sipa commented at 8:04 pm on June 4, 2024:

Indeed!

sipa commented at 8:42 pm on June 4, 2024:

Added an Assume to reflect this.

sipa force-pushed on Jun 4, 2024

sipa commented at 6:15 pm on June 4, 2024: member

@hebasto Good idea, self copy-assignment was indeed broken! Fixed, and added tests for self copy/move/swap.

in src/util/vecdeque.h:129 in 5d06357207 outdated

124+        Reallocate(0);
125+    }
126+
127+    VecDeque& operator=(const VecDeque& other)
128+    {
129+        if (other.m_buffer == m_buffer) return *this;

instagibbs commented at 6:29 pm on June 4, 2024:

seems ever so slightly more direct, even though this seems correct as is

0        if (&other == this) return *this;

sipa commented at 8:41 pm on June 4, 2024:

Done.

theuni commented at 7:15 pm on June 4, 2024: member

@hebasto Good idea, self copy-assignment was indeed broken! Fixed, and added tests for self copy/move/swap.

I suspect this is probably broken in several of our other classes as well. Speaking for myself at least, I almost always forget about correctness there and never look for it in review.

FWIW I tried using the bugprone-unhandled-self-assignment clang-tidy check which does catch the problem, but it also throws a false-positive for this solution (as well as every other that I tried :( )

sipa commented at 7:30 pm on June 4, 2024: member

@theuni What if the comparison is changed to if (this == &other) return *this;?

instagibbs commented at 7:31 pm on June 4, 2024: member

reviewed through 9b04e8864b2807c94a03b9093cfa8c836d7c7116, but I need to look closer at the fuzz cases

theuni commented at 7:42 pm on June 4, 2024: member

if (this == &other) return *this;

Huh, that worked. But this (the one I tried) doesn’t

0if (*this == other) return *this;

Edit: facepalm

theuni commented at 7:46 pm on June 4, 2024: member

Oh, duh, that’s a totally different comparison. Ofc that didn’t do what I wanted :)

sipa force-pushed on Jun 4, 2024

sipa commented at 9:54 pm on June 4, 2024: member

Added a few missing compare_fn calls, and also added branches to the fuzz test to exercise pop_front() and pop_back(), which were apparently missing.

sipa force-pushed on Jun 4, 2024

in src/util/vecdeque.h:43 in e4ecb8217a outdated

38+    void Reallocate(size_t capacity)
39+    {
40+        Assume(capacity >= m_size);
41+        Assume((m_offset == 0 && m_capacity == 0) || m_offset < m_capacity);
42+        // Allocate new buffer.
43+        T* new_buffer = capacity ? std::allocator<T>().allocate(capacity) : nullptr;

hebasto commented at 8:29 am on June 5, 2024:

Would early return for capacity == 0 simplify the code?

sipa commented at 1:06 pm on June 5, 2024:

We may still need to deallocate the old buffer in that case.

instagibbs commented at 4:05 pm on June 5, 2024: member

ACK e4ecb8217ada3dae1c1645a8d0a12e14b0f935da

verified fuzz target coverage and sensible invariant checks are being enforced

DrahtBot requested review from hebasto on Jun 5, 2024

in src/util/vecdeque.h:130 in e4ecb8217a outdated

125+        Reallocate(0);
126+    }
127+
128+    VecDeque& operator=(const VecDeque& other)
129+    {
130+        if (&other == this) return *this;

hebasto commented at 3:22 pm on June 6, 2024:

Does it make sense to label branches with the [[likely]] and [[unlikely]] attributes here?

sipa commented at 5:40 pm on June 6, 2024:

Done.

in src/test/fuzz/vecdeque.cpp:442 in e4ecb8217a outdated

435+
436+    TrackedObj& operator=(const TrackedObj& other)
437+    {
438+        Deref() = other.Deref();
439+        return *this;
440+    }

hebasto commented at 3:25 pm on June 6, 2024:

This copy assignment can be amended to handle the self-assignment as well to do not conflict with #30234.

sipa commented at 5:40 pm on June 6, 2024:

Done, though naive self-assignment isn’t actually broken here. It’s just test code though, so better to be more obviously correct.

hebasto approved

hebasto commented at 3:25 pm on June 6, 2024: member

re-ACK e4ecb8217ada3dae1c1645a8d0a12e14b0f935da, I agree with changes since my recent review.

sipa force-pushed on Jun 6, 2024

sipa commented at 5:41 pm on June 6, 2024: member

I’ve added some doxygen comments on VecDeque.

sipa force-pushed on Jun 6, 2024

DrahtBot added the label CI failed on Jun 6, 2024

DrahtBot commented at 5:44 pm on June 6, 2024: contributor

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

Debug: https://github.com/bitcoin/bitcoin/runs/25906521916

sipa force-pushed on Jun 6, 2024

instagibbs commented at 6:52 pm on June 6, 2024: member

reACK https://github.com/bitcoin/bitcoin/pull/30161/commits/ee253ca7dea9bed01d4c1800760477ef06310df8

reviewed via git range-diff master e4ecb82 ee253ca

DrahtBot requested review from hebasto on Jun 6, 2024

hebasto approved

hebasto commented at 7:14 pm on June 6, 2024: member

re-ACK ee253ca7dea9bed01d4c1800760477ef06310df8, code deduplication using emplace_{back,front} is really nice.

in src/util/vecdeque.h:83 in ee253ca7de outdated

75+    {
76+        if (pos >= m_capacity - m_offset) {
77+            return pos - (m_capacity - m_offset);
78+        } else {
79+            return pos + m_offset;
80+        }

cbergqvist commented at 8:08 pm on June 6, 2024:

For me this is more straight forward:

0        if (m_offset + pos >= m_capacity) {
1            return (m_offset + pos) - m_capacity;
2        } else {
3            return m_offset + pos;
4        }

“We take where we begin now, m_offset, add pos to it and see what that means.” Subtractions hurt readability in this case.

sipa commented at 9:25 pm on June 6, 2024:

Done partially. if (m_offset + pos >= m_capacity) { might be wrong in the hypothetical case that m_offset + pos overflows (which would require a buffer larger than half of the address space…), so I’ve left a comment instead.

cbergqvist commented at 10:03 pm on June 6, 2024:

Excellent catch! I got a bit afraid that (m_offset + pos) - m_capacity might also run into issues when overflowing but appears to work out (and unsigned integer overflow is not undefined behavior).

in src/util/vecdeque.h:249 in ee253ca7de outdated

244+
245+    /** Remove the first element of the deque. Requires !empty(). */
246+    void pop_front()
247+    {
248+        Assume(m_size);
249+        std::destroy_at<T>(m_buffer + m_offset);

cbergqvist commented at 8:30 pm on June 6, 2024:

Since you removed <T> after construct_at:

0        std::destroy_at(m_buffer + m_offset);

sipa commented at 9:25 pm on June 6, 2024:

Done.

cbergqvist approved

cbergqvist commented at 8:37 pm on June 6, 2024: contributor

ACK ee253ca7dea9bed01d4c1800760477ef06310df8

DrahtBot removed the label CI failed on Jun 6, 2024

util: add VecDeque

This is an STL-like container that interface-wise looks like std::deque, but
is backed by a (fixed size, with vector-like capacity/reserve) circular buffer.

62fd24af6a

tests: add fuzz tests for VecDeque 7b8eea067f

in src/util/vecdeque.h:74 in ee253ca7de outdated

69+        m_capacity = capacity;
70+        Assume((m_offset == 0 && m_capacity == 0) || m_offset < m_capacity);
71+    }
72+
73+    /** What index in the buffer does logical entry number pos have? */
74+    size_t BufferIndex(size_t pos) const noexcept

cbergqvist commented at 8:41 pm on June 6, 2024:

Could do with an Assume(pos < m_capacity); as other cases are not handled.

sipa commented at 9:25 pm on June 6, 2024:

Done.

sipa force-pushed on Jun 6, 2024

cbergqvist approved

cbergqvist commented at 10:03 pm on June 6, 2024: contributor

re-ACK 7b8eea067f188c0b0e52ef21b01aedd37667a237

DrahtBot requested review from hebasto on Jun 6, 2024

DrahtBot requested review from instagibbs on Jun 6, 2024

hebasto approved

hebasto commented at 12:10 pm on June 7, 2024: member

re-ACK 7b8eea067f188c0b0e52ef21b01aedd37667a237, I’ve verified changes since my recent review with

0git range-diff master ee253ca7dea9bed01d4c1800760477ef06310df8 7b8eea067f188c0b0e52ef21b01aedd37667a237

instagibbs commented at 12:23 pm on June 7, 2024: member

reACK https://github.com/bitcoin/bitcoin/pull/30161/commits/7b8eea067f188c0b0e52ef21b01aedd37667a237

reviewed via git range-diff master ee253ca 7b8eea0

glozow commented at 1:21 pm on June 7, 2024: member

ACK 7b8eea067f

glozow merged this on Jun 7, 2024

glozow closed this on Jun 7, 2024

fanquake referenced this in commit 00feabf6c5 on Jul 11, 2024

hebasto commented at 6:55 am on July 14, 2024: member

Ported to the CMake-based build system in https://github.com/hebasto/bitcoin/pull/264.

hebasto removed the label Needs CMake port on Jul 14, 2024

util: add VecDeque #30161

Code Coverage

Reviews

Conflicts