How can I implement a lock-free ABA counter in C 11 using CAS and minimize performance overhead?

How can I implement ABA counter with c 11 CAS?

To atomically update two values simultaneously, create an atomic, adjacent struct. Suppose you use std::atomic to implement this. Then, the following actions will occur:

1. Utilize lock cmpxchg16b instruction on x86-64 processors through gcc compilation.
2. Avoid inline assembly and prefer C syntax for efficiency.
3. Employ unions to enable efficient loading of individual struct members.
4. Ensure 16B (or 8B for 32-bit pointers) alignment to prevent performance issues on x86 architectures.
5. Use -mcx16 for x86-64 builds, as cmpxchg16b was not consistently supported by early x86-64 CPUs.

Note that the atomic object should be lock-free, especially for x86 CPUs. Compilers like gcc7 and later might call libatomic instead of using inline lock cmpxchg16b. In such scenarios, consider the following:

• Verify that the compiler generates efficient code for reading individual members without resorting to a lock cmpxchg16b of the pair.
• Ensure that accessing one union member after modifying a different one is well-defined for the implementation. This is legal in GNU C but might incur undefined behavior if you adhere strictly to ISO C .
• Ensure that the object is properly aligned, as misalignment can lead to performance degradation on x86 architectures.
• Maintain alignment for 32-bit pointers, as atomic objects larger than pointers might use locks on x86-64 CPUs.

Here's an example of C 11 code that exhibits these characteristics:

#include <atomic>
#include <stdint.h>

using namespace std;

struct node {
  struct alignas(2*sizeof(node*)) counted_ptr {
    node *    ptr;
    uintptr_t count;  // use pointer-sized integers to avoid padding
  };

  // hack to allow reading just the pointer without lock-cmpxchg16b,
  // but still without any C++ data race
  struct counted_ptr_separate {
    atomic<node *>    ptr;
    atomic<uintptr_t> count_separate;  // var name emphasizes that accessing this way isn't atomic with ptr
  };

  static_assert(sizeof(atomic<counted_ptr>) == sizeof(counted_ptr_separate), "atomic<counted_ptr> isn't the same size as the separate version; union type-punning will be bogus");
  // TODO: write member functions to read next.ptr or read/write next_and_count

  union {  // anonymous union: the members are directly part of struct node
    alignas(2*sizeof(node*)) atomic<counted_ptr> next_and_count;
    counted_ptr_separate  next;
  };
};

In summary, atomically modifying two values simultaneously requires careful design, compiler considerations, and alignment optimizations. By following these guidelines, you can implement lock-free ABA counters in C 11 with efficient and correct code.

The above is the detailed content of How can I implement a lock-free ABA counter in C 11 using CAS and minimize performance overhead?. For more information, please follow other related articles on the PHP Chinese website!