36 ms·
Python 3.6 dict becomes compact and keywords become ordered
- jnbiche 10y agoIf 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:9Tj0HSwUl2YJ:https://mail.python.org/pipermail/python-dev/2016-September/146327.html+&cd=1&hl=en&ct=clnk&gl=us https://webcache.googleusercontent.com/search?q=cache:9Tj0HS... 0. https://news.ycombinator.com/item?id=12411870 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.
- jnbiche 10y ago...
- viraptor 10y agoIf 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?
- jnbiche 10y agoOK, so I was also raising awareness of the issue, guilty. And no, this was the only time I've mentioned this on HN, and I'll never mention it again here, you have my word. Had no fucking idea it would draw so much ire (most downvoted comment ever here in half a decade). Was trying to be helpful. Sorry for pissing you all off so much.
- viraptor 10y agoDon't take it personally. I downvoted it, because I think it's irrelevant. I doubt anyone got angry or had any emotions at all about that post.
- mnx 10y agoThe 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 10y ago> "Preserving the order of kwargs in a function" "What are you trying to achieve?"
- omginternets 10y agoIt's a side-effect.
- masklinn 10y agoThough it's something which has been requested in the past. Also preserving the ordering of class definitions.
- thomasahle 10y agoThere is a motivation segment in the PEP: https://www.python.org/dev/peps/pep-0468/#motivation https://www.python.org/dev/peps/pep-0468/#motivation I don't quite get it though.
- dalke 10y agoSuppose 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.
- kzrdude 10y ago
- Dowwie 10y agoWith this given, why wouldn't collections.OrderedDict be deprecated as of 3.6?
- exDM69 10y agoedit: 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 agoThat'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 agoOh thanks, I was mistaken. Added an edit to GP post.
- deleted 10y ago[deleted]
- vxxzy 10y agoI am sure there is a bit of code out there still calling the method...
- Pirate-of-SV 10y agoDeprecating 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.
- Pirate-of-SV 10y agodict_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.
- thomasahle 10y agoIf your hash function is random (seeded), the order will be random over the seed.
- Pirate-of-SV 10y agoAcross 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())
- thomasahle 10y agoYes across processes. You don't want to change (reseed) the hash function after the dictionary is created. (At least then you need to rehash everything.) Seeded hashing was introduced to python 3.2.3: https://docs.python.org/3.3/using/cmdline.html#cmdoption-R https://docs.python.org/3.3/using/cmdline.html#cmdoption-R $ python3 --version Python 3.5.2 $ python3 -c "print(hash('a'))" 6106879154137036349 $ python3 -c "print(hash('a'))" 9160572615033669802 $ python3 -c "print(set('abcdef'))" {'d', 'f', 'e', 'b', 'c', 'a'} $ python3 -c "print(set('abcdef'))" {'e', 'f', 'd', 'a', 'b', 'c'} Note that there is no guarantee that this ordering is uniformly random. (Though it probably is.)
- Veedrac 10y agoThe order of the keys in a dictionary was merely guaranteed to be consistent for a given instance: that is d1 is d2 ⇒ list(d1) == list(d2) But the order is not guaranteed to be consistent between two equal dictionaries, in that d1 == d2 ⇏ list(d1) == list(d2) This is because the history of the dictionary can affect its order, not just its contents. For example, x = {-1: (), -2: ()} y = {-2: (), -1: ()} list(x) != list(y) This remains true, but now the particular order produced from a given list of insert and delete operations is well-defined, rather than arbitrary. It's worth noting that previously the order of two dictionaries with the same history was also the same (but may vary between program runs), but that was not guaranteed. It's not actually clear if this is still regarded as an implementation detail, but I expect it will be effectively impossible to stop this becoming a key assumption of many libraries, so would expect any attempt to require OrderedDict (except for pre-3.6 compatibility) will fail.
- fucking_tragedy 10y agoHow 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
- andybak 10y agoDoes 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...
- collyw 10y agoI 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 10y agochance my friend is what hides many bugs
- deleted 10y ago[deleted]
- coldtea 10y agoParent 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 10y agoReally? 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.
- collyw 10y agoSorry I wrote that back to front. Fixed now.
- brudgers 10y agoI 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?
- gbin 10y agoThe 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 10y agoAs 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.
- d_theorist 10y agoThis 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 :)
- noobiemcfoob 10y agoIf 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.
- deleted 10y ago[deleted]
- IgorPartola 10y agoHere 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 10y ago[for k in OrderedDict("a"=1, "b"=2)] should give you what you want, IIRC
- the_mitsuhiko 10y agoThat's not even valid Python.
- deleted 10y ago[deleted]
- coldtea 10y agoWell, [k for k in OrderedDict(a=1, b=2)] not that different in valid Python
- mark-r 10y agoBut as pointed out elsewhere, kwargs aren't guaranteed to be in order, so by the time the OrderedDict is built it's already wrong. It seems the change we're discussing was primarily motivated by a desire to fix that specific problem.
- ak217 10y agoThe point OP is making is that none of these statements will guarantee the order of insertion, since OrderedDict must take the variadic kwargs input as a dict, which is inherently unordered. You have to use a list of tuples.
- coldtea 10y ago
- _hyn3 10y agoThis 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.)
- tedmiston 10y agoI 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.
- hayd 10y agoIn 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).
- Retra 10y agoI'm not sure anybody should be relying on code that relies upon the order of an unordered dict.
- masklinn 10y agoThese reliances usually aren't explicit, they just happen to work that way and it can be very hard to tease out the dependency unless you have a way to easily screw with iteration order. Pretty much any unspecified but (because of implementation) reliable ordering will eventually end up with code relying on it, usually implicitly, e.g. some Go code broke in 1.5 (and the release notes noted it explicitly) when scheduling order changed[0] despite it always having been undefined. In fact, specifically to catch this kind of hidden dependencies the Go developers added limited scheduling randomisation to the race detection mode. [0] from definition-ordering to last-definition-bias e.g. if you launched 3 goroutines 1, 2 and 3, in 1.4 the scheduler would just run them in that order, in 1.5 it would run 3 first followed by 1 and 2.
- imh 10y agoWhat'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 10y agoIt 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.
- wyldfire 10y agoThis 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 10y agoIt 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 10y agoHere'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/146348.html https://mail.python.org/pipermail/python-dev/2016-September/...
- crescentfresh 10y agoWhat a sound and reasonable opinion, in my opinion.
- raymondh 10y agoPut 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/123028.html 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.
- carapace 10y agoI'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.
- deleted 10y ago[deleted]
- lqdc13 10y agoSo 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_ 10y agoPython 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 10y agoAny 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.
- singlocnu 10y agoGet webcamshow for free. Sign up there http://u.to/cOg3Dw http://u.to/cOg3Dw
- kragen 10y agoDude, Python is trying to become PHP. Except with a complicated implementation.