title: High Performance Computing: the use of shared_array vs atomics?
body: <p>I'm curious if anyone here has knowledge on the efficiency of atomics, specifically <code>std::atomic&lt;int&gt;</code>. My problem goes as follows:</p>
  
  <hr>
  
  <p>I have a data set, say <code>data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}</code> that is passed into an algorithm <code>algo(begin(data), end(data))</code>. <code>algo</code> partitions the data into chunks and executes each chunk asynchronously, so <code>algo</code> would perform it's operation on, say, 4 different chunks:</p>
  
  <pre><code>{1, 2, 3}
  {4, 5, 6}
  {7, 8, 9}
  {10, 11, 12}
  </code></pre>
  
  <p>in each separate partition I need to return the count of elements that satisfy a predicate <code>op</code> at the end of <strong>each</strong> partition</p>
  
  <pre><code>//partition lambda function
  {
      //'it' corresponds to the position in it's respective partition
      if( op(*it) )
          count++;
  
      //return the count at the end of this partition
      return count;    
  }
  </code></pre>
  
  <p>the problem is that I'm going to run into a data race just incrementing 1 variable with 4 chunks executing asynchronously. I was thinking of two possible solutions:</p>
  
  <ul>
  <li><p><strong>use a std::atomic</strong></p>
  
  <ul>
  <li>the problem here is I know very little about C++'s atomics, and from what i've heard they can be inefficient. Is this true? what results should I expect to see with using atomics to keep track of a count?</li>
  </ul></li>
  <li><p><strong>use a shared array, where the size is the partition count</strong></p>
  
  <ul>
  <li>I know my shared arrays pretty well so this idea doesn't seem too bad, but I'm unsure how it would hold up when a very small chunk size is given, which would make the shared array keeping track of the count at the end of each partition quite large. It would be useful however as the algorithm doesn't have to wait for anything to finish to increment, it simply places it's respective count in the shared array.</li>
  </ul></li>
  </ul>
  
  <p>so with both my ideas, I could implement it possible as:</p>
  
  <pre><code>//partition lambda function, count is now atomic
  {
      //'it' corresponds to the position in it's respective partition
      if( op(*it) )
          count++;
  
      //return the count at the end of this partition
      return count.load();    
  }
  </code></pre>
  
  <hr>
  
  <pre><code>//partition lambda function, count is in shared array that will be be accessed later
  //instead of returned
  {
      int count = 0;
      //'it' corresponds to the position in it's respective partition
      if( op(*it) )
          count++;
  
      //total count at end of each partition. ignore fact that partition_id = 0 wouldn't work
      shared_arr[partition_id] = shared_arr[partition_id - 1] + count;
  }
  </code></pre>
  
  <p>any ideas on <code>atomic</code> vs <code>shared_array</code>?</p>