[libc++] Check hash before calling __hash_table key_eq function

[kmensah]

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.

[kmensah]

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

[kmensah]

Friendly Ping about this

[kmensah]

Another friendly Ping

[EricWF]

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<int>.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.

[kmensah]

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

include/__hash_table

if (__bc != 0)
         size_t __chash = __constrain_hash(__hash, __bc);
         __node_pointer __nd = __bucket_list_[__chash];
         if (__nd != nullptr)
         {
             for (__nd = __nd->__next_; __nd != nullptr &&
                                        __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
                     return iterator(__nd);
 #endif
             }
         }
     }
if (__bc != 0)
         size_t __chash = __constrain_hash(__hash, __bc);
         __node_const_pointer __nd = __bucket_list_[__chash];
         if (__nd != nullptr)
         {
             for (__nd = __nd->__next_; __nd != nullptr &&
                                            __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
                     return const_iterator(__nd);
 #endif
             }
         }