title: How to analyse efficiency of a simple algorithm in C
body: <p>Say I am doing a simple task-- a lot.  For this post I will use the example of reducing mod a power of 2-- but this can be any task.</p>
  
  <p>There are many approaches, and it is difficult to determine which one is better.  For example, to reduce a 64-bit unsigned integer <code>a</code> modulo <code>2^b</code>, we can either do:</p>
  
  <ul>
  <li><p><code>a - (a &gt;&gt; b &lt;&lt; b)</code></p></li>
  <li><p><code>a &lt;&lt; (64 - b) &gt;&gt; (64 - b)</code></p></li>
  <li><p><code>a &amp; ((1 &lt;&lt; b) - 1)</code></p></li>
  <li><p><code>a % (1 &lt;&lt; b)</code></p></li>
  <li><p><code>a &amp; array[b]</code>, where <code>array[i]</code> would contain the value <code>((1 &lt;&lt; i) - 1)</code> for various <code>i</code>'s.  I do not wish to assume that <code>array[i]</code> will be in the L1 cache.</p></li>
  </ul>
  
  <p>Perhaps there are others.  For each of these methods, it is fairly straightforward to determine its cost after looking at the assembly code-- e.g. two shifts and a minus; or two shifts, a single-byte minus, and another minus operation partially optimized away by the compiler.</p>
  
  <p>However, it is difficult to determine, which of these is actually faster on a given architecture.  I have tried the following, but failed:</p>
  
  <p>-- Read documentation on the architecture.  When I can find it, it gives a clear answer as to how many cycles a shift, or an &amp; take-- however, it is still difficult to tell, just how many cycles would a cached minus operation take, or how much of performance drawback I am incurring by pushing useful data out of the cache in order to load the <code>array[b]</code> data.</p>
  
  <p>-- Run the same code many million times in a row.  However, this results in the array remaining in the cache, and therefore giving a faster performance.</p>
  
  <p>-- Run the same code many million times, and in between the runs run some code to put / read other data in the cache.  However, there is a lot of variability in the running time, from me putting and accessing data in the cache, and the standard deviation is too big for the results to be reliable.</p>
  
  <p>-- Thanks to a suggestion by @klutt, I pasted these methods into the real code, and the first three methods seem to have equal performance.  What is probably happening is, all three methods can finish executing while the program is waiting for another value to be pulled up from the cache, later on in the program.  However, in case the program changes later (e.g., less cache lookups), then one of these methods might become preferable to the others.</p>
  
  <p>If I do not wish to revisit my reduction mod 2^* code every time the program changes, is there another, better method, to measure which of these is faster?</p>