From patchwork Tue Sep  6 10:26:10 2011
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: [v3] libstdc++/50257
Date: Tue, 06 Sep 2011 00:26:10 -0000
From: Paolo Carlini <paolo.carlini@oracle.com>
X-Patchwork-Id: 113526
Message-Id: <4E65F542.9010400@oracle.com>
To: "gcc-patches@gcc.gnu.org" <gcc-patches@gcc.gnu.org>
Cc: libstdc++ <libstdc++@gcc.gnu.org>

Hi,

tested x86_64-linux, committed to mainline. See audit trail for details...

Thanks,
Paolo.

/////////////////////
2011-09-06  Paolo Carlini  <paolo.carlini@oracle.com>

	PR libstdc++/50257
	* include/bits/hashtable_policy.h (_Prime_rehash_policy::
   	_M_next_bkt): Optimize for small argument.


Index: include/bits/hashtable_policy.h
===================================================================
--- include/bits/hashtable_policy.h	(revision 178574)
+++ include/bits/hashtable_policy.h	(working copy)
@@ -427,8 +427,15 @@
   _Prime_rehash_policy::
   _M_next_bkt(std::size_t __n) const
   {
-    const unsigned long __p = *std::lower_bound(__prime_list, __prime_list
-						+ _S_n_primes, __n);
+    // Optimize lookups involving the first elements of __prime_list.
+    // (useful to speed-up, eg, constructors)
+    static const unsigned char __fastbkt[12]
+      = { 2, 2, 2, 3, 5, 5, 7, 7, 11, 11, 11, 11 };
+
+    const unsigned long __p
+      = __n <= 11 ? __fastbkt[__n]
+                  : *std::lower_bound(__prime_list + 5,
+				      __prime_list + _S_n_primes, __n);
     _M_next_resize =
       static_cast<std::size_t>(__builtin_floor(__p * _M_max_load_factor));
     return __p;