Hacker News Reader

Comment by ori_b | Hacker News Reader

If you overspecify, you close the door to better implementations. This is why, for example, C++ standard hash tables and regexes are an order of magnitude slower than third party ones.

The standard didn't say "you must implement std::unordered_map as a hash table with chained buckets and extra memory allocations", but ithe standard specified several guarantees that make it very difficult to implement hash tables with open addressing.

Every constraint that you specify potentially locks out a better implementation.

For recursive rwlocks, there's a lot of ways to implement them. Do you want to lock out high performance implementations that do less error checking, for example?

View on HN

This is exactly the issue, and unordered_map exemplifies it perfectly.

On paper, unordered_map sounds great. It lists all the admirable properties you would theoretically want in a hashtable. Then in practice when you go to implement it, you realize that you've painted yourself into a garbage fire, as the saying goes.

I suppose this is a failing of the design by committee method, where the committee isn't directly responsible for implementation either before or during standard writing.

OTOH, 99% of use cases don't care about performance and just want a portable implementation.

While it could be useful to have a "fast" variation that offers no guarantee at all, what you would end up with (because people are vain) is that too may people would use those instead "because perf", even though the actual usage is not performance critical, and have code that breaks whenever the compiler or platform changes.

> OTOH, 99% of use cases don't care about performance

For many other languages, I'd agree with '99%', but in the case of c++, performance is one of the main reasons it's still used, so I doubt the number is nearly that high.

With hindsight, I'd say that std::unordered_map is fine for what it is, but there are a lot of cases where it's really not suitable due to having a dynamic allocation for each element and the resulting lack of cache locality, and because of that many people have to go looking elsewhere for a usable hash map. There are good reasons why we have both std::vector and std::list.

To clarify, I believe the issue is C++ unordered map iterators and when / where they are allowed to go invalid.

OpenAddressing means that an address of map[thing] could change on insert. Which means iterators and pointer invalidation concepts can go stale on insert.

C++11 standard for unordered_map guarantees this won't happen. But that forces slower implementations.

And now people rely upon the standard so we can't change it. At best we do fast_unordered_map or unordered_map2 with different guarantees.

There are numerous factors where std::unordered_map makes API design choices that you would not make today and the invalidation of iterators (or lack thereof) is just one. A particularly frustrating issue is that std::unordered_map promises some things we suspect nobody cares about, but whereas Rust routinely does "crater runs" in which they discover to a good approximation whether their changes break the ecosystem (via hidden ABI dependencies, Hyrum's law etc.) there is little equivalent for C++ and much scare mongering about claimed large codebases hidden from sight which may use absolutely anything.

The most stupid thing about std::unordered_map is that it was standardized in 2011, so it isn't from 1998 like much of the C++ standard library containers, it's newer and yet apparently nothing was learned.

It was standardized in c++11, but it was standardizing hash_map that was in the original STL pre-C++98 and was available as an extension in most STL derived standard libraries.

For me the remaining reason I still reach for unordered_map is if I need reference stability as most faster hash tables don't provide it (and I don't care enough about performance to build reference stability on top of a better hash map).

When you want reference stability, do you need references to stay working even where something moved to a different hash table?

That is suppose we have two std::unordered_map<Goose> labelled A and B, and we put a particular Goose in A, later we get a reference to it, and we might, or might not, move it to B, but it definitely still exists. Do you need that? (As I understand it this is in fact what you get in std::unordered_map today)

Or for your purposes is it enough that it works only so long as the goose we're referring to is in A still and if we moved it out of A then it's fine that the reference is invalidated ?

If I need the lifetime of an object to outlive it's presence in the map then I use boost intrusive or simply a map of (smart) pointers.

For me it is usually when I need a multi indexed map where I use a fast map of pointers for the fast access and unordered_map both to keep the object alive and as a secondary access key.

Really I should use boost intrusive or boost multiindex, but these days I value the implementation simplicity in many cases, even if I have to keep the indices in sync myself

Can you use the CPython approach: an open-addressed hashtable mapping keys to indices into a dynamic array holding (pointers to) the actual keys and values? (Reference stability of course precludes implementing deletes by moving the last key/value entry into the vacated slot; instead you must track empty slots for reuse.)

As soon as the hashmap needs to resize the array will be realloc’d, so it won’t be stable unless you add virtual memory tricks or an indirection via some sort of segmented array.

Of course. That's just map<obj*>. The pointer-to-pointers could move but the pointers are now staying put. But now you have a bit of a lifetime worry.

Map<shared_ptr<obj>> with weak_ptr probably is the best general solution. If the object decided to delete itself the weakptr will be set to null.

And if you underspecify, you force the users to invent their own hacks and workarounds, often very poorly.

And no, I don't want to "high performance" lock implementations that regularly completely deadlock the whole process (deadlocked processes are not very performant) unless wrap every single one of the several hundred uses of them in a test with dubiously-predictable branches, or worse, just completely break the lock invariants (e.g., the lock is now permanently unlocked, even after a lock() on it succeeds) ― it really is not that important how fast you can do the wrong thing.

However, recursive locking is a bad idea overall, and the tracking needed to make it work on rwlock contexts isn't worth the overhead it imposes in the common case of non-recursive rwlocks.

It would be better if the spec simply said it was disallowed.

Reply on news.ycombinator.com