Check for unconstrained hash equality before constrained hash equality.
authorEric Fiselier <eric@efcs.ca>
Sun, 17 Jul 2016 22:04:57 +0000 (22:04 +0000)
committerEric Fiselier <eric@efcs.ca>
Sun, 17 Jul 2016 22:04:57 +0000 (22:04 +0000)
commit6a411472e3c4d707a3e25058f9ffadb25691a7f5
tree0d9076f16575daeac4d722f26e232d26cfc4458a
parent5fe4d141e07c1c868c1a11a2b52cfb1ad829c086
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%.

llvm-svn: 275734
libcxx/include/__hash_table