title: Lost/confused in optimizing
body: <p>I just completed a computer graphics course, where we had to program a ray tracer. Though all the results were correct, I was confused about the use of OpenMP (which BTW was not part of the course). I have this loop (C++):</p>
  
  <pre><code>#pragma omp parallel for private(L, ray)
  //  for (x = x_from; x &lt; x_till; x++) {
  //  printf("Col: %5d\n", x);
  //  for (y = y_from; y &lt; y_till; y++) {
    for (int xy = 0; xy &lt; xy_range; xy++) {
      int x = x_from + (xy % x_width);
      int y = y_from + (xy / x_width);
          ray = cam-&gt;get_ray_at(x, y);
          L = trace_ray(ray, 0, cam-&gt;inter);
      #pragma omp critical
      cam-&gt;set_pixel(x, y, L);
    }
  //  }
  }
  </code></pre>
  
  <p>I tried many configurations. But what finally confuses me the most is that the above version, with a combined, single for, was the least efficient of all (150 seconds vs 120s for separate x and y for. The 'critical' does not noticeably change the timing.</p>
  
  <p>More: though I would expect the single for-loop to parallelize each separate iteration, it doesn't. Using this method, 25 loops are executed as groups of 8 - 8 - 8 - 1 (8 cores). In fact the separate y-loops (commented out in listing) seem to distribute the load more efficiently. Removing the 'for' in 'parallel for' does improve
  slightly (148 vs 150s ;)</p>
  
  <p>Also, I tried local vs global definitions (with the necessary private pragmas). I tried to declare L and ray inside the loops. All to no avail...</p>
  
  <p>I'd appreciate suggestions or pointers...</p>
  
  <p>Here are some more precise data:</p>
  
  <pre><code>Single loop             Yes                     No                      No                      Yes    
  'Critical"              No                      No                      Yes                     Yes
                  ----------------------  ----------------------  ----------------------  ----------------------
                  User    CPU     Mean    User    CPU     Mean    User    CPU     Mean    User    CPU     Mean
  Scene 5         37.9    158.9   3.66    26.5    185.5   7.00    27.0    187.7   6.95    38.7    161.8   4.18
  Scene 6         18.8    110     5.85    17.7    112     6.32    18.1    113.8   5.29    19.4    112.2   5.78
  Scene 7         149     658.8   4.42    114     679.9   5.96    114     653.8   5.73    149     659.8   4.43
  Plane           112.0   497.3   4.44    105     520.5   4.95    103.8   525     5.06    113.5   504.8   4.45     
  5-balls         126     760.2   6.03    162.3   697.5   4.36    170.3   725.3   4.23    127.3   766.5   6.02
  </code></pre>
  
  <p>'Mean' is CPU/User, which is the mean core occupation. Note that in several cases, mean is only 4.xx.</p>
  
  <p>Solution, and results:</p>
  
  <pre><code>Single loop             Yes                     No
                  ----------------------  ----------------------
                  User    CPU     Mean    User    CPU     Mean
  Scene 5         23.9    190.1   7.95    24.4    190.7   7.82
  Scene 6         14.3    114.2   7.98    14.5    114.9   7.92
  Scene 7         85.5    675.9   7.91    106.9   698.8   6.54
  Plane           72.7    579.1   7.97    72.6    578.4   7.97
  5-balls         104.8   823.3   7.86    103.9   825.1   7.94
  </code></pre>
  
  <p>This excellent result is obtained by adding schedule(dynamic, 1) to
  the #pragma omp parallel for line like this:</p>
  
  <pre><code>#pragma omp parallel for schedule(dynamic, 1)
  </code></pre>
  
  <p>which see to a run-time load distribution for cores (as opposed to
  compile time). </p>
  
  <p>Just one more note, the ', 1' parameter is to limit the size of the
  chunks. It can be left out, in which case openmp uses a default
  value. Maybe adding 1 made the load distribution too fine-grained,
  but I cannot find any performance difference either way in this case .
  I guess the raytracing task is too slow and hides any administrative 
  overhead.</p>