adrianton3 adrianton3 - 2 months ago 14
C++ Question

Summing up an array in parallel

I have the following algorithm for summing up the elements of an array:

// global
index = 0
array = [...]
total_sum = 0 // this is what we're interested in

// per thread
thread_sum = 0
mutex.lock()
while (index < array.size) {
mutex.unlock()

thread_sum += array[index]

mutex.lock()
index++
}
total_sum += thread_sum
mutex.unlock()


Every thread runs the same code and they are joined with the main thread as soon as they finish. The issue is that sometimes more than one thread add the same number. How does this happen?

The original code is in C++ and is using std::vector/thread/mutex/ref.

Answer

Increment index before you release the lock, otherwise multiple threads may see the same value:

// per thread
thread_sum = 0
mutex.lock()
while (index < array.size) {
  i = index++
  mutex.unlock()

  thread_sum += array[i]

  mutex.lock()
}
total_sum += thread_sum
mutex.unlock()

Then again, atomically changing the value of an integer can be done way more efficiently if you use atomic integers.

Lastly think of batching when the individual workload is small or very predictable to reduce the overhead of the synchronisation.