title: overhead of critical region exceeds speedup of for loop parallelization
body: <p>I am trying to parallelize the following serial code in a function</p>
  
  <pre><code>    float arr[100];
      for ( int i = 0; i &lt; 100; ++i) arr[i]=0;
  
      int i,j;
      for ( i = 0; i &lt; 100; ++i) {
        float* pi = arr+i;
        int index[10];
        f(i, index); // f fills in the array index
        for (j = 0; j &lt; 10; ++j) {
          float* pj = arr+index[j];
          if (pj &gt; pi){
              float tmp = g(i,j); // some function g
              *pi += tmp;
              *pj += tmp;
          }
        }
      }
  </code></pre>
  
  <p>and a similar one appear in another function</p>
  
  <pre><code>    float arr[100];
      for ( int i = 0; i &lt; 100; ++i) arr[i]=0;
  
      int i,j;
      for ( i = 0; i &lt; 100; ++i) {
        float* pi = arr+i;
        int index[10];
        f(i, index); // f fills in the array index
        for (j = 0; j &lt; 10; ++j) {
          float* pj = arr+index[j];
          if (pj &gt; pi){    
              h(pi,i); // function h updates the memory pointed by pi, 
              // by adding to  to *pi something, which only depends on i but not on the values pointed by pi.
              h(pj,j); // 
          }
        }
      }
  </code></pre>
  
  <p>My way is:</p>
  
  <pre><code>    float arr[100];
      for ( int i = 0; i &lt; 100; ++i) arr[i]=0;
  
      int i,j;
  #pragma omp parallel for shared(arr) private(i,j) schedule(auto)
      for ( i = 0; i &lt; 100; ++i) {
        float* pi = arr+i;
        int index[10];
        f(i, index);
        for (j = 0; j &lt; 10; ++j) {
          float* pj = arr+index[j];
          if (pj &gt; pi){
              float tmp = g(i,j);
              *pi += tmp;
              #pragma omp atomic update
              *pj += tmp;
          }
        }
      }
  </code></pre>
  
  <p>and</p>
  
  <pre><code>    float arr[100];
      for ( int i = 0; i &lt; 100; ++i) arr[i]=0;
  
      int i,j;
  #pragma omp parallel for shared(arr) private(i,j) schedule(auto)
      for ( i = 0; i &lt; 100; ++i) {
        float* pi = arr+i;
        int index[10];
        f(i, index);
        for (j = 0; j &lt; 10; ++j) {
          float* pj = arr+index[j];
          if (pj &gt; pi){
             h(pi,i); 
             #pragma omp critical (pj)
             h(pj,j); // 
          }
        }
      }
  </code></pre>
  
  <p>I use the atomic and critical directives because multiple threads can write to memory pointed by pj simultaneously. (if I am correct, threads don't write to the memory pointed by pi simultaneously.)</p>
  
  <p>However, adding the atomic and critical directives, increases the running time to be around the same as that of the serial code.</p>
  
  <p>So I wonder what should I do?</p>