-1

There are ways of summing up elements of a C++ vector, but how to guarantee this "atomically"? During the summing action, the elements of the vector may be modified by other threads, which leads to unknown result. Is there a lock-free way to prevent the vector from being modified until the summation is complete?

Remy Lebeau
  • 555,201
  • 31
  • 458
  • 770
Salmon
  • 369
  • 1
  • 4
  • 14
  • Can you give a scenario where you would calculate an outdated sum of a vector which is (like it seems) heavily changed by other threads? Why does it need to be lock-free? – RoQuOTriX Jun 30 '21 at 13:01
  • If the vector is large, then any 'truly atomic' operation would likely have dire consequences for the operating system. – Adrian Mole Jun 30 '21 at 13:02
  • 5
    No, there isn't one. Anything that prevents the vector being modified is, by definition, a lock. – user253751 Jun 30 '21 at 13:03
  • I am implementing a sliding window limiter in a multi-threaded context. It is implemented by vector. When a request comes, I need to sum the vector to determine whether to accept the current request, and if accecpted, vector[index]++ will be done. – Salmon Jun 30 '21 at 13:08
  • @Salmon and locking is not a option then? This doesn't sound like a real-time or time-consuming problem where you would prefer lock-free implementations – RoQuOTriX Jun 30 '21 at 13:10
  • One option would be to copy the vector and sum up the elements of the copy. (Obviously you'd still need to make sure the copy happens at a time when other threads aren't writing to it) - However, i'd consider this carefully. Summing the elements of a vector, especially if the elements are small and there's no indirection is a blisteringly fast operation on modern hardware. Even if you have a ton of elements, i'd wait until the profiler singles out your sum operation as time consuming. – George Jun 30 '21 at 13:16
  • 3
    Another option would be to keep a running sum. Then the problem would shift to having an atomic (and lock-free) `+=`, and making sure that the threads keep the sum updated. Of course, this only makes sense if the rate that the sum changes at is not stupidly higher than how often the sum is read. – Frodyne Jun 30 '21 at 13:25
  • @Frodyne: Smartypants. You just need to be a little careful with floating point, if that's applicable. – Bathsheba Jun 30 '21 at 13:39
  • @Frodyne: Another consideration (forgive me for thinking about this too hard - I've just been on a run) is what happens if a NaN is introduced and subsequently removed? Or a very large number compared to the others? – Bathsheba Jun 30 '21 at 14:43

1 Answers1

-1

Sharing a mutable reference to a vector between threads can lead to very weird bugs. E.g. read iterators can be invalidated by appending or deleting items in another thread.

IMHO the only solution would be to hide the vector behind some layer that logs the inserts/deletes/updates in the modifying thread such that this threads doesn't have to acquire a mutex and hence won't block. Once it can aquire the mutex it can then apply the queued up mutations.

That said, you may consider having the vector owned and referenced by exactly one thread at a time to avoid all these issues.

Marti Nito
  • 697
  • 5
  • 17
  • And how would you protect the log with inserts/deletes/updates? You can't abstract away thread synchronization in the C++ model. – MSalters Jun 30 '21 at 14:39