title: Why does this code execute more slowly after strength-reducing multiplications to loop-carried additions?
body: <p>I was reading <a href="https://en.wikipedia.org/wiki/Agner_Fog" rel="noreferrer">Agner Fog</a>'s <a href="https://en.wikipedia.org/wiki/Agner_Fog#Optimization" rel="noreferrer">optimization manuals</a>, and I came across this example:</p>
  <pre class="lang-c prettyprint-override"><code>double data[LEN];
  
  void compute()
  {
      const double A = 1.1, B = 2.2, C = 3.3;
  
      int i;
      for(i=0; i&lt;LEN; i++) {
          data[i] = A*i*i + B*i + C;
      }
  }
  </code></pre>
  <p>Agner indicates that there's a way to optimize this code - by realizing that the loop can avoid using costly multiplications, and instead use the &quot;deltas&quot; that are applied per iteration.</p>
  <p>I use a piece of paper to confirm the theory, first...</p>
  <p><a href="https://i.stack.imgur.com/wzzgt.png" rel="noreferrer"><img src="https://i.stack.imgur.com/wzzgt.png" alt="Theory" /></a></p>
  <p>...and of course, he is right - in each loop iteration we can compute the new result based on the old one, by adding a &quot;delta&quot;. This delta starts at value &quot;A+B&quot;, and is then incremented by &quot;2*A&quot; on each step.</p>
  <p>So we update the code to look like this:</p>
  <pre class="lang-c prettyprint-override"><code>void compute()
  {
      const double A = 1.1, B = 2.2, C = 3.3;
      const double A2 = A+A;
      double Z = A+B;
      double Y = C;
  
      int i;
      for(i=0; i&lt;LEN; i++) {
          data[i] = Y;
          Y += Z;
          Z += A2;
      }
  }
  </code></pre>
  <p>In terms of operational complexity, the difference in these two versions of the function is indeed, striking. Multiplications have a reputation for being significantly slower in our CPUs, compared to additions. And we have replaced 3 multiplications and 2 additions... with just 2 additions!</p>
  <p>So I go ahead and add a loop to execute <code>compute</code> a lot of times - and then keep the minimum time it took to execute:</p>
  <pre class="lang-c prettyprint-override"><code>unsigned long long ts2ns(const struct timespec *ts)
  {
      return ts-&gt;tv_sec * 1e9 + ts-&gt;tv_nsec;
  }
  
  int main(int argc, char *argv[])
  {
      unsigned long long mini = 1e9;
      for (int i=0; i&lt;1000; i++) {
          struct timespec t1, t2;
          clock_gettime(CLOCK_MONOTONIC_RAW, &amp;t1);
          compute();
          clock_gettime(CLOCK_MONOTONIC_RAW, &amp;t2);
          unsigned long long diff = ts2ns(&amp;t2) - ts2ns(&amp;t1);
          if (mini &gt; diff) mini = diff;
      }
      printf(&quot;[-] Took: %lld ns.\n&quot;, mini);
  }
  </code></pre>
  <p>I compile the two versions, run them... and see this:</p>
  <pre class="lang-bash prettyprint-override"><code>gcc -O3 -o 1 ./code1.c
  
  gcc -O3 -o 2 ./code2.c
  
  ./1
  
  [-] Took: 405858 ns.
  
  ./2
  
  [-] Took: 791652 ns.
  </code></pre>
  <p>Well, that's unexpected. Since we report the minimum time of execution, we are throwing away the &quot;noise&quot; caused by various parts of the OS. We also took care to run in a machine that does absolutely nothing. And the results are more or less repeatable - rerunning the two binaries shows this is a consistent result:</p>
  <pre class="lang-bash prettyprint-override"><code>for i in {1..10} ; do ./1 ; done
  
  [-] Took: 406886 ns.
  [-] Took: 413798 ns.
  [-] Took: 405856 ns.
  [-] Took: 405848 ns.
  [-] Took: 406839 ns.
  [-] Took: 405841 ns.
  [-] Took: 405853 ns.
  [-] Took: 405844 ns.
  [-] Took: 405837 ns.
  [-] Took: 406854 ns.
  
  for i in {1..10} ; do ./2 ; done
  
  [-] Took: 791797 ns.
  [-] Took: 791643 ns.
  [-] Took: 791640 ns.
  [-] Took: 791636 ns.
  [-] Took: 791631 ns.
  [-] Took: 791642 ns.
  [-] Took: 791642 ns.
  [-] Took: 791640 ns.
  [-] Took: 791647 ns.
  [-] Took: 791639 ns.
  </code></pre>
  <p>The only thing to do next, is to see what kind of code the compiler created for each one of the two versions.</p>
  <p><code>objdump -d -S</code> shows that the first version of <code>compute</code> - the &quot;dumb&quot;, yet somehow fast code - has a loop that looks like this:</p>
  <p><a href="https://i.stack.imgur.com/JbWNJ.png" rel="noreferrer"><img src="https://i.stack.imgur.com/JbWNJ.png" alt="objdump naive" /></a></p>
  <p>What about the second, optimized version - that does just two additions?</p>
  <p><a href="https://i.stack.imgur.com/HQwXx.png" rel="noreferrer"><img src="https://i.stack.imgur.com/HQwXx.png" alt="objdump optimized" /></a></p>
  <p>Now I don't know about you, but speaking for myself, I am... puzzled. The second version has approximately 4 times fewer instructions, with the two major ones being just <a href="https://en.wikipedia.org/wiki/Streaming_SIMD_Extensions" rel="noreferrer">SSE</a>-based additions (<code>addsd</code>). The first version, not only has 4 times more instructions... it's also full (as expected) of multiplications (<code>mulpd</code>).</p>
  <p>I confess I did not expect that result. Not because I am a fan of Agner (I am, but that's irrelevant).</p>
  <p>Any idea what I am missing? Did I make any mistake here, that can explain the difference in speed? Note that I have done the test on a <a href="https://en.wikipedia.org/wiki/List_of_Intel_Xeon_processors_(Nehalem-based)#%22Gainestown%22_(45_nm)" rel="noreferrer">Xeon W5580</a> and a <a href="https://en.wikipedia.org/wiki/List_of_Intel_Xeon_processors_(Sandy_Bridge-based)#Xeon_E5-1620" rel="noreferrer">Xeon E5-1620</a> - in both, the first (dumb) version is much faster than the second one.</p>
  <p>For easy reproduction of the results, there are two gists with the two versions of the code: <a href="https://gist.github.com/ttsiodras/7b4f4d6948886500cd8fa32fc90dab41" rel="noreferrer">Dumb yet somehow faster</a> and <a href="https://gist.github.com/ttsiodras/178ddc5dd696948a1b34bea09500d96a" rel="noreferrer">optimized, yet somehow slower</a>.</p>
  <p>P.S. Please don't comment on floating point accuracy issues; that's not the point of this question.</p>