0

In a well-known book The Art of Multiprocessor Programming by Herlihy, Shavit some of lock-free and wait-free algorithms utilize Java's template AtomicMarkableReference<T> type. It allows to perform single atomic CAS operation on the pair consisting of T reference and boolean mark.

There is no similar type in C/C++/Go stdlib, but at least in C++ it's possible to model it using bit stealing approach (see C++ example). On x86_64 arch only 48 bits of 64 bits are actually used, so one can store arbitrary data in the remaining 16 bits, and work with the whole pointer and the data atomically.

As far as I understand, there are two requirements to implement this approach:

  1. Pointers must be aligned.
  2. Pointer's low bits must be clear (if you want to store something like bool in this area, it must not be already occupied).

Are these requirements met in Go? Are there any working examples of bit stealing technique in Go?

Vitaly Isaev
  • 5,392
  • 6
  • 45
  • 64
  • 3
    There is the potential for a Go GC implementation to use any otherwise-unused bits of pointers for its own purposes, so in general this is unwise. If, however, you pick a *particular implementation*, where you know how the runtime uses (or does not use) these bits, you can attempt this kind of thing. – torek May 06 '21 at 04:18
  • I doubt that these requirements actually are requirements and I think the crucial ones are missing (see toreks comment). – Volker May 06 '21 at 04:46

0 Answers0