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

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

Susan Sarandon
Release: 2024-12-15 08:07:11
Original
773 people have browsed it

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;
  };
};
Copy after login

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!

source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Latest Articles by Author
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template