Geek Answers Handbook

Atomic Compare and Swap with structure in Go

I am trying to create a package of non-blocking queues for a parallel application using the algorithm of Magad M. Michael and Michael L. Scott, as described here .

This requires the use of atomic CompareAndSwap, offered by the package "sync/atomic" .
However, I'm not sure if the Go equivalent is equivalent to the following pseudo-code:

 E9: if CAS(&tail.ptr->next, next, <node, next.count+1>)

where tail and next is of type:

 type pointer_t struct { ptr *node_t count uint }

and node is of type:

 type node_t struct { value interface{} next pointer_t }

If I understood correctly, it seems to me that I need to make CAS with a structure (both a pointer and a uint ). Is this possible with an atomic package?

Thanks for the help!

+4
source share
2 answers

If I understood this correctly, it seems to me that I need to make CAS with a structure (both a> and uint pointer). Is this possible with an atomic package?

No, It is Immpossible. Most architectures only support atomic operations on a single word. However, most academic papers use more powerful CAS operators (such as comparison and swap), which are not available today. Fortunately, there are a few tricks that are commonly used in such situations:

  • You can, for example, steal a couple of bits from a pointer (especially on 64-bit systems) and use them to encode your counter. Then you can just use Go CompareAndSwapPointer, but you need to mask the corresponding bits of the pointer before trying to dereference it.

  • Another possibility is to work with pointers to your (immutable!) Pointer_t structure. Whenever you want to change an element from your pointer_t structure, you will need to create a copy, change the copy and atomically replace the pointer with your structure. This idiom is called COW (copied when writing) and works with arbitrary large structures. If you want to use this method, you will have to change the next attribute to next *pointer_t .

I recently wrote a free list on Go for educational reasons. You can find the source (imho well documented) here: https://github.com/tux21b/goco/blob/master/list.go

This rather short example uses atomic.CompareAndSwapPointer excessively, and also introduces the atomic type for marked pointers (MarkAndRef structure). This type is very similar to your pointer_t structure (except that it stores a bool + pointer instead of an int + pointer). It was used to ensure that the node is not marked as deleted when you try to insert an element immediately afterwards. Feel free to use this source as a starting point for your own projects.

+9
source

You can do something like this:

  if atomic.CompareAndSwapPointer( (*unsafe.Pointer)(unsafe.Pointer(tail.ptr.next)), unsafe.Pointer(&next), unsafe.Pointer(&pointer_t{&node, next.count + 1}) )
0
source

More articles:


All Articles