[Bug libstdc++/50257] [C++0x] unordered_map slow initialization due to huge __prime_list

[justin at fathomdb dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50257

--- Comment #9 from Justin SB <justin at fathomdb dot com> 2011-09-06 04:04:12 UTC ---
I think I personally prefer the original patches for readability, but I guess
it all depends on what gets optimized away.  But that caused me to think: how
about relying on constexpr?  We should be able to precompute the lookup for any
constant, while having the original runtime behaviour (no extra checks) for any
non-constant.

I tried the code below, and while it seems to be correct and satisfy the
constexpr rules, it doesn't get optimized away to a constant with gcc 4.6 (and
I'm ashamed to say I can't get the git version of gcc to build at the moment)

If this could be made to work, I think this could be a great approach, in that
we're then not trading off the constant/non-constant cases against each other.

(Optimizing small non-constexpr values as you've done in this latest patch
might also be helpful for performance, but I don't know if that really happens
much in practice; I suspect if a caller goes to the trouble of specifying a
small size they know that the hash is very unlikely to grow beyond that size)

---

#include <iostream>

using namespace std;

constexpr int primes[] = { 2, 3, 5, 7, 11, 13}; 

constexpr int primes_lower_bound(int __first, int __last, int __val)
{
  return (__first == __last)
    ? primes[__first]
    : (primes[__first + ((__last - __first) >> 1)] < __val)
      ? primes_lower_bound(__first + ((__last - __first) >> 1) + 1, __last,
__val) 
      : primes_lower_bound(__first, __first + ((__last - __first) >> 1),
__val);
}

static_assert( primes_lower_bound( 0, 6, 10) == 11, "Sanity check error");

constexpr int next_prime(int k) {
return primes_lower_bound( 0, 6, k);
}

int main() {
cout << next_prime(10) << endl;
return 0;
}