4 ms·

With this given, why wouldn't collections.OrderedDict be deprecated as of 3.6?

by Dowwie 10y ago

exDM69 10y ago
edit: it seems like this is exactly what OrderedDict does, I presumed it's ordered by key, like std::map (red-black tree) vs. std::unordered_map (hash table) is in C++. No, this new dict implementation preserves insertion order, it's not ordered by value of the key. The motivation is to preserve the order of kwargs.
- creshal 10y ago
  That's exactly the way OrderedDict works too: https://docs.python.org/2/library/collections.html#collections.OrderedDict https://docs.python.org/2/library/collections.html#collectio... > An OrderedDict is a dict that remembers the order that keys were first inserted. If a new entry overwrites an existing entry, the original insertion position is left unchanged. Deleting an entry and reinserting it will move it to the end.
  - exDM69 10y ago
    Oh thanks, I was mistaken. Added an edit to GP post.
- deleted 10y ago
  [deleted]
vxxzy 10y ago
I am sure there is a bit of code out there still calling the method...
- Pirate-of-SV 10y ago
  Deprecating it won't affect that code since it's more of a flag to indicate that future use should be limited to ensure forward compatibility.
ganduG 10y ago
Because this is an implementation detail. The language spec doesn't enforce this. The real reason they did this was because of the performance gains from the approach - the ordering is just a nice side effect. Its an idea originally from PyPy afaik. `OrderedDict` is now just a thin wrapper around `dict`. i.e. if you want your code to be portable among different Python implementations then you should still use `OrderedDict`.
- mikeash 10y ago
  Do you have a link to info about why it's faster? My initial reaction was that the extra indirection would slow it down, but of course that's based on nothing but general knowledge and two seconds' thought.
  - masklinn 10y ago
    > My initial reaction was that the extra indirection would slow it down, but of course that's based on nothing but general knowledge and two seconds' thought. There are already indirections in the current implementation. The new dict has much better memory locality: the "actual data" (24 bytes on 64b platforms) is stored in a dense array instead of the former sparse array, and the sparse array only stores indices so it can be made much more compact (especially as it can switch the index size depending on the size of the compact array, for small dicts it'll store byte indices). So not only is the new dict smaller, the way the data is laid out is better fetchable. The original point[0] was actually iteration speed: since the data is stored in a dense array, that can be iterated directly and efficiencly instead of having to iterate a sparse array and skip the random empty entries (leading to awful branch predictability, whether a given entry of the sparse array is empty is essentially random if the hash is any good). [0] https://mail.python.org/pipermail/python-dev/2012-December/123028.html https://mail.python.org/pipermail/python-dev/2012-December/1...
    - mikeash 10y ago
      Great, thank you. That's a cool technique and I'll have to remember it.
yes_or_gnome 10y ago
It is. Like most programming language deprecations, it's implementation was removed and the name remains for backwards compatibility.

With this given, why wouldn't collections.OrderedDict be deprecated as of 3.6?

by Dowwie 10y ago

With this given, why wouldn't collections.OrderedDict be deprecated as of 3.6?

edit: it seems like this is exactly what OrderedDict does, I presumed it's ordered by key, like std::map (red-black tree) vs. std::unordered_map (hash table) is in C++. No, this new dict implementation preserves insertion order, it's not ordered by value of the key. The motivation is to preserve the order of kwargs.

creshal 10y ago
That's exactly the way OrderedDict works too: https://docs.python.org/2/library/collections.html#collections.OrderedDict https://docs.python.org/2/library/collections.html#collectio... > An OrderedDict is a dict that remembers the order that keys were first inserted. If a new entry overwrites an existing entry, the original insertion position is left unchanged. Deleting an entry and reinserting it will move it to the end.
- exDM69 10y ago
  Oh thanks, I was mistaken. Added an edit to GP post.
deleted 10y ago
[deleted]

vxxzy 10y ago

I am sure there is a bit of code out there still calling the method...

Pirate-of-SV 10y ago
Deprecating it won't affect that code since it's more of a flag to indicate that future use should be limited to ensure forward compatibility.

ganduG 10y ago

Because this is an implementation detail. The language spec doesn't enforce this. The real reason they did this was because of the performance gains from the approach - the ordering is just a nice side effect. Its an idea originally from PyPy afaik. `OrderedDict` is now just a thin wrapper around `dict`. i.e. if you want your code to be portable among different Python implementations then you should still use `OrderedDict`.

mikeash 10y ago
Do you have a link to info about why it's faster? My initial reaction was that the extra indirection would slow it down, but of course that's based on nothing but general knowledge and two seconds' thought.
- masklinn 10y ago
  > My initial reaction was that the extra indirection would slow it down, but of course that's based on nothing but general knowledge and two seconds' thought. There are already indirections in the current implementation. The new dict has much better memory locality: the "actual data" (24 bytes on 64b platforms) is stored in a dense array instead of the former sparse array, and the sparse array only stores indices so it can be made much more compact (especially as it can switch the index size depending on the size of the compact array, for small dicts it'll store byte indices). So not only is the new dict smaller, the way the data is laid out is better fetchable. The original point[0] was actually iteration speed: since the data is stored in a dense array, that can be iterated directly and efficiencly instead of having to iterate a sparse array and skip the random empty entries (leading to awful branch predictability, whether a given entry of the sparse array is empty is essentially random if the hash is any good). [0] https://mail.python.org/pipermail/python-dev/2012-December/123028.html https://mail.python.org/pipermail/python-dev/2012-December/1...
  - mikeash 10y ago
    Great, thank you. That's a cool technique and I'll have to remember it.

yes_or_gnome 10y ago

It is. Like most programming language deprecations, it's implementation was removed and the name remains for backwards compatibility.