[Larry] > Didn't some paths also get sliiiiightly slower as a result of maintaining > insertion order when mixing insertions and deletions?
I paid no attention at the time. But in going from "compact dict" to "ordered dict", deletion all by itself got marginally cheaper. The downside was the need to rearrange the whole dict when too many "holes" built up. "Compact (but unordered) dict" doesn't need that. > My recollection is that that was part of the debate--not only "are we going to > regret inflicting these semantics on posterity, and on other > implementations?", > but also "are these semantics worth the admittedly-small performance hit, in > Python's most important and most-used data structure?". There's a layer of indirection in compact dicts - lookups are distributed across two arrays. In non-compact unordered dicts, everything is in a single array. Cache effects may or may not make a measurable difference then, depending on all sorts of things. > Also, I don't recall anything about us resigning ourselves to explicitly > maintain ordering on dicts because people were relying on it, "battling > windmills", etc. Dict ordering had never been guaranteed, a lack > of guarantee Python had always taken particularly seriously. Rather, we > decided it was a desirable feature, and one worth pursuing even at the > cost of a small loss of performance. I'm not convinced there was a loss of performance. The delay between the implementation supplying ordered dicts, and the language guaranteeing it, was, I suspect, more a matter of getting extensive real-world experience about whether the possible new need to massively rearrange dict internals to remove "holes" would bite someone too savagely to live with. But, again, I wasn't paying attention at the time. > One prominent Python core developer** wanted this feature for years, and I > recall > them saying something like: > > Guido says, "When a programmer iterates over a dictionary and they see the > keys > shift around when the dictionary changes, they learn something!" To that I > say--"Yes! > They learn that Python is unreliable and random!" I never wanted ordered dicts, but never objected to them either. All in all, given that _I_ haven't seen a performance degradation, I like that they're more predictable, and love the memory savings. But as Raymond said (& I elaborated on), there's reason to believe that the implementation of ordered dicts is less suited to sets, where high rates of mixing adds and deletes is more common (thus triggering high rates of massive internal dict rearranging). Which is why I said much earlier that I'd be +1 on ordered sets only when there's an implementation that's as fast as what we have now. Backing up: > Python is the language where speed, correctness, and readability trump > performance every time. Speed trumping performance didn't make any sense ;-) So assuming you didn't intend to type "speed", I think you must have, say, Scheme or Haskell in mind there. "Practicality beats purity" is never seen on forums for those languages. Implementation speed & pain have played huge rules in many Python decisions. As someone who has wrestled with removing the GIL, you should know that better than anyone ;-) _______________________________________________ Python-Dev mailing list -- python-dev@python.org To unsubscribe send an email to python-dev-le...@python.org https://mail.python.org/mailman3/lists/python-dev.python.org/ Message archived at https://mail.python.org/archives/list/python-dev@python.org/message/QK3KERIPYD3Q3XNKZJBQBQ6NUUKT63WN/ Code of Conduct: http://python.org/psf/codeofconduct/
