undefined | Better HN

0 points_gabe_3y ago0 comments

It looks like caching definitely skewed the results a bit. You can take a look at the linked code yourself. Worst case was still only around 80 nanoseconds which is definitely slower, but still orders of magnitude faster than "sub 5 micros".

Don't take my word for it though, you can take a look at the Robin Hood benchmarks[0]. Robin Hood unordered map is a competitive hash map that's performed much better than the STL for me in many cases. They average a 4 nanosecond lookup speed for a hash map with 2000 elements and an integer key.

> Did you benchmark against Java's HashMap?

I benchmarked against C#, which has a runtime that performs similar if not better than the JVM. The C# code was a ~~few microseconds~~ around 130 nanoseconds. Which is still very fast, but up to 100x slower. (And yes, this was after warming up the code. I used benchmark dot net[1] here.). This is a really easy benchmark to set up. If you doubt me you can write a couple of benchmarks in under an hour and compare yourself.

[0]: https://martin.ankerl.com/2019/04/01/hashmap-benchmarks-04-0...

[1]: https://benchmarkdotnet.org/articles/overview.html

0 comments

titzer3y ago

Did I read that right? The C# version is computing SHA256 hashes?

_gabe_OP3y ago

That's a link to the benchmark framework that I used. The C# benchmark are in a separate gist that I didn't feel like digging up. This is the C# benchmarks[0]. All the interfaces and indirection is the result of me adapting this from a separate comment. But the benchmark is just testing `HashSet.TryGetValue`.

Edit: I just re-ran the benchmarks because I didn't have the results pasted in the snippet (which I've now done so I don't keep getting this wrong haha). The C# HashSet takes around 130 nanoseconds, not microseconds. So it's not orders of magnitude slower, but it is still more than a 2x slow down and up to a 100x slow down in the case of an integer key.

[0]: https://gist.github.com/ambrosiogabe/ba6bd0fa80588c2fd2ca26d...

j / k navigate · click thread line to collapse