Add __reversed__ methods for dict
Hi, since dict keys are sorted by their insertion order since Python 3.6 and that it’s part of Python specs since 3.7 a proposal has been made in bpo-33462 to add the __reversed__ method to dict and dict views. Concerns have been raised in the comments that this feature may add too much bloat in the core interpreter and be harmful for other Python implementations. Given the different issues this change creates, I see three possibilities: 1. Accept the proposal has it is for dict and dict views, this would add about 300 lines and three new types in dictobject.c 2. Accept the proposal only for dict, this would add about 80 lines and one new type in dictobject.c while still being useful for some use cases 3. Drop the proposal as the whole, while having some use, reversed(dict(a=1, b=2)) may not be very common and could be done using OrderedDict instead. What’s your stance on the issue ? Best regards, Rémi Lapeyre
Please go find some real world code that would benefit from this. Don't
make up examples, just show some code in a repository (public if possible,
but private is okay, as long as you can quote small amounts of code from
it) where te existence of reverse iteration over a dict would have been
helpful.
On Thu, May 24, 2018 at 5:55 AM, Rémi Lapeyre
Hi,
since dict keys are sorted by their insertion order since Python 3.6 and that it’s part of Python specs since 3.7 a proposal has been made in bpo-33462 to add the __reversed__ method to dict and dict views.
Concerns have been raised in the comments that this feature may add too much bloat in the core interpreter and be harmful for other Python implementations.
Given the different issues this change creates, I see three possibilities:
1. Accept the proposal has it is for dict and dict views, this would add about 300 lines and three new types in dictobject.c
2. Accept the proposal only for dict, this would add about 80 lines and one new type in dictobject.c while still being useful for some use cases
3. Drop the proposal as the whole, while having some use, reversed(dict(a=1, b=2)) may not be very common and could be done using OrderedDict instead.
What’s your stance on the issue ?
Best regards, Rémi Lapeyre _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/ guido%40python.org
-- --Guido van Rossum (python.org/~guido)
(Also this probably belongs in python-ideas, unless there's already a
bugs.python.org issue for it -- but you didn't mention that so I assume
it's just an idea? How did you reach the line count estimates?)
On Fri, May 25, 2018 at 8:46 AM, Guido van Rossum
Please go find some real world code that would benefit from this. Don't make up examples, just show some code in a repository (public if possible, but private is okay, as long as you can quote small amounts of code from it) where te existence of reverse iteration over a dict would have been helpful.
On Thu, May 24, 2018 at 5:55 AM, Rémi Lapeyre
wrote: Hi,
since dict keys are sorted by their insertion order since Python 3.6 and that it’s part of Python specs since 3.7 a proposal has been made in bpo-33462 to add the __reversed__ method to dict and dict views.
Concerns have been raised in the comments that this feature may add too much bloat in the core interpreter and be harmful for other Python implementations.
Given the different issues this change creates, I see three possibilities:
1. Accept the proposal has it is for dict and dict views, this would add about 300 lines and three new types in dictobject.c
2. Accept the proposal only for dict, this would add about 80 lines and one new type in dictobject.c while still being useful for some use cases
3. Drop the proposal as the whole, while having some use, reversed(dict(a=1, b=2)) may not be very common and could be done using OrderedDict instead.
What’s your stance on the issue ?
Best regards, Rémi Lapeyre _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/guido% 40python.org
-- --Guido van Rossum (python.org/~guido)
-- --Guido van Rossum (python.org/~guido)
INADA Naoki asked Rémi Lapeyre in https://bugs.python.org/issue33462
to start a discussion on python-dev.
Victor
2018-05-25 17:48 GMT+02:00 Guido van Rossum
(Also this probably belongs in python-ideas, unless there's already a bugs.python.org issue for it -- but you didn't mention that so I assume it's just an idea? How did you reach the line count estimates?)
On Fri, May 25, 2018 at 8:46 AM, Guido van Rossum
wrote: Please go find some real world code that would benefit from this. Don't make up examples, just show some code in a repository (public if possible, but private is okay, as long as you can quote small amounts of code from it) where te existence of reverse iteration over a dict would have been helpful.
On Thu, May 24, 2018 at 5:55 AM, Rémi Lapeyre
wrote: Hi,
since dict keys are sorted by their insertion order since Python 3.6 and that it’s part of Python specs since 3.7 a proposal has been made in bpo-33462 to add the __reversed__ method to dict and dict views.
Concerns have been raised in the comments that this feature may add too much bloat in the core interpreter and be harmful for other Python implementations.
Given the different issues this change creates, I see three possibilities:
1. Accept the proposal has it is for dict and dict views, this would add about 300 lines and three new types in dictobject.c
2. Accept the proposal only for dict, this would add about 80 lines and one new type in dictobject.c while still being useful for some use cases
3. Drop the proposal as the whole, while having some use, reversed(dict(a=1, b=2)) may not be very common and could be done using OrderedDict instead.
What’s your stance on the issue ?
Best regards, Rémi Lapeyre _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/guido%40python.org
-- --Guido van Rossum (python.org/~guido)
-- --Guido van Rossum (python.org/~guido)
_______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/vstinner%40redhat.com
It looks like an optimization, since you can already do something like
reversed(list(d)). Do you have benchmark numbers to see the benefit of
your change?
Even if reversed(list(d)) is slow, I'm not sure that it's worth it to
optimize it, since it's a rare usecase.
Victor
2018-05-24 14:55 GMT+02:00 Rémi Lapeyre
Hi,
since dict keys are sorted by their insertion order since Python 3.6 and that it’s part of Python specs since 3.7 a proposal has been made in bpo-33462 to add the __reversed__ method to dict and dict views.
Concerns have been raised in the comments that this feature may add too much bloat in the core interpreter and be harmful for other Python implementations.
Given the different issues this change creates, I see three possibilities:
1. Accept the proposal has it is for dict and dict views, this would add about 300 lines and three new types in dictobject.c
2. Accept the proposal only for dict, this would add about 80 lines and one new type in dictobject.c while still being useful for some use cases
3. Drop the proposal as the whole, while having some use, reversed(dict(a=1, b=2)) may not be very common and could be done using OrderedDict instead.
What’s your stance on the issue ?
Best regards, Rémi Lapeyre _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/vstinner%40redhat.com
It's worth nothing that OrderedDict already supports reversed().
The argument could go both ways:
1. dict is similar to OrderedDict nowadays, so it should support
reversed() too;
2. you can use OrderedDict to signal explicitly that you care about
ordering; no need to add anything to dict.
Regards
Antoine.
On Thu, 24 May 2018 14:55:32 +0200
Rémi Lapeyre
Hi,
since dict keys are sorted by their insertion order since Python 3.6 and that it’s part of Python specs since 3.7 a proposal has been made in bpo-33462 to add the __reversed__ method to dict and dict views.
Concerns have been raised in the comments that this feature may add too much bloat in the core interpreter and be harmful for other Python implementations.
Given the different issues this change creates, I see three possibilities:
1. Accept the proposal has it is for dict and dict views, this would add about 300 lines and three new types in dictobject.c
2. Accept the proposal only for dict, this would add about 80 lines and one new type in dictobject.c while still being useful for some use cases
3. Drop the proposal as the whole, while having some use, reversed(dict(a=1, b=2)) may not be very common and could be done using OrderedDict instead.
What’s your stance on the issue ?
Best regards, Rémi Lapeyre _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/python-python-dev%40m.gma...
On May 25, 2018, at 9:32 AM, Antoine Pitrou
wrote: It's worth nothing that OrderedDict already supports reversed(). The argument could go both ways:
1. dict is similar to OrderedDict nowadays, so it should support reversed() too;
2. you can use OrderedDict to signal explicitly that you care about ordering; no need to add anything to dict.
Those are both valid sentiments :-) My thought is that guaranteed insertion order for regular dicts is brand new, so it will take a while for the notion settle in and become part of everyday thinking about dicts. Once that happens, it is probably inevitable that use cases will emerge and that __reversed__ will get added at some point. The implementation seems straightforward and it isn't much of a conceptual leap to expect that a finite ordered collection would be reversible. Given that dicts now track insertion order, it seems reasonable to want to know the most recent insertions (i.e. looping over the most recently added tasks in a task dict). Other possible use cases will likely correspond to how we use the Unix tail command. If those use cases arise, it would be nice for __reversed__ to already be supported so that people won't be tempted to implement an ugly workaround using popitem() calls followed by reinsertions. Raymond .
OK, +1 On Fri, May 25, 2018 at 10:26 AM, Raymond Hettinger < raymond.hettinger@gmail.com> wrote:
On May 25, 2018, at 9:32 AM, Antoine Pitrou
wrote: It's worth nothing that OrderedDict already supports reversed(). The argument could go both ways:
1. dict is similar to OrderedDict nowadays, so it should support reversed() too;
2. you can use OrderedDict to signal explicitly that you care about ordering; no need to add anything to dict.
Those are both valid sentiments :-)
My thought is that guaranteed insertion order for regular dicts is brand new, so it will take a while for the notion settle in and become part of everyday thinking about dicts. Once that happens, it is probably inevitable that use cases will emerge and that __reversed__ will get added at some point. The implementation seems straightforward and it isn't much of a conceptual leap to expect that a finite ordered collection would be reversible.
Given that dicts now track insertion order, it seems reasonable to want to know the most recent insertions (i.e. looping over the most recently added tasks in a task dict). Other possible use cases will likely correspond to how we use the Unix tail command.
If those use cases arise, it would be nice for __reversed__ to already be supported so that people won't be tempted to implement an ugly workaround using popitem() calls followed by reinsertions.
Raymond
.
_______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/ guido%40python.org
-- --Guido van Rossum (python.org/~guido)
I am also in agreement.
On Fri, May 25, 2018, 13:49 Guido van Rossum
OK, +1
On Fri, May 25, 2018 at 10:26 AM, Raymond Hettinger < raymond.hettinger@gmail.com> wrote:
On May 25, 2018, at 9:32 AM, Antoine Pitrou
wrote: It's worth nothing that OrderedDict already supports reversed(). The argument could go both ways:
1. dict is similar to OrderedDict nowadays, so it should support reversed() too;
2. you can use OrderedDict to signal explicitly that you care about ordering; no need to add anything to dict.
Those are both valid sentiments :-)
My thought is that guaranteed insertion order for regular dicts is brand new, so it will take a while for the notion settle in and become part of everyday thinking about dicts. Once that happens, it is probably inevitable that use cases will emerge and that __reversed__ will get added at some point. The implementation seems straightforward and it isn't much of a conceptual leap to expect that a finite ordered collection would be reversible.
Given that dicts now track insertion order, it seems reasonable to want to know the most recent insertions (i.e. looping over the most recently added tasks in a task dict). Other possible use cases will likely correspond to how we use the Unix tail command.
If those use cases arise, it would be nice for __reversed__ to already be supported so that people won't be tempted to implement an ugly workaround using popitem() calls followed by reinsertions.
Raymond
.
_______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/guido%40python.org
-- --Guido van Rossum (python.org/~guido) _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/ramseydsilva%40gmail.com
Concerns have been raised in the comments that this feature may add too much bloat in the core interpreter and be harmful for other Python implementations.
To clarify, my point is it prohibit hashmap + single linked list implementation in other Python implementation. Because doubly linked list is very memory inefficient, every implementation would be forced to implement dict like PyPy (and CPython) for efficiency. But I don't know much about current MicroPython and other Python implementation's plan to catch Python 3.6 up.
Given the different issues this change creates, I see three possibilities:
1. Accept the proposal has it is for dict and dict views, this would add about 300 lines and three new types in dictobject.c
2. Accept the proposal only for dict, this would add about 80 lines and one new type in dictobject.c while still being useful for some use cases
3. Drop the proposal as the whole, while having some use, reversed(dict(a=1, b=2)) may not be very common and could be done using OrderedDict instead.
What’s your stance on the issue ?
I want to wait one version (3.8) for other implementations.
"Keep insertion order" is requirement from 3.7 which is not released yet.
I feel it's too early to add more stronger requirements to core type.
Regards,
---
INADA Naoki
Hm, I find Inada's argument compelling that this might not be easy for all
implementations. So let's wait.
On Sat, May 26, 2018 at 7:20 AM, INADA Naoki
Concerns have been raised in the comments that this feature may add too much bloat in the core interpreter and be harmful for other Python implementations.
To clarify, my point is it prohibit hashmap + single linked list implementation in other Python implementation. Because doubly linked list is very memory inefficient, every implementation would be forced to implement dict like PyPy (and CPython) for efficiency.
But I don't know much about current MicroPython and other Python implementation's plan to catch Python 3.6 up.
Given the different issues this change creates, I see three possibilities:
1. Accept the proposal has it is for dict and dict views, this would add about 300 lines and three new types in dictobject.c
2. Accept the proposal only for dict, this would add about 80 lines and one new type in dictobject.c while still being useful for some use cases
3. Drop the proposal as the whole, while having some use, reversed(dict(a=1, b=2)) may not be very common and could be done using OrderedDict instead.
What’s your stance on the issue ?
I want to wait one version (3.8) for other implementations. "Keep insertion order" is requirement from 3.7 which is not released yet. I feel it's too early to add more stronger requirements to core type.
Regards,
--- INADA Naoki
_______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/ guido%40python.org
-- --Guido van Rossum (python.org/~guido)
On May 26, 2018, at 7:20 AM, INADA Naoki
wrote: Because doubly linked list is very memory inefficient, every implementation would be forced to implement dict like PyPy (and CPython) for efficiency. But I don't know much about current MicroPython and other Python implementation's plan to catch Python 3.6 up.
FWIW, Python 3.7 is the first Python that where the language guarantees that regular dicts are order preserving. And the feature being discussed in this thread is for Python 3.8. What potential implementation obstacles do you foresee? Can you imagine any possible way that an implementation would have an order preserving dict but would be unable to trivially implement __reversed__? How could an implementation have a __setitem__ that appends at the end, and a popitem() that pops from that same end, but still not be able to easily iterate in reverse? It really doesn't matter whether an implementer uses a dense array of keys or a doubly-linked-list; either way, looping backward is as easy as going forward. Raymond P.S. It isn't going to be hard to update MicroPython to have a compact and ordered dict (based on my review of their existing dict implementation). This is something they are really going to want because of the improved memory efficiency. Also, they're also already going to need it just to comply with guaranteed keyword argument ordering and guaranteed ordering of class dictionaries.
On Sun, May 27, 2018 at 12:43 PM Raymond Hettinger < raymond.hettinger@gmail.com> wrote:
On May 26, 2018, at 7:20 AM, INADA Naoki
wrote: Because doubly linked list is very memory inefficient, every implementation would be forced to implement dict like PyPy (and CPython) for efficiency. But I don't know much about current MicroPython and other Python implementation's plan to catch Python 3.6 up.
FWIW, Python 3.7 is the first Python that where the language guarantees that regular dicts are order preserving. And the feature being discussed in this thread is for Python 3.8.
What potential implementation obstacles do you foresee? Can you imagine any possible way that an implementation would have an order preserving dict but would be unable to trivially implement __reversed__? How could an implementation have a __setitem__ that appends at the end, and a popitem()
Oh, my mistake. that pops from that same end, but still not be able to easily iterate in reverse? It really doesn't matter whether an implementer uses a dense array of keys or a doubly-linked-list; either way, looping backward is as easy as going forward. I thought `popitem()` removes the last item is still implementation detail. So I thought about hashmap + single linked list. When removing item, dummy entry will be kept in the list. The dummy entry in the list will be removed when iterating over the list, or rebuilding hashmap. FWIW, quick survey of other languages hashmap implementations and APIs are: # PHP PHP 5 used hashmap + doubly linked list. PHP 7 uses Python-like implementation. While PHP doesn't have reverse iterator, there are `end()` and `prev()` which can be used to iterate backwards. # Ruby From Ruby 1.9, Hash is ordered. At the time, implementation is hashmap + doubly linked list. From Ruby 2.4, Python-like implementation. There are `Enumereble.reverse_each` API. But the API is documented as "Builds a temporary array and traverses that array in reverse order." So Ruby seems allow other implementation which doesn't have zerocopy reverse iterator. (I don't know CRuby provides it or not.) http://ruby-doc.org/core-2.2.2/Enumerable.html#method-i-reverse_each # Java The LinkedHashMap document says " it maintains a doubly-linked list ". https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html On the other hand, there are no reverse iterator API. So if we require `__reverse__` for dict, Jython can't use LinkedHashMap as backend of dict. # C# (.Net) There are legacy (non generic) OrderedDict. It's `remove()` seems O(n) implementation. https://referencesource.microsoft.com/#System/compmod/system/collections/spe... # Rust, Swift, and Go Builtin mapping is arbitrary ordered, and there is no ordered mapping in the standard library. --- It seems: * There are no single linked list based OrderedDict implementation, but * Only PHP exposes "zerocopy reverse iterate" API. I may be wrong because I'm not expert of these languages. Please point out if I am wrong.
Raymond
P.S. It isn't going to be hard to update MicroPython to have a compact and ordered dict (based on my review of their existing dict implementation). This is something they are really going to want because of the improved memory efficiency. Also, they're also already going to need it just to comply with guaranteed keyword argument ordering and guaranteed ordering of class dictionaries.
Thanks.
Sadly speaking, Jython and IronPython development seems very slow and "wait
until 3.9" may be
not long enough for they catch Python 3.7 up.
When focusing to CPython, PyPy and MicroPython, no problem for adding
__reverse__ in 3.8 seems OK.
Regards,
--
INADA Naoki
Hi Inada,
On 27 May 2018 at 09:12, INADA Naoki
When focusing to CPython, PyPy and MicroPython, no problem for adding __reverse__ in 3.8 seems OK.
Fwiw, the functionality that is present in OrderedDict but still absent from 'dict' is: ``__reverse__``, discussed above, and ``move_to_end(last=False)``. In PyPy3, OrderedDict is implemented not like in the CPython stdlib but as just a thin dict subclass without any extra data, using two custom built-ins from the ``__pypy__`` module for the two methods above (plus some pure Python code for other methods like __eq__(), where it is possible to do so with the correct complexity). A bientôt, Armin.
participants (8)
-
Antoine Pitrou
-
Armin Rigo
-
Guido van Rossum
-
INADA Naoki
-
Ramsey D'silva
-
Raymond Hettinger
-
Rémi Lapeyre
-
Victor Stinner