How to Implement a 64-bit Atomic Counter Using Only 32-bit Atomic Variables?

Implementing a 64-bit Atomic Counter with 32-bit Atomic Variables

Question:

Design and implement a 64-bit atomic counter using 32-bit atomic variables. The counter has a single writer (signal handler) and multiple readers.

Code:

class counter {
    atomic<uint32_t> lo_{};
    atomic<uint32_t> hi_{};
    atomic<uint32_t> gen_{};

    uint64_t read() const {
        auto acquire = memory_order_acquire;
        uint32_t lo, hi, gen1, gen2;
        do {
            gen1 = gen_.load(acquire);
            lo = lo_.load(acquire);
            hi = hi_.load(acquire);
            gen2 = gen_.load(acquire);
        } while (gen1 != gen2 || (gen1 & 1));
        return (uint64_t(hi) << 32) | lo;
    }

    void increment() {
        auto release = memory_order_release;
        gen_.fetch_add(1, release);
        uint32_t newlo = 1 + lo_.fetch_add(1, release);
        if (newlo == 0) {
            hi_.fetch_add(1, release);
        }
        gen_.fetch_add(1, release);
    }
};

Answer:

The provided code is a correct implementation of a 64-bit atomic counter using 32-bit atomic variables. It uses a technique known as a SeqLock, which employs a generation count to maintain the consistency of the high and low halves of the counter.

The read operation uses a loop to acquire the correct state of the counter while handling potential race conditions between readers and writers. The write operation increments both the high and low parts of the counter atomically, using memory ordering to ensure correct behavior.

Improved Implementation:

While the provided code is correct, it can be improved for better performance and efficiency:

• Instead of using atomic RMW operations for the counter payload, they can be replaced with plain loads and stores to avoid unnecessary overhead.
• The sequence counter can also be maintained with plain loads and stores, as it only needs to be monotonically increasing and not atomically updated.

Alternative Design:

An alternative design that eliminates the need for atomic RMW operations altogether is to use a union of a volatile uint64_t and a std::atomic variable. The volatile part can be used for reading and writing the value, while the atomic variable can be used for updating the sequence counter. This approach provides the necessary guarantees for correct behavior while also optimizing for performance.

The above is the detailed content of How to Implement a 64-bit Atomic Counter Using Only 32-bit Atomic Variables?. For more information, please follow other related articles on the PHP Chinese website!