4
\$\begingroup\$

I'm in need of a simple wrapper for a fixed-size std::vector that can ensure atomic insertion.

Since my only real problem is with atomic insertion and I know beforehand the amount of entries it will have, I don't need any other parallelism related feature.

I am happy to have the initial allocation (std::vector::resize) run from the main thread, so it shouldn't need anything fancy.

Although there are great, free to use parallel vectors available, I think that my particular use case, being fixed size shouldn't require any fancy library (e.g. TBB).

I was thinking about something along these lines:

template <typename T>
class AtomicFixedSizeVector {
public:

    // a bunch of passthrough methods here...

    inline void reserve(size_t count) {
        m_data.resize(count);
        //m_data.reserve(count);
    }

    inline void push_back(const T& entry) {
        size_t index = m_count.fetch_add(1, std::memory_order_relaxed);
        m_data[index] = entry;
    }

    // I don't think I need this at all, but just in case
    inline size_t size()const {
        return m_count.load(std::memory_order_relaxed);
    }

private:
    std::vector<T> m_data;
    std::atomic<size_t> m_count;
};

It needs to be a wrapper to std::vector since the other parts of code take one.

I thought I'd ask this question as my knowledge of atomics is rather limited, and although it seems ok when executed, it's hard to tell if it's actually going well or I'm being lucky multiple times in a row.

Another question that I have is if I can trust std::vector::reserve to do the allocation on the spot or if it's implementation-dependent. I'm asking because if it allocates on the spot I don't need to override the behavior of std::vector::size and can use a passthrough wrapper there, too.

Please note that this is not a premature optimization but rather a post-mortem one, my insertion could be parallelized but only if it ends up adding onto a single block of entries.

This std::vector block of entries will only store uint32_t in case it helps.


Edit:

The current use case is to insert from multiple threads, but this was designed knowing beforehand that by the time the data is accessed, the threads will have been joined.

There is an upper limit on the amount of values to be inserted so the vector will be preallocated before insertion.

\$\endgroup\$
0
2
\$\begingroup\$

This thing will work as long as one doesn't push_back beyond the capacity.

I wouldn't call it AtomicFixedSizedVector - I think it's better to name it AtomicFixedCapacityBackInserter or something and let it wrap an iterator of the vector - or pointer towards base of the vector - plus the very same atomic size. That's because this way its name states more clearly and precisely what it does and aims to do.

std::vector::reserve is ought to make the allocation and you can access the size of the total allocated amount via capacity function.

However, you should be aware that this is just a safety mechanism and unlikely to be an optimization. It might and probably will perform slower than a single threaded insertion. That's due to cacheline size and mechanism of syncronization of the said cachelines. The efficiency or lackthereof is surely hardware dependant and requires testing.

\$\endgroup\$
4
\$\begingroup\$

You haven't shown how you intend to use this thing, so it's impossible to say for sure whether it "works correctly." For example, obviously it doesn't work if you're planning to use it like this:

AtomicFixedSizeVector<int> v;
v.reserve(100);
std::thread t1([&]() {
    while (v.size() < 10) v.push_back(42);
});
std::thread t2([&]() {
    while (v.size() < 10) std::this_thread::sleep_for(1ms);
    std::cout << v.m_data[0] << "\n";  // DATA RACE!
});

Obviously it won't compile if your type T isn't default-constructible. You could address that idiomatically by adding

static_assert(std::is_default_constructible_v<T>);

to the top of the class body — thus hopefully reassuring the client-programmer that the crazy template error message they just got was intended, and not a bug.


Your reserve method can only be called once, and m_count increases monotonically. Think about whether to implement a clear() method, and what it might do. Think about whether reserve() should reset m_count to zero or not.

My kneejerk reaction is that reserve shouldn't exist at all, and that you should force the user to construct the container with the right capacity to begin with:

explicit AtomicFixedSizeVector(int capacity);

ALX23z is right that what you mean is FixedCapacity, not FixedSize.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks, I will be sure to remove the reserve as you mentioned and take a note on the static_assertion too. Both answers were equally useful for me, I hope you don't mind I accepted the first one, I don't think I can accept both. :( \$\endgroup\$ – Exaberri Tokugawa Mar 1 '20 at 17:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.