Hacker News Reader

Hacker News

Comment by amelius | Hacker News Reader

Full thread

amelius

Why didn't they just use the same algorithms as typical implementations of C++'s STL?

View on HN

Some resources which were on HN before about Robin-Hood hashing:

About Robin-Hood hashing: http://www.sebastiansylvan.com/post/robin-hood-hashing-shoul...

Rust's implementation of HashMap: http://cglab.ca/~abeinges/blah/robinhood-part-1/

Any algorithm you pick is going to have edge cases, and the C++ STL only defines the interfaces for interacting with them. This means that there is no "typical" implementation. Do you actually know how the implementation you're currently using is written?

I might be wrong but I thought the STL design docs also had restrictions on algorithm speed? As in - you are free to choose any design you want, as long as it has a given API and has O(1) access.

It's been a while, so my memory could be playing tricks on me. However, I believe the specified std::unordered_map iterator invalidation behavior rules out efficient use of open addressing unless someone comes up with some timsort-level novel implementation ideas.

I know some of the core algorithms used by GNU's implementation (libstdc++). But what the Rust team could do is compare the performance of different implementations, and pick the best one for each data structure.

... which they have done, for some definition of "best".

They've chosen an implementation with good cache locality and lower memory overhead (and presumably better average-case speed) than the chaining implementation usually used for std::unordered_map. The downside is that its worst-case speed is pretty bad.

On the other hand, I believe they use Siphash by default, which means it's very difficult to even intentionally trigger worst-case behavior without being able to inspect the process's memory for the random Siphash key.

std::unordered_map isn't particularly good. Its strength is that it can handle nearly all workloads without having abysmal performance. The price paid for that is that it's never actually all that good. If you know your workload, a "specialised" hash table can easily be 2x faster (e.g. Google's dense_hash_map).

This is because the standard makes some very specific complexity guarantees on operations and iterator validity. This practically forces standard-compliant implementations to use hashing with chaining, and not in the most efficient way. That's why it's universally bad and not just a bad implementation in any particular standard library. I don't remember the exact details, though.

But we are talking about a standard hash table here. I.e., one that should have consistent performance for general problems, and no surprising behavior whatsoever.

Imho, if the user wants better performance for special use cases, then they can search for better algorithms.

Despite the downvotes, I think you're absolutely right. "No surprises, okay performance" is what a standard library data structure or algorithm should strive for. Sometimes that works out really well for both criteria (libstdc++'s std::sort), but other times performance suffers as "no surprises" is more important (std::unordered_map).

Reply on news.ycombinator.com