title: OpenMP atomic substantially slower than critical for array
body: <p>The examples that I have seen for OpenMP's <code>omp atomic</code> generally involve updating a scalar, and usually report that it is faster than <code>omp critical</code>. In my application I wish to update elements of an allocated array, with some overlap between the elements that different threads will update, and I find that atomic is substantially slower than critical. Does it make a difference that it is an array, and am I using it correctly?</p>
  <pre><code>#include &lt;stdlib.h&gt;
  #include &lt;assert.h&gt;
  #include &lt;omp.h&gt;
  
  #define N_EACH 10000000
  #define N_OVERLAP 100000
  
  #if !defined(OMP_CRITICAL) &amp;&amp; !defined(OMP_ATOMIC)
  #error Must define OMP_CRITICAL or OMP_ATOMIC
  #endif
  #if defined(OMP_CRITICAL) &amp;&amp; defined(OMP_ATOMIC)
  #error Must define only one of either OMP_CRITICAL or OMP_ATOMIC
  #endif
  
  int main(void) {
  
    int const n = omp_get_max_threads() * N_EACH -
                  (omp_get_max_threads() - 1) * N_OVERLAP;
    int *const a = (int *)calloc(n, sizeof(int));
  
  #pragma omp parallel
    {
      int const thread_idx = omp_get_thread_num();
      int i;
  #ifdef OMP_CRITICAL
  #pragma omp critical
  #endif /* OMP_CRITICAL */
      for (i = 0; i &lt; N_EACH; i++) {
  #ifdef OMP_ATOMIC
  #pragma omp atomic update
  #endif /* OMP_ATOMIC */
        a[thread_idx * (N_EACH - N_OVERLAP) + i] += i;
      }
    }
  
  /* Check result is correct */
  #ifndef NDEBUG
    {
      int *const b = (int *)calloc(n, sizeof(int));
      int thread_idx;
      int i;
      for (thread_idx = 0; thread_idx &lt; omp_get_max_threads(); thread_idx++) {
        for (i = 0; i &lt; N_EACH; i++) {
          b[thread_idx * (N_EACH - N_OVERLAP) + i] += i;
        }
      }
      for (i = 0; i &lt; n; i++) {
        assert(a[i] == b[i]);
      }
      free(b);
    }
  #endif /* NDEBUG */
  
    free(a);
  }
  </code></pre>
  <p>Note that in this simplified example we can determine in advance which elements will overlap, so it would be more efficient to only apply <code>atomic</code>/<code>critical</code> when updating those, but in my real application this is not possible.</p>
  <p>When I compile this using:</p>
  <ul>
  <li><code>gcc -O2 atomic_vs_critical.c -DOMP_CRITICAL -DNDEBUG -fopenmp -o critical</code></li>
  <li><code>gcc -O2 atomic_vs_critical.c -DOMP_ATOMIC -DNDEBUG -fopenmp -o atomic</code></li>
  </ul>
  <p>and run with <code>time ./critical</code> I get:
  <code>real    0m0.110s user    0m0.086s sys 0m0.058s</code></p>
  <p>and with <code>time ./atomic</code>, I get:
  <code>real    0m0.205s user    0m0.742s sys 0m0.032s</code></p>
  <p>So it uses about half the wallclock time with the critical section (and I get the same when I repeat it).</p>
  <p>There is another post that <a href="https://stackoverflow.com/questions/49787162/openmp-critical-performance-better-than-atomic">claims critical is slower than atomic</a>, but that uses a scalar, and when I run the provided code the atomic result is actually slightly faster than the critical one.</p>