Author: ericwf
Date: Sun Jul 17 17:04:57 2016
New Revision: 275734
URL: http://llvm.org/viewvc/llvm-project?rev=275734&view=rev
Log:
Check for unconstrained hash equality before constrained hash equality.
This patch implements a simple optimization in __hash_table::find. When
iterating
the found bucket we only constrain the bucket elements hash if it doesn't
already match the unconstrained hash of the specified key. This prevent
the performance of an expensive modulo operation.
Since the bucket element almost always matches the key, especially when the
load factor is low, this optimization has large performance impacts. For
a unordered_set<int> of random integers this patch improves the performance of
'find(...)' by 40%.
Modified:
libcxx/trunk/include/__hash_table
Modified: libcxx/trunk/include/__hash_table
URL:
http://llvm.org/viewvc/llvm-project/libcxx/trunk/include/__hash_table?rev=275734&r1=275733&r2=275734&view=diff
==============================================================================
--- libcxx/trunk/include/__hash_table (original)
+++ libcxx/trunk/include/__hash_table Sun Jul 17 17:04:57 2016
@@ -2202,7 +2202,8 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>
if (__nd != nullptr)
{
for (__nd = __nd->__next_; __nd != nullptr &&
- __constrain_hash(__nd->__hash_, __bc) == __chash;
+ (__nd->__hash_ == __hash
+ || __constrain_hash(__nd->__hash_, __bc) == __chash);
__nd =
__nd->__next_)
{
if ((__nd->__hash_ == __hash) && key_eq()(__nd->__value_, __k))
@@ -2231,7 +2232,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>
if (__nd != nullptr)
{
for (__nd = __nd->__next_; __nd != nullptr &&
- __constrain_hash(__nd->__hash_, __bc) == __chash;
+ (__hash == __nd->__hash_ || __constrain_hash(__nd->__hash_,
__bc) == __chash);
__nd =
__nd->__next_)
{
if ((__nd->__hash_ == __hash) && key_eq()(__nd->__value_, __k))
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
