[libcxx] r274857 - [libc++] Check hash before calling __hash_table key_eq function

[Kwasi Mensah via cfe-commits]

Author: kmensah
Date: Fri Jul  8 10:34:28 2016
New Revision: 274857

URL: http://llvm.org/viewvc/llvm-project?rev=274857=rev
Log:
[libc++] Check hash before calling __hash_table key_eq function

Summary: 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.

Reviewers: EricWF

Subscribers: kmensah, cfe-commits

Differential Revision: http://reviews.llvm.org/D21510

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=274857=274856=274857=diff
==
--- libcxx/trunk/include/__hash_table (original)
+++ libcxx/trunk/include/__hash_table Fri Jul  8 10:34:28 2016
@@ -2205,7 +2205,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>
 || __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
@@ -2235,7 +2235,7 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>
 || __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

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

[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

[PATCH] D16363: Add option to specify clang-format binary for clang-format-diff

[Kwasi Mensah via cfe-commits]

kmensah created this revision.
kmensah added a reviewer: djasper.
kmensah added a subscriber: cfe-commits.
kmensah set the repository for this revision to rL LLVM.

A command line option that lets users of the script specify which clang-format 
binary to use. Useful if clang-format is not on PATH or you want more control 
over which binary gets chosen.

Repository:
  rL LLVM

http://reviews.llvm.org/D16363

Files:
  clang-format-diff.py

Index: clang-format-diff.py
===
--- clang-format-diff.py
+++ clang-format-diff.py
@@ -30,11 +30,8 @@
 import StringIO
 import sys
 
+binary_default = 'clang-format'
 
-# Change this to the full path if clang-format is not on the path.
-binary = 'clang-format'
-
-
 def main():
   parser = argparse.ArgumentParser(description=
'Reformat changed lines in diff. Without -i 
'
@@ -60,6 +57,11 @@
   '-style',
   help=
   'formatting style to apply (LLVM, Google, Chromium, Mozilla, WebKit)')
+  parser.add_argument(
+  '-binary',
+  default=binary_default,
+  help=
+  'location of binary to use for clang-format')
   args = parser.parse_args()
 
   # Extract changed lines for each file.
@@ -95,7 +97,7 @@
   for filename, lines in lines_by_file.iteritems():
 if args.i and args.verbose:
   print 'Formatting', filename
-command = [binary, filename]
+command = [args.binary, filename]
 if args.i:
   command.append('-i')
 if args.sort_includes:


Index: clang-format-diff.py
===
--- clang-format-diff.py
+++ clang-format-diff.py
@@ -30,11 +30,8 @@
 import StringIO
 import sys
 
+binary_default = 'clang-format'
 
-# Change this to the full path if clang-format is not on the path.
-binary = 'clang-format'
-
-
 def main():
   parser = argparse.ArgumentParser(description=
'Reformat changed lines in diff. Without -i '
@@ -60,6 +57,11 @@
   '-style',
   help=
   'formatting style to apply (LLVM, Google, Chromium, Mozilla, WebKit)')
+  parser.add_argument(
+  '-binary',
+  default=binary_default,
+  help=
+  'location of binary to use for clang-format')
   args = parser.parse_args()
 
   # Extract changed lines for each file.
@@ -95,7 +97,7 @@
   for filename, lines in lines_by_file.iteritems():
 if args.i and args.verbose:
   print 'Formatting', filename
-command = [binary, filename]
+command = [args.binary, filename]
 if args.i:
   command.append('-i')
 if args.sort_includes:
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits