C++ What memory order do I need for the atomics in this MPMC queue?

Viewed 72

This is my implementation of a lockless, waitless, multithread-safe MPMC queue using only atomics:

template <typename T, int32_t SIZE>
class queue_mpmc {
    T ar[SIZE];
    std::atomic_uint64_t start;
    std::atomic_uint64_t end;
    std::atomic_int32_t precount;
    std::atomic_int32_t postcount;
  public:
    queue_mpmc() {
        start = 0;
        end = 0;
        precount = 0;
        postcount = 0;
    }
    bool trypush(T data) {
        int32_t c = ++precount;    // this must be done before the line beginning ar
        if (c > SIZE) { [[unlikely]]
            --precount;
            return false;
        }
        ar[end++ % SIZE] = data;
        ++postcount;               // this must be done after the line beginning ar
        return true;
    }
    T trypop() {
        int32_t c = --postcount;   // this must be done before the line beginning ar
        if (c < 0) {
            ++postcount;
            return T{};
        }
        T r = ar[start++ % SIZE];
        --precount;                // this must be done after the line beginning ar
        return r;
    }
    int32_t len() {
        return precount;
    }
};

It's designed for SIZE to be a factor of 2 (32, 64, 128, 256, etc.) as in these cases it provides efficient wraparound on the underlying array using the modulus operator due to compiler optimizations.

I have been reading about atomic memory order, but I'm new to this and I can't figure out whether this applies to the atomics I'm using? The design does rely on the ++/--precount and ++/--postcount being before or after the end++ and start++ instructions (which are inside the lines beginning ar). That's it though, and that only needs to apply on the current thread, it doesn't need to sync between threads beyond what is typically expected of atomics.

Can I improve performance by specifying a memory order?

1 Answers

If the other bugs are fixed, most likely start, end, and precount can all be memory_order_relaxed in all uses.

postcount is the variable that signifies that a value has been written to the queue. ie it controls the publishing of the value, and the reading of the value.

So postcount needs memory_order_release ("publish") in push, and memory_order_acquire before reading (ie in pop).

Maybe.

Related