Correct usage of atomics

Question

I've written a small lightweight push/pop queue based on a vector (figured it should be fast) like this:

template <typename T> class MyVectorQueue{

public:

    MyVectorQueue (size_t sz):my_queue(sz),start(0),end(0){}

    void push(const T& val){
       size_t idx=atomic_fetch_add(&end,1UL);
       if (idx==my_queue.size())
          throw std::runtime_error("Limit reached, initialize to larger vector");
       my_queue[idx]=val;
    }

    const T& pop(){
        if (start==end) 
           return end__;
        return my_queue[start.fetch_add(1UL)];
    }

    size_t empty()
    {
        return end==start;
    }

    const T& end() {
        return end__;
    }

private:
    T end__;
    std::atomic<size_t> start,end;
    std::vector<T> my_queue;    
}; 

The size of the vector should be known and I am wondering why is it not thread safe? In what circumstances does this mess my structure?

Answer 1

Your start and end are atomic variables, but using std::vector::operator[] is not atomic operation, making it not thread-safe.

---

Suppose you have 10 threads and the size of the vector is 5. Now, suppose all of them are executing, say push.

Now suppose all 10 threads may have passed the check and the if (end==my_queue.size()) is evaluated to false, as and end has not reached the limit, meaning - the vector is not full.

Then, it's possible that all of them increment end and at the same time call std::vector::operator[]. At least 5 of the threads will try to access elements, "outside" the vector.