6 ms·

Author here. > This starts at fairly fundamental data structures. Need a hash map? In Rust you have one available, out-of-box, with state-of-art performance. I

Author here. > This starts at fairly fundamental data structures. Need a hash map? In Rust you have one available, out-of-box, with state-of-art performance. In C? Implement one yourself. And good luck getting even a fraction of the performance the Rust one has. I've implemented a hash map in my code. I loved the experience, and I know more about computers and hash maps now that I've done it. And my hash map was faster than the one in the C++ STL last I checked. I haven't benchmarked it against the Rust one, though.

kouteiheika 4y ago
> I've implemented a hash map in my code. I loved the experience, and I know more about computers and hash maps now that I've done it. Yep, everyone at least once should implement a hash map. Hash maps are so fundamental and so often used that it really pays off to understand what makes them tick. > And my hash map was faster than the one in the C++ STL last I checked. I haven't benchmarked it against the Rust one, though. The one in C++ is very famous for being really slow, so this is a low bar to clear. (: Not sure if someone directly compared Rust's hash map to C++'s, but Rust's hash map is based on Google's SwissTable, so you can probably assume it performs roughly the same. Here are some graphs: https://youtu.be/ncHmEUmJZf4?t=2093 https://youtu.be/ncHmEUmJZf4?t=2093
- menaerus 4y ago
  > The one in C++ is very famous for being really slow, so this is a low bar to clear. (: There's nothing wrong with the C++ hash-map. It's a different trade-off which makes perfect sense for something that is part of the general-purpose toolbox. See my response above for more details if interested.
menaerus 4y ago
> And my hash map was faster than the one in the C++ STL last I checked. Last time I checked, benchmarking hash-maps, or FWIW any other data structure, in the vacuum did not make much sense to me. Microbenchmarks cannot mimic or predict end user workloads well enough, at least in the cases where it's worth it. That said, each implementation has its own trade-offs and in particular the one from C++ STL opted in for the pointer stability. For that reason alone, which I think is quite worthy, open-addressing conflict resolution is out of the question because it cannot give such guarantees. With that in mind, if you're ok that a pointer to your key-value pair can all of the sudden be _invalidated_ by the mere operation of inserting or erasing yet another element from your hash-map, then of course, you can trade robustness for a more cache-friendly conflict resolution algorithm. But then again, this says nothing about the potential performance improvement unless you're able to measure it.

kouteiheika 4y ago

> I've implemented a hash map in my code. I loved the experience, and I know more about computers and hash maps now that I've done it. Yep, everyone at least once should implement a hash map. Hash maps are so fundamental and so often used that it really pays off to understand what makes them tick. > And my hash map was faster than the one in the C++ STL last I checked. I haven't benchmarked it against the Rust one, though. The one in C++ is very famous for being really slow, so this is a low bar to clear. (: Not sure if someone directly compared Rust's hash map to C++'s, but Rust's hash map is based on Google's SwissTable, so you can probably assume it performs roughly the same. Here are some graphs: https://youtu.be/ncHmEUmJZf4?t=2093 https://youtu.be/ncHmEUmJZf4?t=2093

menaerus 4y ago
> The one in C++ is very famous for being really slow, so this is a low bar to clear. (: There's nothing wrong with the C++ hash-map. It's a different trade-off which makes perfect sense for something that is part of the general-purpose toolbox. See my response above for more details if interested.

menaerus 4y ago

> And my hash map was faster than the one in the C++ STL last I checked. Last time I checked, benchmarking hash-maps, or FWIW any other data structure, in the vacuum did not make much sense to me. Microbenchmarks cannot mimic or predict end user workloads well enough, at least in the cases where it's worth it. That said, each implementation has its own trade-offs and in particular the one from C++ STL opted in for the pointer stability. For that reason alone, which I think is quite worthy, open-addressing conflict resolution is out of the question because it cannot give such guarantees. With that in mind, if you're ok that a pointer to your key-value pair can all of the sudden be _invalidated_ by the mere operation of inserting or erasing yet another element from your hash-map, then of course, you can trade robustness for a more cache-friendly conflict resolution algorithm. But then again, this says nothing about the potential performance improvement unless you're able to measure it.