How to Implement a 64-Bit Atomic Counter Using Only 32-Bit Atomics?

Implementing a 64-Bit Atomic Counter with 32-Bit Atomics

Introduction:

This article addresses the design and implementation of a 64-bit atomic counter using 32-bit atomic operations. It aims to provide efficient, lock-free access to a shared counter, particularly suitable for scenarios with multiple readers and a single writer.

Design Considerations:

The proposed design is based on the concept of a "SeqLock," which leverages a 32-bit generation count with a low bit used as a read-lock mechanism.

Code Implementation:

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);
    }
};

Design Evaluation:

1. Correctness: The design provides a valid implementation of a 64-bit atomic counter, preventing race conditions and ensuring that all threads see consistent values.
2. Efficiency: The use of 32-bit atomics instead of 64-bit atomics improves performance, especially in systems where 64-bit atomic operations are expensive.
3. Lock-freeness: The SeqLock design eliminates the need for locks, resulting in highly concurrent access to the counter.

Alternative Solution:

It is important to note that atomic read-modify-write (RMW) operations may not be necessary for the increment operation. Instead, a more efficient approach is to use pure loads and stores with release memory ordering:

void increment() {
    auto release = memory_order_release;
    uint64_t count = lo_.load(release) | (uint64_t(hi_.load(release)) << 32);
    count++;
    lo_.store(count & uint32_t(-1), release);
    hi_.store((count >> 32) & uint32_t(-1), release);
}

Conclusion:

The proposed implementation provides an efficient and correct solution for creating a 64-bit atomic counter using 32-bit atomics. The SeqLock design ensures that the counter operates without locks while allowing multiple readers and a single writer to operate concurrently without introducing data races.

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