title: Strange performance observed with memoized function
body: <p>I was toying around with something that uses Euclid's algorithm to computed the GCD of two numbers.  I implemented the standard one-liner as usual, and it worked fine.  It's used in a algorithm that computes a series and calls <code>gcd()</code> several times per element as <code>n</code> gets larger.  I decided to see if I could do better by memoizing, so here is what I tried:</p>
  
  <pre><code>size_t const gcd(size_t const a, size_t const b) {
    return b == 0 ? a : gcd(b, a % b);
  }
  
  struct memoized_gcd : private std::unordered_map&lt;unsigned long long, size_t&gt; {
    size_t const operator()(size_t const a, size_t const b) {
      unsigned long long const key = (static_cast&lt;unsigned long long&gt;(a) &lt;&lt; 32) | b;
      if (find(key) == end()) (*this)[key] = b == 0 ? a : (*this)(b, a % b);
      return (*this)[key];
    }
  };
  
  //std::function&lt;size_t (size_t, size_t)&gt; gcd_impl = gcd&lt;size_t,size_t&gt;;
  std::function&lt;size_t (size_t, size_t)&gt; gcd_impl = memoized_gcd();
  </code></pre>
  
  <p>I call the chosen function through the <code>std::function</code> instance later.  Interestingly, when for example n = 10,000, the calculation runs in 8 sec on this computer, and with the memoized version it's close to a minute, everything else being equal.</p>
  
  <p>Have I missed something obvious?  I am using <code>key</code> as an expedient so that I don't need to specialize <code>std::hash</code> for the hash map.  The only things I can think of are maybe that the memoized version doesn't get the TCO and <code>gcd()</code> does, or that calling through the <code>std::function</code> is slow for the functor (even though I use it for both), or perhaps that I'm retarded.  Gurus, show me the way.</p>
  
  <p><strong>Notes</strong> </p>
  
  <p>I've tried this on win32 and win64 with g++ 4.7.0 and linux x86 with g++ 4.6.1 and 4.7.1.</p>
  
  <p>I also tried a version with a <code>std::map&lt;std::pair&lt;size_t, size_t&gt;, size_t&gt;</code> that had comparable performance to the unmemoized version.</p>