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

[Nick Coghlan]

On 6 November 2017 at 06:50, Peter Ludemann via Python-Dev
<python-dev at python.org> wrote:
> Isn't ordered dict also useful for **kwargs?

3.6 already made this semantic change for **kwargs and class execution
namespaces - it just left the door open to having implementations meet
those requirements by way of substituting in collections.OrderedDict
for those use cases, rather than using a regular builtin dictionary.

So we're also already imposing the requirement on conformant Python
implementations to have a reasonably performant insertion-ordered
mapping implementation available.

The open questions around insertion ordering thus relate to what user
expectations should be for:

- dictionary displays
- explicit invocations of the builtin dict constructor
- mutating methods on builtin dicts
- serialisation and deserialisation operations that use regular dicts
(e.g. the JSON module, csv.DictReader/Writer)

It's that last category which is particularly problematic now, as in
*C*Python 3.6, the dicts used for these operations actually *are*
insertion ordered, so round trips from disk, through a CPython builtin
dict, and then back to disk *will* be order preserving, whereas in
previous versions there was no guarantee that that would be the case
(and hash randomisation meant the key reordering wasn't even
deterministic).

While such operations were already order preserving in PyPy (since
their switch to an insertion-ordered builtin dict implementation
served as prior art for the subsequent switch in CPython), we know
from experience that it's incredibly easy for even things that are
nominally implementation details of CPython to become expected
behaviour for Python users (e.g. there's still plenty of code out
there that relies on the use of an eager refcounting memory management
strategy to handle external resources properly).

That means our choices for 3.7 boil down to:

* make this a language level guarantee that Python devs can reasonably rely on
* deliberately perturb dict iteration in CPython the same way the
default Go runtime does [1]

When we did the "insertion ordered hash map" availability review, the
main implementations we were checking on behalf of were Jython & VOC
(JVM implementations), Batavia (JavaScript implementation), and
MicroPython (C implementation). Adding IronPython (C# implementation)
to the mix gives:

* for the JVM, the insertion ordered LinkedHashMap [2] has been
available since J2SE 1.4 was released in 2002
* for JavaScript, ECMA 6 defines the Map type [3] as an insertion
ordered key/value store
* for the .NET CLR, System.Collections.Specialized.OrderedDictionary
[4] seems to be the best builtin option, but the Java implementations
also map reasonably well to C# semantics
* for MicroPython, it's not yet clear whether or not the hash map
design used in CPython could also be adapted to their design
constraints (i.e. giving both insertion ordering and O(1) lookup
without requiring excessive amounts of memory), but it should at least
be feasible to make the semantics configurable based on a compile time
option (since CPython has a working C implementation of the desired
semantics already)

Since the round-trip behaviour that comes from guaranteed order
preservation is genuinely useful, and we're comfortable with folks
switching to more specialised containers when they need different
performance characteristics from what the builtins provide, elevating
insertion order preservation to a language level requirements makes
sense.

Cheers,
Nick.

[1] https://blog.golang.org/go-maps-in-action (search for "Iteration Order")
[2] https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashMap.html
[3] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map
[4] https://docs.microsoft.com/en-us/dotnet/api/system.collections.specialized.ordereddictionary?view=netframework-4.7.1

-- 
Nick Coghlan   |   ncoghlan at gmail.com   |   Brisbane, Australia