5 ms·

I disagree with having the ordering embedded into the map implementation. That imposes an unnecessary performance overhead to support a small subset of use case

by kitd 2y ago

I disagree with having the ordering embedded into the map implementation. That imposes an unnecessary performance overhead to support a small subset of use cases. I think what the author requires is iterating over a sorted list of keys. That is pretty easy to implement using the standard library, and imposes the performance penalty only when it is needed.

DandyDev 2y ago
The author is not saying that ordering needs to be added to the _current_ map implementation. He suggests adding an additional map implementation that has ordering built in. That way, you can choose between functionality and (hypothetical) better performance The author does not seem to require iterating over a sorted list. Sorting is not the same as ordering. An ordered map is a map in which the insertion order is preserved when iterating over the elements. A sorted map outputs the elements in an order defined by a comparison function when iterating, regardless of their insertion order. You can for example sort alphabetical in case of string keys.
- deleted 2y ago
  [deleted]
masklinn 2y ago
> I disagree with having the ordering embedded into the map implementation. Good thing that's not what they are asking at all. They just want an ordered map to be in the standard library. > That imposes an unnecessary performance overhead to support a small subset of use cases. Naturally ordered hash maps generally have a small performance hit on lookup and a performance gain on iteration, as iteration goes through a dense array. Linked hash maps do tend to have worse performances for all cases. > I think what the author requires is iterating over a sorted list of keys. Had they needed that, they'd have said that. But they did not. And they specifically refer to an ordered map, and to Python's built-in and Ordered dicts, which are not sorted.
gizmo 2y ago
In most cases the performance penalty of having an extra internal array to keep track of insertion order is minimal, and the whole point of built-in collections is so people can quickly write correct programs. When optimizing for performance default collections are likely to get replaced with hand-rolled versions anyway. But in all other cases a dictionary that “just works” is preferable to one that has such an annoying footgun that the go team had to randomize the iteration order in an attempt to treat the symptom instead of choosing correctness. Go isn’t even a high-performance language and many language design choices (channels!) explicit prioritize correctness over performance. It’s like having an unstable sort as the default standard library sort function. People reasonably expect that when calling sort twice the second sort to do nothing, but you can always find people who will passionately argue that people deserve to get burned if they assume a sort function is stable.
- icholy 2y ago
  Yeah, who needs O(1) deletes anyway? /s
  - lifthrasiir 2y ago
    In case you haven't realized yet, a hash table that maintains the insertion order can be still do O(1) deletes as long as the key order doesn't change arbitrarily after the initial insertion.
    - icholy 2y ago
      I'm commenting on the proposed implementation of using an array to keep track of insertion order.
      - lifthrasiir 2y ago
        An array can be used to efficiently simulate a linked list and other data structure, however. (Or an intrusive linked list may be embedded into the bucket structure like PHP, but this is less efficient with open addressing scheme which is nowadays better for cache locality.)
tialaramex 2y ago
There are three distinct types being discussed here, let me try to briefly explain them. 1. Just a hash table, Rust's std::collections::HashMap, C++ std::unordered_map, Go's map This type is not about the "order" of its contents. If you want the "order" in any sense, that's not what this is for and you have the wrong type just as surely as if you were surprised that your integer type can't store a half. Types of this kind can be optimised to provide extremely fast indexing by key which is why they exist as this is useful in many problems. 2. A container arranged by the value of the keys, Rust's BTreeMap, C++ std::map This type is about the order of its contents by value. It doesn't matter when you put a 4 into this container, it goes between 3 and 5 anyway. This type is good when you need to work in that "by value" order later, for example to take the "Most important" item or the "Soonest". It doesn't remember the order in which things were added, and it is relatively slow to find items by their key. 3. A container forever arranged by order of insertion, Python's OrderedDict (and dict), in Rust that's https://crates.io/crates/linked-hash-map https://crates.io/crates/linked-hash-map LinkedHashMap This type remembers the order in which you inserted items into the container and can give them all back in that order efficiently. In other ways it's like the first container, but it compromises performance significantly to deliver this "order" promise. It is problematic that people talk past each other on this, both in terms of a useful discussion on HN, but much worse in a Software Engineerign team if you thought you were being given an OrderedDict, but it was actually a BTreeMap for example. Python chooses to provide (3) because Python is slow anyway so why not at least provide the least surprising container given how slow the language is. The existing Python dict was so awful that OrderedDict is actually faster (not fast in the wider scheme of things, but faster than that) so that's good enough.
- nbadg 2y ago
  Not to take away from your broader point (that different data types are appropriate in different scenarios), but: > Python chooses to provide (3) because Python is slow anyway so why not at least provide the least surprising container given how slow the language is. The existing Python dict was so awful that OrderedDict is actually faster (not fast in the wider scheme of things, but faster than that) so that's good enough. The python dict implementation is actually extremely optimized, and used in very critical hot paths throughout the interpreter and object model (for example, ``object.__dict__``). Additionally, python dicts (in cpython) are implemented in C, so any "slowness" there is going to be the result of the python code written to use the dictionary, and not the dict itself. Up until python 3.6, cpython dictionaries were not ordered. At version 3.6, cpython dicts were made ordered, but only as an implementation detail. And at version 3.7, the preserves-insertion-order property of dicts was officially made part of the language spec, so that all python implementations need to support it. The 3.6 change was made purely for performance reasons (and the stdlib already included an OrderedDict anyways). It was then made part of the language spec in 3.7 for several reasons: reduced maintenance burden for OrderedDict, convenience to developers using python, reducing the chance of accidental footguns of people relying on the implementation detail as if it were actually part of the language (and it then being removed later and breaking things), etc. The decision was made as part of this thread[1], if you're curious. [1] https://mail.python.org/pipermail/python-dev/2017-December/151263.html https://mail.python.org/pipermail/python-dev/2017-December/1...

by kitd 2y ago

DandyDev 2y ago

The author is not saying that ordering needs to be added to the _current_ map implementation. He suggests adding an additional map implementation that has ordering built in. That way, you can choose between functionality and (hypothetical) better performance The author does not seem to require iterating over a sorted list. Sorting is not the same as ordering. An ordered map is a map in which the insertion order is preserved when iterating over the elements. A sorted map outputs the elements in an order defined by a comparison function when iterating, regardless of their insertion order. You can for example sort alphabetical in case of string keys.

deleted 2y ago
[deleted]

masklinn 2y ago

> I disagree with having the ordering embedded into the map implementation. Good thing that's not what they are asking at all. They just want an ordered map to be in the standard library. > That imposes an unnecessary performance overhead to support a small subset of use cases. Naturally ordered hash maps generally have a small performance hit on lookup and a performance gain on iteration, as iteration goes through a dense array. Linked hash maps do tend to have worse performances for all cases. > I think what the author requires is iterating over a sorted list of keys. Had they needed that, they'd have said that. But they did not. And they specifically refer to an ordered map, and to Python's built-in and Ordered dicts, which are not sorted.

gizmo 2y ago

In most cases the performance penalty of having an extra internal array to keep track of insertion order is minimal, and the whole point of built-in collections is so people can quickly write correct programs. When optimizing for performance default collections are likely to get replaced with hand-rolled versions anyway. But in all other cases a dictionary that “just works” is preferable to one that has such an annoying footgun that the go team had to randomize the iteration order in an attempt to treat the symptom instead of choosing correctness. Go isn’t even a high-performance language and many language design choices (channels!) explicit prioritize correctness over performance. It’s like having an unstable sort as the default standard library sort function. People reasonably expect that when calling sort twice the second sort to do nothing, but you can always find people who will passionately argue that people deserve to get burned if they assume a sort function is stable.

icholy 2y ago
Yeah, who needs O(1) deletes anyway? /s
- lifthrasiir 2y ago
  In case you haven't realized yet, a hash table that maintains the insertion order can be still do O(1) deletes as long as the key order doesn't change arbitrarily after the initial insertion.
  - icholy 2y ago
    I'm commenting on the proposed implementation of using an array to keep track of insertion order.
    - lifthrasiir 2y ago
      An array can be used to efficiently simulate a linked list and other data structure, however. (Or an intrusive linked list may be embedded into the bucket structure like PHP, but this is less efficient with open addressing scheme which is nowadays better for cache locality.)

tialaramex 2y ago

There are three distinct types being discussed here, let me try to briefly explain them. 1. Just a hash table, Rust's std::collections::HashMap, C++ std::unordered_map, Go's map This type is not about the "order" of its contents. If you want the "order" in any sense, that's not what this is for and you have the wrong type just as surely as if you were surprised that your integer type can't store a half. Types of this kind can be optimised to provide extremely fast indexing by key which is why they exist as this is useful in many problems. 2. A container arranged by the value of the keys, Rust's BTreeMap, C++ std::map This type is about the order of its contents by value. It doesn't matter when you put a 4 into this container, it goes between 3 and 5 anyway. This type is good when you need to work in that "by value" order later, for example to take the "Most important" item or the "Soonest". It doesn't remember the order in which things were added, and it is relatively slow to find items by their key. 3. A container forever arranged by order of insertion, Python's OrderedDict (and dict), in Rust that's https://crates.io/crates/linked-hash-map https://crates.io/crates/linked-hash-map LinkedHashMap This type remembers the order in which you inserted items into the container and can give them all back in that order efficiently. In other ways it's like the first container, but it compromises performance significantly to deliver this "order" promise. It is problematic that people talk past each other on this, both in terms of a useful discussion on HN, but much worse in a Software Engineerign team if you thought you were being given an OrderedDict, but it was actually a BTreeMap for example. Python chooses to provide (3) because Python is slow anyway so why not at least provide the least surprising container given how slow the language is. The existing Python dict was so awful that OrderedDict is actually faster (not fast in the wider scheme of things, but faster than that) so that's good enough.

nbadg 2y ago
Not to take away from your broader point (that different data types are appropriate in different scenarios), but: > Python chooses to provide (3) because Python is slow anyway so why not at least provide the least surprising container given how slow the language is. The existing Python dict was so awful that OrderedDict is actually faster (not fast in the wider scheme of things, but faster than that) so that's good enough. The python dict implementation is actually extremely optimized, and used in very critical hot paths throughout the interpreter and object model (for example, ``object.__dict__``). Additionally, python dicts (in cpython) are implemented in C, so any "slowness" there is going to be the result of the python code written to use the dictionary, and not the dict itself. Up until python 3.6, cpython dictionaries were not ordered. At version 3.6, cpython dicts were made ordered, but only as an implementation detail. And at version 3.7, the preserves-insertion-order property of dicts was officially made part of the language spec, so that all python implementations need to support it. The 3.6 change was made purely for performance reasons (and the stdlib already included an OrderedDict anyways). It was then made part of the language spec in 3.7 for several reasons: reduced maintenance burden for OrderedDict, convenience to developers using python, reducing the chance of accidental footguns of people relying on the implementation detail as if it were actually part of the language (and it then being removed later and breaking things), etc. The decision was made as part of this thread[1], if you're curious. [1] https://mail.python.org/pipermail/python-dev/2017-December/151263.html https://mail.python.org/pipermail/python-dev/2017-December/1...