3

I have two pointers which point to a big graph object in a multi-threading C++ app. I try to swap them every 5 minutes. Which way is safe and has the best performance? Is C++11 atomic<> a good choice?

Jonathan Wakely
  • 166,810
  • 27
  • 341
  • 521
Dean Chen
  • 3,800
  • 8
  • 45
  • 70
  • 1
    I would imagine, holding them in a `std::atomic<>` and calling `compare_exchange`, e.g. http://en.cppreference.com/w/cpp/atomic/atomic/compare_exchange – Nim Apr 08 '15 at 10:31
  • Swapping two values of the same type can be done using a temporary variable of the same type and three assignments. I don't think there is a performance issue here. – axiac Apr 08 '15 at 10:31
  • 15
    You're doing one swap every five minutes and you're looking for "best performance"?! – David Schwartz Apr 08 '15 at 10:35
  • 1
    @DavidSchwartz swapping might not be the issue, but checking if you're currently swapping every time you read one of the pointers might... – Lanting Apr 08 '15 at 10:36
  • @axiac, I would imagine that in a multi-threaded scenario though, there is no guarantee that the swap would be "atomic", for example if you play out what would happen if two threads attempted the swap... – Nim Apr 08 '15 at 10:36
  • Depending on the data structure and algorithms involved, [RCU](https://en.wikipedia.org/wiki/Read-copy-update) could be relevant. – Wintermute Apr 08 '15 at 10:41
  • 3
    One approach is to have say `std::atomic_int the_flipper;` and flip it from `0` to `1` and back: code can then get `ptr[the_flipper]` or `ptr[the_flipper^1]` - resolving to different pointers when `the_flipper`'s changed. Still, I'm struggling to imagine a use where it would matter if the pointers are briefly identical (there's a race condition meaning anyone reading both might see the same around an atomic swap anyway), so using two `std::atomic_uintptr_t` and a temporary as axiac suggests is likely perfectly fine. – Tony Delroy Apr 08 '15 at 10:42
  • Following up with @DavidSchwartz 's response, have you actually profiled or measured your application and found this worth optimizing? You are doing it once every 5 minutes... Does it hang/stall? – Preet Kukreti Apr 08 '15 at 10:49
  • 1
    @Nim sure, you are right about the part of the question that requires a safe way to swap the pointers. I was referring to the performance issue. – axiac Apr 08 '15 at 10:52
  • Is this question about performance or about concurrency/safety? – Paolo M Apr 08 '15 at 10:57
  • What is the target OS? The OS could also provide you a safe way to do this thing. I cannot tell for Linux/Unix and OSX but Windows surely does. – axiac Apr 08 '15 at 10:59
  • If this question is about performance, should be closed, one pointer swap every 5 minutes, you can use the slowest mechanism in the world that the impact in your application would be 0.01%. If you are asking about a safe way to swap values, use atomic or spin locks, it is not worth to use a mutex for swaping pointers. – Jose Palma Apr 08 '15 at 11:09

1 Answers1

6

Does the swap need to be atomic? i.e. do you need to guarantee that another thread cannot observe them both having the same value while swapping?

If you don't need to guarantee the swap is atomic then just use two std::atomic<T*> objects and swap them using a temporary:

T* tmp = p1;
p1 = p2.load();
p2 = tmp;

If you need the swap to be atomic then to do it in standard C++ you will need to store them both in the same structure, so it can be updated in a single step e.g.

struct TwoPointers { T* p1; T* p2; }
std::atomic<TwoPointers> p;

then you can swap them like so:

auto old = p.load();
p = { old.p2, old.p1 };

This uses double-word atomic operations, which might be implemented with a mutex behind the scenes, so the simple assignment via a temporary is likely to perform better, but I doubt it will make any difference once every five minutes.

Both versions above assume only one thread will try to swap them at any time, because although loading the old value is done atomically, and writing the new value is done atomically, there is a window between those two steps during which another thread could change the pointer values. If that's a problem use a std::atomic<TwoPointers> like this instead:

auto old = p.load();
while (!p.compare_exchange_strong(old, { old.p2, old.p1 }))
{ };

Using compare_exchange_strong in a loop is slightly slower than a single atomic store, but again you won't notice the difference if it only happens once every five minutes.

This TwoPointers solutions also mean the two pointers share a cache-line, but if they are read-only apart from the swap every five minutes then that's not a problem.

Jonathan Wakely
  • 166,810
  • 27
  • 341
  • 521