title: Why does random extra code improve performance?
body: <pre><code>Struct Node {
      Node *N[SIZE];
      int value;
  };
  
  struct Trie {
      Node *root;
  
      Node* findNode(Key *key) {
          Node *C = &amp;root;
          char u;
          while (1) {
              u = key-&gt;next();
              if (u &lt; 0) return C;
           // if (C-&gt;N[0] == C-&gt;N[0]); // this line will speed up execution significantly
              C = C-&gt;N[u];
              if (C == 0) return 0;
          }
      }
      void addNode(Key *key, int value){...};
  };
  </code></pre>
  
  <p>In this implementation of Prefix Tree (aka Trie) I found out that 90% of <code>findNode()</code> execution time is taken by a single operation <code>C=C-&gt;N[u];</code></p>
  
  <p>In my attempt to speed up this code, I randomly added the line that is commented in the snipped above, and code became 30% faster! Why is that?</p>
  
  <p>UPDATE</p>
  
  <p>Here is complete program.</p>
  
  <pre><code>#include "stdio.h"
  #include "sys/time.h"
  
  long time1000() {
    timeval val;
    gettimeofday(&amp;val, 0);
    val.tv_sec &amp;= 0xffff;
    return val.tv_sec * 1000 + val.tv_usec / 1000;
  }
  
  struct BitScanner {
      void *p; 
      int count, pos;
      BitScanner (void *p, int count) {
          this-&gt;p = p;
          this-&gt;count = count;
          pos = 0;
      }
      int next() {
          int bpos = pos &gt;&gt; 1;
          if (bpos &gt;= count) return -1;
          unsigned char b = ((unsigned char*)p)[bpos];
          if (pos++ &amp; 1) return (b &gt;&gt;= 4);
          return b &amp; 0xf;
      }
  
  };
  
  struct Node {
      Node *N[16];
      __int64_t value;
      Node() : N(), value(-1) { }
  };
  
  struct Trie16 {
      Node root;
  
      bool add(void *key, int count, __int64_t value) {
          Node *C = &amp;root;
          BitScanner B(key, count);
          while (true) {
              int u = B.next();
              if (u &lt; 0) {
                  if (C-&gt;value == -1) {
                      C-&gt;value = value;
                      return true; // value added
                  }
                  C-&gt;value = value;
                  return false; // value replaced
              }
              Node *Q = C-&gt;N[u];
              if (Q) {
                  C = Q;
              } else {
                  C = C-&gt;N[u] = new Node;
              }
          }
      }
  
      Node* findNode(void *key, int count) {
          Node *C = &amp;root;
          BitScanner B(key, count);
          while (true) {
              char u = B.next();
              if (u &lt; 0) return C;
  //          if (C-&gt;N[0] == C-&gt;N[1]);
              C = C-&gt;N[0+u];
              if (C == 0) return 0;
          }
      }
  };
  
  int main() {
      int T = time1000();
      Trie16 trie;
      __int64_t STEPS = 100000, STEP = 500000000, key;
      key = 0;
      for (int i = 0; i &lt; STEPS; i++) {
          key += STEP;
          bool ok = trie.add(&amp;key, 8, key+222);
      }
      printf("insert time:%i\n",time1000() - T); T = time1000();
      int err = 0;
      key = 0;
      for (int i = 0; i &lt; STEPS; i++) {
          key += STEP;
          Node *N = trie.findNode(&amp;key, 8);
          if (N==0 || N-&gt;value != key+222) err++;
      }
      printf("find time:%i\n",time1000() - T); T = time1000();
      printf("errors:%i\n", err);
  }
  </code></pre>