Hacker News Reader

Comment by WesternStar | Hacker News Reader

<unpopular opinion>We should break ABI on unordered map just to stop embarrassing ourselves in public and in front of new users.</unpopular opinion>

View on HN

It’s unfortunately not just ABI, but also API. The standard specifies that you can get iterations to specific buckets in O(1)[1], and also specifies bucket_count(), max_bucket_count(), bucket_size() (which is specified to be O(n)), and bucket(). Those functions and their specified performance make it effectively impossible to implement a standards-compliant std::unordered_map without using separate chaining.

[1] https://en.cppreference.com/w/cpp/container/unordered_map/be...

You can just remove those functions. The real problem is that the API break would invalidate iterators and create undefined behavior.

I'm not even sure that is an unpopular opinion. Its a minority opinion, but people on the committee have been grumbling about how ABI consistency is hamstringing C++ for a while now.

What's wrong with unordered map?

It's implementation is buckets divided node based hash map. Theoretically, its order is good, but not that efficient in modern hardware where the memory access is heavily cached so the data locality is more important than saving the memory copy or memory size. Using the linked list to save some memory copy doesn't benefit at all and the overhead is far greater than simply copying the contagious large chunk of memory. Especially so if the data type is trivial so the simple byte by byte memcpy is suffice.

> contagious

normally I wouldn't point out an obvious autocorrect mistake, but this is really season-appropriate (or, better, inappropriate) :).

Oh that's... not intended really.

So use unordered_map with an allocator that returns nodes from a small local memory?

To be useful that would require that the nodes are allocated in the order they appear in the map (and still has pointer overhead). Is that a given with an unordered map or does it break down the moment the map is rehashed?

why not just define std::dict or something like that that is better?

Because you should be able to find a good hash data structure for your language. You shouldn't be able to accidentally get a bad one. It should arguably be the first data structure you reach for.

I think the parent is proposing adding a better hash map to the standard library but with a different name to preserve backward compatibility.

Deprecate the old data structure. Even Java did that. Originally it had the Vector class as primary List type. Nowadays everyone uses the List interface and ArrayLists as default implementation.

You can even find this in the javadoc of the Vector class:

>As of the Java 2 platform v1.2, this class was retrofitted to implement the List interface, making it a member of the Java Collections Framework. Unlike the new collection implementations, Vector is synchronized. If a thread-safe implementation is not needed, it is recommended to use ArrayList in place of Vector.

The problem is, hash map isn't that effective in modern hardware, the overhead cost is greater than the benefit. If it's consists of clustered network connected computers, it may be, but not for the single local computer for the most of problem.

Reply on news.ycombinator.com