title: OpenMP - Nested for-loop becomes faster when having parallel before outer loop. Why?
body: <p>I'm currently implementing an dynamic programming algorithm for solving knapsack problems. Therefore my code has two for-loops, an outer and an inner loop. </p>
  
  <p>From the logical point of view I can parallelize the inner for loop since the calculations there are independant from each other. The outer for loop can not be parallelized because of dependancies.</p>
  
  <p>So this was my <strong>first approach</strong>:</p>
  
  <pre><code>for(int i=1; i &lt; itemRows; i++){
          int itemsIndex = i-1;
          int itemWeight = integerItems[itemsIndex].weight;
          int itemWorth = integerItems[itemsIndex].worth;
  
          #pragma omp parallel for if(weightColumns &gt; THRESHOLD)
          for(int c=1; c &lt; weightColumns; c++){
              if(c &lt; itemWeight){
                  table[i][c] = table[i-1][c];
              }else{
                  int worthOfNotUsingItem = table[i-1][c];
                  int worthOfUsingItem = itemWorth + table[i-1][c-itemWeight];
                  table[i][c] = worthOfNotUsingItem &lt; worthOfUsingItem ? worthOfUsingItem : worthOfNotUsingItem;
              }
          }
  }
  </code></pre>
  
  <p>The code works well, the algorithm solves the problems correctly.
  Then I was thinking about optimizing this, since I was not sure how OpenMP's thread management works. I wanted to prevent unnecessary initialization of the threads during each iteration, thus I put an outer parallel block around the outer loop.</p>
  
  <p><strong>Second approach:</strong></p>
  
  <pre><code>#pragma omp parallel if(weightColumns &gt; THRESHOLD)
  {
      for(int i=1; i &lt; itemRows; i++){
          int itemsIndex = i-1;
          int itemWeight = integerItems[itemsIndex].weight;
          int itemWorth = integerItems[itemsIndex].worth;
  
          #pragma omp for
          for(int c=1; c &lt; weightColumns; c++){
              if(c &lt; itemWeight){
                  table[i][c] = table[i-1][c];
              }else{
                  int worthOfNotUsingItem = table[i-1][c];
                  int worthOfUsingItem = itemWorth + table[i-1][c-itemWeight];
                  table[i][c] = worthOfNotUsingItem &lt; worthOfUsingItem ? worthOfUsingItem : worthOfNotUsingItem;
              }
          }
       }
  }
  </code></pre>
  
  <p>This has an unwanted side effect: Everything inside the parallel block will now be executed n-times, where n is the number of available cores. I already tried to work with pragmas <code>single</code> and <code>critical</code> to force the outer for-loop to be executed in one thread, but then I can not calculate the inner loop by multiple threads unless I open a new parallel block (but then there would be no gain in speed). But nevermind, because the good thing is: this does not affect the result. The problems are still solved correctly.</p>
  
  <p><strong>NOW THE STRANGE THING: The second approach is FASTER than the first one!</strong></p>
  
  <p>How can this be? I mean, although the outer for-loop is calculated n times (in parallel) and the inner for-loop is distributed n times among n cores it is faster than the first approach which only calculates the outer loop one time and distributes the workload of the inner for-loop evenly.</p>
  
  <p>At first I was thinking: "well yeah, it's probably because of thread management" but then I read that OpenMP pools the instantiated threads which would speak against my assumption. Then I disabled compiler optimization (compiler flag -O0) to check if it has something to do with. But this did not affect the measurement.</p>
  
  <p>Can anybody of you shed more light into this please?</p>
  
  <p>The <strong>measured times</strong> for solving the knapsack-problem containing 7500 items with a max capacity of 45000 (creating a matrix of 7500x45000, which is way over the used THRESHOLD variable in code):</p>
  
  <ul>
  <li>Approach 1: ~0.88s </li>
  <li>Approach 2: ~0.52s</li>
  </ul>
  
  <p>Thanks in advance,</p>
  
  <p>phineliner</p>
  
  <p><strong>EDIT</strong>:</p>
  
  <p>Measurement of a more complex problem:
  Added 2500 items to the problem (from 7500 to 10000) (more complex problems can't currently be handled because of memory reasons).</p>
  
  <ul>
  <li>Approach 1: ~1.19s </li>
  <li>Approach 2: ~0.71s</li>
  </ul>
  
  <p><strong>EDIT2</strong>:
  I was mistaken about the compiler optimization. This does not affect measurement. At least I can not reproduce the difference I measured before. I edited the question text according to this.</p>