CODEWITHSUNDEEP
c++multithreadingatomic
Josh Weinstein
Josh Weinstein

Reputation: 2968

Is using the result of an std::atomic fetch_add to index an array still atomic?

So I wanted to try implementing a fixed sized, wait free stack with the fetch_add and fetch_sub atomic instructions. Say that I have a basic stack, with two operations, push and pop.

struct WaitFreeStack {
    std::atomic<size_t> cur;
    std::atomic<int>* buf;

    void push(int i) {
        buf[cur.fetch_add(1)].store(i);
    }

    int pop() {
        return buf[cur.fetch_sub(1) - 1].load();
    }
};

My question is, are operations in the form of B[X], where B is an array and X is an integer atomic ? In my example for instance, is it possible that after a fetch_add call for the push() method is executed, and before the B[X] is executed, that a whole pop and push in separate threads could be executed, causing a push to overwrite another push ?

Upvotes: 0

Views: 435

Answers (2)

StPiere
StPiere

Reputation: 4243

B[X] is not atomic. But if it even would be atomic, it wouldn't help much.

The problem is that you have expression of multiple atomic operations. Although operations are atomic, the whole expression is not atomic.

Or: an expression containing of multiple atomic operations does not need to be atomic.

The class invariant here should be that cur points to the current object in buf. But this invariant is broken between 2 atomic operations fetch_add and store.

If B[X] would be atomic (which is not), one would have following sequence of atomic operations for push:

X = cur.fetch_add(1);  // atomic
// 1. dT
ref = B[X];             // let's assume atomic
// 2. dT
ref.store(i);           // atomic

For example in the time interval 2.dT imagine second thread popping 2 items and third thread pushing 1 item, all executing before ref.store(i). In this time the value under ref reference would change.

Upvotes: 0

Sprite
Sprite

Reputation: 3763

are operations in the form of B[X], where B is an array and X is an integer atomic ?

No.

In my example for instance, is it possible that after a fetch_add call for the push() method is executed, and before the B[X] is executed, that a whole pop and push in separate threads could be executed, causing a push to overwrite another push ?

Yes.

Your example can be equated to:

void push(int i) {
    size_t index = cur.fetch_add(1);
    // execution time interval
    buf[index].store(i);
}

int pop() {
    size_t index = cur.fetch_sub(1) - 1;
    // execution time interval
    return buf[index].load();
}

There will be an execution time interval at both comment positions above, although the time interval is very very short, but if another thread calls push or pop and completes the call at this time, it will be absolutely unsafe.

The easiest way to implement thread-safe containers is with std::mutex, and there are some lock-free implementations (like boost).

Upvotes: 1

Related Questions