[Python-Dev] Guarantee ordered dict literals in v3.7?

[Steven D'Aprano]

On Mon, Nov 06, 2017 at 06:35:48PM +0200, Paul Sokolovsky wrote:

> For MicroPython, it would lead to quite an overhead to make
> dictionary items be in insertion order. As I mentioned, MicroPython
> optimizes for very low bookkeeping memory overhead, so lookups are
> effectively O(n), but orderedness will increase constant factor
> significantly, perhaps 5x.

Paul, it would be good if you could respond to Raymond's earlier 
comments where he wrote:

    I've just looked at the MicroPython dictionary implementation and 
    think they won't have a problem implementing O(1) compact dicts with 
    ordering.

    The likely reason for the confusion is that they are already have an 
    option for an "ordered array" dict variant that does a brute-force 
    linear search.  However, their normal hashed lookup is very similar 
    to ours and is easily amenable to being compact and ordered.

    See:  https://github.com/micropython/micropython/blob/77a48e8cd493c0b0e0ca2d2ad58a110a23c6a232/py/map.c#L139

Raymond has also volunteered to assist with this.


> Also, arguably any algorithm which would *maintain* insertion order
> over mutating operations would be more complex and/or require more
> memory that one which doesn't.

I think it would be reasonable to say that builtin dicts only maintain 
insertion order for insertions, lookups, and changing the value. Any 
mutation which deletes keys may arbitrarily re-order the dict.

If the user wants a stronger guarantee, then they should use 
OrderedDict.




-- 
Steve