6 ms·

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

RantyDave 6y ago
What's wrong with unordered map?
- ezoe 6y ago
  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.
  - gpderetta 6y ago
    > contagious normally I wouldn't point out an obvious autocorrect mistake, but this is really season-appropriate (or, better, inappropriate) :).
    - ezoe 6y ago
      Oh that's... not intended really.
  - TwoBit 6y ago
    So use unordered_map with an allocator that returns nodes from a small local memory?
    - josefx 6y ago
      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?
ezoe 6y ago
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.
cozzyd 6y ago
why not just define std::dict or something like that that is better?
- WesternStar 6y ago
  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.
  - gpderetta 6y ago
    I think the parent is proposing adding a better hash map to the standard library but with a different name to preserve backward compatibility.
  - imtringued 6y ago
    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.
alexhutcheson 6y ago
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/begin2 https://en.cppreference.com/w/cpp/container/unordered_map/be...
- SamReidHughes 6y ago
  You can just remove those functions. The real problem is that the API break would invalidate iterators and create undefined behavior.
UncleMeat 6y ago
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.

RantyDave 6y ago

What's wrong with unordered map?

ezoe 6y ago
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.
- gpderetta 6y ago
  > contagious normally I wouldn't point out an obvious autocorrect mistake, but this is really season-appropriate (or, better, inappropriate) :).
  - ezoe 6y ago
    Oh that's... not intended really.
- TwoBit 6y ago
  So use unordered_map with an allocator that returns nodes from a small local memory?
  - josefx 6y ago
    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?

ezoe 6y ago

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.

cozzyd 6y ago

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

WesternStar 6y ago
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.
- gpderetta 6y ago
  I think the parent is proposing adding a better hash map to the standard library but with a different name to preserve backward compatibility.
- imtringued 6y ago
  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.

alexhutcheson 6y ago

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/begin2 https://en.cppreference.com/w/cpp/container/unordered_map/be...

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

UncleMeat 6y ago

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.