Python 3.6 dict becomes compact and keywords become ordered

https://mail.python.org/pipermail/python-dev/2016-September/146327.html

by Buetol • 10 years ago

297 157 10 years ago

mail.python.org

jnbiche3• 10 years ago

If you've disabled the StartCom CA due to concerns about lack of transparency[0] and are therefore unable to view pages like this one, you can always click the "web" link above and then view the cached page on Google.

For convenience, that link is:

https://webcache.googleusercontent.com/search?q=cache:9Tj0HS...

0. https://news.ycombinator.com/item?id=12411870

Edit: To be clear to the downvoters, this has nothing to do with Python, other than they're using the StartCom certs. Not a criticism of Python.

jnbiche3• 10 years ago

...

viraptor2• 10 years ago

If you care enough to disable one specific CA, then you likely know how caches work and how to find the alternative. Did you plan to post a comment like this on every single HN article which uses StartCom's cert?

mnx• 10 years ago

The python docs were actually the sole reason I've re-added this cert to my trust store :(

(I didn't want to train myself to click-through the warnings)

smegel• 10 years ago

"Preserving the order of kwargs in a function"

"What are you trying to achieve?"

omginternets• 10 years ago

It's a side-effect.

masklinn5• 10 years ago

Though it's something which has been requested in the past. Also preserving the ordering of class definitions.

thomasahle4• 10 years ago

There is a motivation segment in the PEP: https://www.python.org/dev/peps/pep-0468/#motivation

I don't quite get it though.

dalke2• 10 years ago

Suppose you want to make something like an XML generator helper function:

   def start(tag_, **kwargs):
      write("<" + escape(tag_))
      if kwargs:
          for k, v in kwargs.item():
             write(" " + escape(k) + "=" + quote_escape(v))
      write(">")

(Apply hand-wavying to get the correct code.) This might be called as:

    start("abc", x="1.0", y="2.0")

but generate the output

    <abc y="2.0" x="1.0">

when you want it to be:

    <abc x="1.0" y="2.0">

The output order depends on the Python hash implementation, which (in modern Pythons) is randomly selected during startup. For an API which preserves order, you must currently either pass in the pairs in iterable order, like:

    start("abc", (("x", "1.0"), ("y", "2.0")))

or switch the API to pass in a dictionary-like object instead of kwargs, then switch to an OrderedDict (which must also be initialized with pairs in iterable order).

In 3.6, there's no need for that -- kwargs will preserve the keyword parameter order.

Dowwie• 10 years ago

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

exDM692• 10 years 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.

creshal2• 10 years ago

That's exactly the way OrderedDict works too:

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.

vxxzy• 10 years ago

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

Pirate-of-SV3• 10 years 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.

ganduG2• 10 years 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`.

mikeash2• 10 years 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.

masklinn5• 10 years ago

Its an idea originally from PyPy afaik.

No, the idea is from Raymond Hettinger on the Python-Dev ML back in 2012: https://mail.python.org/pipermail/python-dev/2012-December/1...

PyPy were the first to bother actually implementing it.

RedCrowbar• 10 years ago

`OrderedDict` is now just a thin wrapper around `dict`.

It is not. odictobject.c has not been touched at all yet. Also, OrderedDict defines several methods that ordinary dict does not (and unlikely ever will).

yes_or_gnome2• 10 years ago

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

Pirate-of-SV3• 10 years ago

    dict_keys(['c', 'd', 'e', 'b', 'a'])   # random order

> random

Maybe I'm nit picky but I find the misuse of that word annoying. My experience of CPython is that dicts are unordered but deterministic. Not random.

thomasahle4• 10 years ago

If your hash function is random (seeded), the order will be random over the seed.

Pirate-of-SV3• 10 years ago

Across processes perhaps? But hash(a) == hash(a) and hash(b) == hash(b) so a dictionary that with a and b inserted will yield the same order every time.

    d1 = dict()
    d1['a'] = 1
    d1['b'] = 1
    print(d1.keys())

    d2 = dict()
    d2['a'] = 1
    d2['b'] = 1
    print(d2.keys())

creshal2• 10 years ago

Stable, but not in insertion order or any other order I'd call deterministic.

marcosdumay• 10 years ago

Deterministic means it is completely determined by the parameters, so it doesn't change from one call to another. This seems to be exactly what you are naming "stable" here. If it outputed the keys in a known order, it would be predictable.

Yet, the GP is just complaining about two different and widespread definitions of "random", so, whatever. It would be great to have a contexts dictionary we could use to resolve such things.

kzrdude2• 10 years ago

They should say "arbitrary order"

grumpopotamus• 10 years ago

How about unspecified order?

fucking_tragedy• 10 years ago

How will they reconcile this?

  In [10]: OrderedDict((('a', 1), ('b', 2))) == OrderedDict((('b', 2), ('a', 1)))
  Out[10]: False
  In [11]: dict((('a', 1), ('b', 2))) == dict((('b', 2), ('a', 1)))
  Out[11]: True

wyldfire2• 10 years ago

The equality test for dict objects will be unchanged. Note that it's not as if they said "Oh gee let's just alias dict() to OrderedDict() and call it a day".

raymondh2• 10 years ago

The entire test suite still passes. What do that tell you?

andybak• 10 years ago

Does this mean all dicts are ordered in Python 3.6 onwards?

If so I can see scope for subtle bugs as code written and tested on Python 3.6 will potentially fail on earlier versions due to dict order.

But I guess that's why you test using tox...

collyw2• 10 years ago

I am trying to imagine a bug that would happen with an ordered dictionary which would not happen on an unordered dictionary. An unordered dictionary may return it ordered by chance.

wiz21c• 10 years ago

chance my friend is what hides many bugs

coldtea3• 10 years ago

Parent said for bugs happening in the other direction -- written for 3.6, run on earlier versions, so it would be the inverse happening (ordered assumption not holding).

njharman• 10 years ago

Really? It's in the freaking name. Code is written that depends on dictionary being ordered. Works in CPython 3.6, fails on earlier CPython and other implementations of Python.

brudgers• 10 years ago

I suspect that any procedure relying on dictionary order can experience all the classes of bugs associated with relying on mutated state. For example, if procedure P1 relies on dictionary order and calls another procedure P2 on a dictionary, might get a new dictionary back in a case where P2 is written in a functional rather than imperative style.

Essentially, relying on ordering requires tracking identities rather than values. Which suggests a second bug. What does it mean now mean for two dictionaries to be equal?

sametmax• 10 years ago

If you delete a key, and add one, the order can be lost.

eva1984• 10 years ago

But it is correct in the sense that the insertion order has already changed.

OskarS• 10 years ago

That's an argument against ever adding ANYTHING to a new language!

"Oh, we have this neat feature in mind, but because code that uses it wont work on older versions of the compiler/interpreter, we can't use it!"

Python code that will depend on the ordering will either have to specify Python 3.6 as the minimum version, or just use OrderedDict, which is presumably isn't going anywhere.

Also, it's rare that anything "depends" on the ordering of dictionary keys, but it's frequently "nice to have". For instance, it means that if you output JSON, all the keys are in a sensible order. This matters not at all for other computers reading the JSON (as the JSON spec explicitly says that ordering of keys is irrelevant), but it's lovely for developers debugging the program.

jamiesonbecker• 10 years ago

That's an argument against ever adding ANYTHING to a new language!

Not exactly, because no error will be raised from Python and subtle bugs could be introduced if someone relied on this behavior.

gbin• 10 years ago

The optimization is awesome but IMHO the key ordering "benefit" in the implementation but not the spec is a so-so move: It can cause some future bugs in the code assuming it is there. Some languages like Go added some key ordering randomization to maps to be sure to avoid people counting on any specific key order.

kough• 10 years ago

As long as the language specification is updated to specify ordered keys in dicts then this is good. The big complaint about key ordering I remember hearing is that it was basically a side effect of the CPython implementation (back in the 2.X days), but not part of the spec.

If the spec won't be updated to specify that dict keys must be ordered, then I agree with you.

EDIT: ganduG clarified below that this is just an implementation change. No bueno.

kabdib3• 10 years ago

Many, many people won't read the spec. And their code will break when the implementation changes.

d_theorist4• 10 years ago

This was my thought as well.

I haven't really followed the discussion around the decision, so perhaps I am missing something, but my initial feeling is that either ordering should be required by the spec and implemented, or the ordering should be randomised.

But, that is the outcome of about 1 minute's thought :)

noobiemcfoob4• 10 years ago

If the ordering of the keys is not in the spec, a programmer should not assume the ordering of the keys. If none of the training material says or implies that the keys will always be ordered, why would a programmer?

The new and improved algorithm happens to preserve ordering. Future algorithms might not. The dictionary data structure does not specify order preservation so that, in the future, a better algorithm that doesn't have this same side effect could be used.

d_theorist4• 10 years ago

If none of the training material says or implies that the keys will always be ordered, why would a programmer?

Because people make mistakes.

larrik• 10 years ago

Given how much Python I learned just by opening the interpreter and seeing what happened, I can definitely go along with the idea that this is bad.

GFK_of_xmaspast• 10 years ago

why would a programmer

How many programmers have you worked with? (People will assume all sorts of things that are not true if it makes their job slightly easier, or even harder)

gbog2• 10 years ago

why would a programmer? Because the programmer would just run the code and check what different methods return as result. Then if it looks like the ordered keys, said programmer will rely on this behavior.

For instance, I'm writing some javascript recently. I try a little array in the console, if Array.keys() returns the orders keys, I will assume it is, and would check the docs (where?) only if I had a problem. Something unstable should not look stable. I agree with the Golang way, make it look like what it is by the specs.

tedmiston4• 10 years ago

a programmer should not assume the ordering of the keys

The Python community has many inexperienced programmers, even non-technical people. Particularly, it's so beginner friendly by making it very, very easy to get started with the REPL, etc. A lot of these programmers aren't even going to look at the docs and even if they do, might not understand them.

bjourne3• 10 years ago

It is very easy to inadvertently add dependencies on key order. For example, if you are generating HTML, you might have something like:

    print("<a " + " ".join(k+"=\""+v+"\"" for (k,v) in d.items()) + "/>")

And d would be a dict of attributes for the anchor element. The code will produce different output depending on computer which is not what you want because it can cause subtle problems for other systems expecting a certain output.

Several compiler bugs have been of this kind so it is not only newbie programmers that make these mistakes.

kabdib3• 10 years ago

It's not so-so, it's a terrible idea. At a minimum, the implementation should cough up keys in (say) reverse order, or some cheap to implement different order than insertion order.

Two years down the line, the amount of code that depends on insertion order will make it impossible to do further optimization.

[Many years ago I wrote a platform with an unintended ordering scheme in its dictionary. The documentation stated in bold that order was not deterministic and could change. Users started reporting "bugs" when I changed the order. That sucked.]

notdonspaulding2• 10 years ago

Ordered kwargs is in a PEP[0] that is in "Final" status, meaning it's been accepted and implemented and is making its way into the language proper.

[0] https://www.python.org/dev/peps/pep-0468/

EDIT: On rereading, I see that the parent and GP aren't specifically talking about the kwarg-ordering benefit, but the general dict-ordering benefit. I would be surprised if dict did not become a synonym for OrderedDict in the spec in the near future.

The only potential disadvantage of dict==odict is performance, as anyone relying on the current arbitrarily-ordered dict behavior by definition isn't worried about the underlying implementation moving to a deterministic-by-insertion-order dictionary.

hayd2• 10 years ago

I've seen some python 2 code "made use" of the deterministic ordering of dict. Migrating to python 3 sucked, it took a while to realize this was the reason for some failing tests.

Retra3• 10 years ago

It seems strange that that's what you'd be worried about. Your users found bugs in their own code. That's GOOD, isn't it? Does it matter that they blame you?

Like if I'm using pointers after freeing them and just happen to get usable data back... then you go an change it so that memory is reallocated and my code breaks. Yeah, it is a bug. In my code. It's pretty clear that I should not have been doing that. If I'm to stubborn or stupid to figure that out, then I'm really just a shit programmer.

IgorPartola• 10 years ago

Here is a fun little thing I didn't realize before running into it:

    OrderedDict(a=1, b=2).keys()

Is not guaranteed to return ['a', 'b'].

Of course this makes sense, but is annoying nonetheless.

toyg• 10 years ago

[for k in OrderedDict("a"=1, "b"=2)] should give you what you want, IIRC

the_mitsuhiko• 10 years ago

That's not even valid Python.

deno• 10 years ago

  SyntaxError: keyword can't be an expression

You want to pass a list of tuples:

  from collections import OrderedDict
  assert list(OrderedDict([('a', 1), ('b', 2)]).keys()) == ['a', 'b']

philh• 10 years ago

The problem isn't that .keys() isn't returning them in order. The problem is that the kwargs (a=1, b=2) aren't passed to OrderedDict() in order, so the constructor has no way of knowing which one should be first.

fovc• 10 years ago

I think the standard answer is to use

OrderedDict([('a', 1), ('b', 2)])

I find myself doing that and similar things (objects with `key` and `value` attributes) to deal with JSON non-ordering a lot. I can definitely see value in preserving keyword argument order

yes_or_gnome2• 10 years ago

In 3.6, this will be ordered. Python creates a dict out of the keywords arguments, so before 3.6, this creates the old hash-ordered dict which is covered to an OrderedDict.

But, as the other commenter mentioned, a list of 2-tuples is the safe bet.

_hyn3• 10 years ago

This doesn't feel right.. it's not actually a nice side effect at all.

1. it's not in the spec

2. you shouldn't rely on it

3. python can't figure out if you're relying on it, so no error will be raised

4. subtle bugs are sure to be introduced by people who "know" this "feature" exists and use it.

Regardless of the cool implementation details, this post shouldn't advertise that "keywords become ordered" and "A nice "side effect" of compact dict is that the dictionary now preserves the insertion order".

Ergo... we built this awesome thing that you'd love to use but you can't. Don't use it or you'll be a bad programmer who doesn't read specs!

(Just use addict or OrderedDict.)

tedmiston4• 10 years ago

I tend to agree that this is something that could be confusing to rely on, especially if running tests against multiple version of Python (such as a previous version where this isn't the behavior).

    Explicit is better than implicit.

    There should be one-- and preferably only one --obvious way to do it.

hayd2• 10 years ago

In python 2 the ordering was deterministic. Cue lots of weird bugs when upgrading to python 3. Of course, it should never have been relied on... but it had been.

I'd prefer either a completely random order or a completely deterministic one - but please no take backs (people will rely on it).

camel_Snake• 10 years ago

And so we get a 3rd way to interpolate strings in 3.6.

notdonspaulding2• 10 years ago

At least with respect to ordered kwargs, the spec is changing:

https://www.python.org/dev/peps/pep-0468/

I believe it's an implementation detail that in cpython 3.6, dict and odict are essentially equivalent now, but it's an implementation detail which is there to support an official feature of the language.

If your project can sustain a minimum version of (the as yet unreleased) Python 3.6, I don't see why you shouldn't begin to rely on this feature straightaway.

carapace7• 10 years ago

Ugh. This is all bad.

This just isn't the sort of thing that benefits from fucking with.

This is imposing a slight but not-insignificant open-ended technical debt on the whole of the Python ecosystem, for what seems to me to be very obscure benefits.

munificent• 10 years ago

For what it's worth, the JS ecosystem has tried for years to get users to not rely on key iteration order. It was always unspecified but no matter what, users still expected them to iterate in insertion order.

V8 fought against it for years. Look at this bug horror show:

https://bugs.chromium.org/p/v8/issues/detail?id=164

I think Python is doing the right thing. The only reason to not provide a deterministic iteration order for unsorted maps is to give more room for optimizers. But it seems like there is a clean implementation that is faster while also iterating over keys in insertion order.

Sure, maybe someone will come up with an even better optimization in the future that would break this, but at some point, you have to say, "OK, what we have is good enough, and it gives users a more predictable system."

If you are going to declare insertion order is non-deterministic, you really should make it non-deterministic by doing something like shuffling it. Otherwise, users will just inadvertently rely on whatever deterministic-but-unspecified-order the current implementation happens to provide.

xapata8• 10 years ago

make it non-deterministic

In Python v3.1 - v3.5 the order is deterministic within an execution, but non-deterministic across executions. This was implemented to avoid the possibility that a hacker could slow down dict key lookup/insertion by creating a large number of hash table collisions.

https://mail.python.org/pipermail/python-announce-list/2012-...

IMHO, that doesn't seem to be a big vulnerability.

danpat• 10 years ago

For once, C++ got some usability right and created std::map and std::unordered_map which have explicit key ordering behaviour.

Now, back to waiting for my project to compile.....

duaneb• 10 years ago

I interpret it differently: the ordering is a side effect, and the positive aspect is that it's easier to debug conveniently, not a feature you should rely on version to version.

a3n• 10 years ago

Yeah, this is not a dict that has ordered keys. It's a dict that has that side effect.

I can't think of any reason why a set's members, or a dict's keys (which are just set members with associated values, conceptually) should be unordered. Yes, set membership is traditionally unordered, but we have ordered sets and dicts, so they must be desirable, and they're certainly coherent.

I just hope that if sets and dicts become ordered by spec, that some day someone doesn't feel compelled to implement unordered versions.

dragonwriter• 10 years ago

I just hope that if sets and dicts become ordered by spec, that some day someone doesn't feel compelled to implement unordered versions.

Unspecified-order minimizes constraints on future implementations. If someone finds a useful time or space optimization (for particular workloads, not necessarily in big-O asymptotic terms) that isn't consistent with the specified ordering, that might be a compelling reason to implement a version without the ordering constraint. (But, if its not the best choice for general use, that's true even if the default implementation isn't ordered, since its possible that the optimization will still be unsuitable as the default.)

And, obviously, even if the base case has one ordering, there's all kinds of reasons you might need to implement a version with a different ordering.

pekk3• 10 years ago

"Ordered sets" are coherent in the sense that you can make a data structure like a set and then define an order over its members, and call it an ordered set, but "ordered sets" are not sets.

There are certain purposes sets are natural for. When you introduce ordering, you will naturally be asked to add methods for querying or perhaps modifying that ordering in various ways. Many methods later, it's worth asking why you are calling this data structure a set, and what its actual purpose is supposed to be.

rbanffy2• 10 years ago

I am not very sure this is tat bad. If code breaks because dict is no longer ordered, people should have used an ordered one from the start. It's a happy accident it is faster and ordered and not bad because whoever relies on dicts bein unordered (when sometimes they aren't) deserves whatever breakage they get.

rocqua2• 10 years ago

A language that makes it easier to write shitty code is worse than one that doesn't

takeda2• 10 years ago

This is very similar issue that made migration to Python 3 so painful.

A lot of the code had broken unicode from the start. The difference was that it worked in python 2 most of the time and failed on special cases, while python 3 was stricter and mixing bytes with string always caused it to crash.

Once dict() is ordered and people will use that property (even unknowingly) if the behavior changes again in the future, a lot of their code will be broken.

pekk3• 10 years ago

It isn't right, but popular personalities like the creator of Flask have been demanding it for years so here we are. Welcome to Open Source.

imh• 10 years ago

What's the point of the compact dict? Does having all the keys together outweigh the extra indirection? That would surprise me. Can someone help explain why that would be the case?

PythonicAlpha• 10 years ago

It all depends on the underlying technology. Yes, an indirection costs more. But in the same time, the first level array can be much smaller and it even can be that both arrays together are smaller than the old array before, because it had to had gaps. The new compact array does not need to have gaps.

It of course depends on many factors, like how is the filling factor.

But, preserving memory can potentially also preserve transfers between processor and main memory. In old processors, pure clock cycles and the complexity of the opcodes where the main factor when it came to speed. Today, the complexity of opcodes (for example indirection) are less and less interesting. The amount of cache misses and how much memory must be transferred between processor and memory chips are deciding.

wyldfire2• 10 years ago

This news has spread and seems to cause a great deal of confusion. I wish the headline had been "Python dict faster [because of some subtle details ... don't look behind the curtain]"

brettcannon• 10 years ago

It needs to be realized that this dict implementation landed literally yesterday. There are space benefits and it simplifies the language in three places where we are adding ordered mapping guarantees (kwargs, namespace passed to metaclasses, and cls.__dict__, all of which were planned to be ordered prior to this dict implementation coming into the language).

Before we bake the requirement of dictionaries being ordered into the language spec and require all current and future Python implementations to support it for Python 3.6 onwards -- remember, Python is 26 years old -- we want to live with the dict implementation for a few releases first.

fermigier• 10 years ago

Here's what Guido wrote about some of the issues that have been raised here:

"""

I've been asked about this. Here's my opinion on the letter of the law in 3.6:

- keyword args are ordered

- the namespace passed to a metaclass is ordered by definition order

- ditto for the class __dict__

A compliant implementation may ensure the above three requirements either by making all dicts ordered, or by providing a custom dict subclass (e.g. OrderedDict) in those three cases.

I'd like to handwave on the ordering of all other dicts. Yes, in CPython 3.6 and in PyPy they are all ordered, but it's an implementation detail. I don't want to force all other implementations to follow suit. I also don't want too many people start depending on this, since their code will break in 3.5. (Code that needs to depend on the ordering of keyword args or class attributes should be relatively uncommon; but people will start to depend on the ordering of all dicts all too easily. I want to remind them that they are taking a risk, and their code won't be backwards compatible.)

"""

https://mail.python.org/pipermail/python-dev/2016-September/...

crescentfresh• 10 years ago

What a sound and reasonable opinion, in my opinion.

raymondh2• 10 years ago

Put another way, "We're trying out a smaller, faster dict implementation that has the side-effect of being ordered. We would like to be able to change our mind in the future, except for the three cases listed above where we really want to guarantee ordering."

The original proposal was only about improving the implementation https://mail.python.org/pipermail/python-dev/2012-December/1...

Also, Guido wants people to write Python3 code that doesn't rely on dict ordering so that their code run on both Python3.5 and Python3.6.

carapace7• 10 years ago

I'm one of those weirdos who wants to continue to use Python 2 for the foreseeable future, so to me this is just introducing a way to break backwards compatibility all the way back to 2 for the benefit of a similar but ever-more-incompatible language that I'll never use.

I'm not trying to be negative, I just want to let you know that people like me are out there.

zzzeek3• 10 years ago

this is fine, but with PYTHONHASHSEED no longer impacting dictionary ordering, we need a new way to test our applications to ensure they aren't relying on dictionary ordering, without having to replace all dict / {} instances with "myapplication.utils.patchable_dict". What solution has been arrived at for this use case? (there IS a solution, right?)

lqdc13• 10 years ago

So for larger dicts the memory size of the dict would be 5/3 of what it is now? That seems like a big regression unless I'm missing something.

Terr_• 10 years ago

Python should have a "grumpy mode" which causes dict-keyword order to be randomized, and other deliberate attempts to break code where people are doing the wrong thing :P

rurban• 10 years ago

Any benchmarks yet? I'm curious about the cost of the indirection and the 2nd array vs the smaller sparse array (easier cachable), and thinking of doing the same for cperl hashes.

splits also need to realloc now twice, which might have some costs. still the run-time advantage should beat all new costs.

kragen• 10 years ago

Dude, Python is trying to become PHP. Except with a complicated implementation.

Python 3.6 dict becomes compact and keywords become ordered

Related Stories