Page MenuHomePhabricator

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

Authored by kmensah on Jun 19 2016, 1:31 PM.

Details

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.

Diff Detail

Repository
rL LLVM

Event Timeline

kmensah updated this revision to Diff 61223.Jun 19 2016, 1:31 PM
kmensah retitled this revision from to [libc++] Check hash before calling __hash_table key_eq function.
kmensah updated this object.
kmensah set the repository for this revision to rL LLVM.
kmensah added a subscriber: cfe-commits.

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

Friendly Ping about this

Another friendly Ping

EricWF accepted this revision.Jun 29 2016, 11:15 PM
EricWF edited edge metadata.

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.
  1. 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.
  1. 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.
This revision is now accepted and ready to land.Jun 29 2016, 11:15 PM

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

kmensah closed this revision.Jul 8 2016, 8:41 AM