kmensah created this revision.
kmensah added a subscriber: cfe-commits.
kmensah set the repository for this revision to rL LLVM.
The current implementations of __hash_table::find used by
std::unordered_set/unordered_map call key_eq on each key that lands in the same
bucket as the key you're looking for. However, since equal objects mush hash to
the same value, you can short-circuit the possibly expensive call to key_eq by
checking the hashes first.
Repository:
rL LLVM
http://reviews.llvm.org/D21510
Files:
include/__hash_table
Index: include/__hash_table
===================================================================
--- include/__hash_table
+++ include/__hash_table
@@ -2200,7 +2200,7 @@
__constrain_hash(__nd->__hash_, __bc)
== __chash;
__nd =
__nd->__next_)
{
- if (key_eq()(__nd->__value_, __k))
+ if ((__nd->__hash_ == __hash) && key_eq()(__nd->__value_, __k))
#if _LIBCPP_DEBUG_LEVEL >= 2
return iterator(__nd, this);
#else
@@ -2229,7 +2229,7 @@
__constrain_hash(__nd->__hash_,
__bc) == __chash;
__nd =
__nd->__next_)
{
- if (key_eq()(__nd->__value_, __k))
+ if ((__nd->__hash_ == __hash) && key_eq()(__nd->__value_, __k))
#if _LIBCPP_DEBUG_LEVEL >= 2
return const_iterator(__nd, this);
#else
Index: include/__hash_table
===================================================================
--- include/__hash_table
+++ include/__hash_table
@@ -2200,7 +2200,7 @@
__constrain_hash(__nd->__hash_, __bc) == __chash;
__nd = __nd->__next_)
{
- if (key_eq()(__nd->__value_, __k))
+ if ((__nd->__hash_ == __hash) && key_eq()(__nd->__value_, __k))
#if _LIBCPP_DEBUG_LEVEL >= 2
return iterator(__nd, this);
#else
@@ -2229,7 +2229,7 @@
__constrain_hash(__nd->__hash_, __bc) == __chash;
__nd = __nd->__next_)
{
- if (key_eq()(__nd->__value_, __k))
+ if ((__nd->__hash_ == __hash) && key_eq()(__nd->__value_, __k))
#if _LIBCPP_DEBUG_LEVEL >= 2
return const_iterator(__nd, this);
#else
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
