Re: [PATCH] D21510: [libc++] Check hash before calling __hash_table key_eq function

[Kwasi Mensah via cfe-commits]

kmensah added a comment.

Thanks. For future reference, do these benchmarking tests live some place
where I can run them myself in the future?


Repository:
  rL LLVM

http://reviews.llvm.org/D21510



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

Re: [PATCH] D21510: [libc++] Check hash before calling __hash_table key_eq function

[Kwasi Mensah via cfe-commits]

Thanks. For future reference, do these benchmarking tests live some place
where I can run them myself in the future?

On Thu, Jun 30, 2016 at 2:15 AM, Eric Fiselier  wrote:

> EricWF accepted this revision.
> EricWF added a comment.
> This revision is now accepted and ready to land.
>
> LGTM. I benchmarked the change against different key types and:
>
> 1. The change doesn't have a large detrimental impact when the key
> equality is as expensive as hash equality. I benchmarked
> std::unordered_set.find(...) at 27ns and 29ns before and after the
> change for a load factor >= 3.5, and 15ns vs 17 ns when the load factor is
> less than one.
>
> 2. The change has a large positive impact when the load factor is > 1 and
> where key equality is more expensive than hash equality. For strings of
> size 1024 that only differed in the last characters I noticed a change of
> 880ns to 650ns. for a load factor >= 3.5.
>
> 3. This change has a slight positive inpact when the load factor is < 1.
> For the same string inputs (mentioned above)  I  saw timings of 661ns and
> 623ns before and after.
>
>
>
>
> Repository:
>   rL LLVM
>
> http://reviews.llvm.org/D21510
>
>
>
>
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

Re: [PATCH] D21510: [libc++] Check hash before calling __hash_table key_eq function

[Eric Fiselier via cfe-commits]

EricWF accepted this revision.
EricWF added a comment.
This revision is now accepted and ready to land.

LGTM. I benchmarked the change against different key types and:

1. The change doesn't have a large detrimental impact when the key equality is 
as expensive as hash equality. I benchmarked std::unordered_set.find(...) 
at 27ns and 29ns before and after the change for a load factor >= 3.5, and 15ns 
vs 17 ns when the load factor is less than one.

2. The change has a large positive impact when the load factor is > 1 and where 
key equality is more expensive than hash equality. For strings of size 1024 
that only differed in the last characters I noticed a change of 880ns to 650ns. 
for a load factor >= 3.5.

3. This change has a slight positive inpact when the load factor is < 1. For 
the same string inputs (mentioned above)  I  saw timings of 661ns and 623ns 
before and after.




Repository:
  rL LLVM

http://reviews.llvm.org/D21510



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

Re: [PATCH] D21510: [libc++] Check hash before calling __hash_table key_eq function

[Kwasi Mensah via cfe-commits]

kmensah added a comment.

Another friendly Ping


Repository:
  rL LLVM

http://reviews.llvm.org/D21510



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

Re: [PATCH] D21510: [libc++] Check hash before calling __hash_table key_eq function

[Kwasi Mensah via cfe-commits]

kmensah added a subscriber: kmensah.
kmensah added a comment.

Friendly Ping about this


Repository:
  rL LLVM

http://reviews.llvm.org/D21510



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

Re: [PATCH] D21510: [libc++] Check hash before calling __hash_table key_eq function

[Kwasi Mensah via cfe-commits]

kmensah added a comment.

I've run make make check-libcxx and this seems to pass fine.


Repository:
  rL LLVM

http://reviews.llvm.org/D21510



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D21510: [libc++] Check hash before calling __hash_table key_eq function

[Kwasi Mensah via cfe-commits]

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