Dictionary order?

[Dan Stromberg]

Hi folks.

I'm still porting some code from Python 2.7 to 3.10.

As part of that, I saw a list being extended with a dict.values(), and
thought perhaps it wasn't ordered as intended on Python 2.7, even though
the problem would conceivably just disappear on 3.10.

So I decided to write a little test program to run on a variety of
CPythons, to confirm what I was thinking.

And instead I got a surprise.

On 1.4 through 2.1 I got descending key order.  I expected the keys to be
scattered, but they weren't.

On 2.2 through 3.5 I got ascending key order.  I expected the keys to be
scattered, but they weren't.

On 3.6 through 3.10 I got insertion order, as expected.

But why are 1.4 through 3.5 ordering so much?  It's like they're a treap or
red-black tree or something.  I'm pretty sure dict's used to be ordered in
a mostly-arbitrary way.

What am I missing?

Here's the little test program:

#!/usr/local/cpython-2.7/bin/python2

import sys

keys = [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7, 12, 11]

dict_ = {}
for key in keys:
    dict_[key] = 1

if list(dict_.keys()) == keys:
    # The order matches
    print('compact')
    sys.exit(0)
else:
    # The order does not match
    print('list(dict_): %s, keys: %s' % (list(dict_.keys()), keys))
    sys.exit(1)

Here's some output (irrelevant python's deleted) when run under
https://stromberg.dnsalias.org/~strombrg/pythons/

/usr/local/cpython-1.4/bin/python (1.4) bad  list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-1.5/bin/python (1.5.2) bad  list(dict_): [15, 14, 12,
11, 10, 9, 8, 7, 6, 5, 4, 2, 1], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-1.6/bin/python (1.6.1) bad  list(dict_): [15, 14, 12,
11, 10, 9, 8, 7, 6, 5, 4, 2, 1], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.0/bin/python (2.0.1) bad  list(dict_): [15, 14, 12,
11, 10, 9, 8, 7, 6, 5, 4, 2, 1], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.1/bin/python (2.1.0) bad  list(dict_): [15, 14, 12,
11, 10, 9, 8, 7, 6, 5, 4, 2, 1], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.2/bin/python (2.2.0) bad  list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.3/bin/python (2.3.0) bad  list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.4/bin/python (2.4.0) bad  list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.5/bin/python (2.5.6) bad  list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.6/bin/python (2.6.9) bad  list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-2.7/bin/python (2.7.16) bad  list(dict_): [1, 2, 4, 5,
6, 7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.0/bin/python (3.0.1) bad  list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.1/bin/python (3.1.5) bad  list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.2/bin/python (3.2.5) bad  list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.3/bin/python (3.3.7) bad  list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.4/bin/python (3.4.8) bad  list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.5/bin/python (3.5.5) bad  list(dict_): [1, 2, 4, 5, 6,
7, 8, 9, 10, 11, 12, 14, 15], keys: [5, 10, 15, 14, 9, 4, 1, 2, 8, 6, 7,
12, 11]
/usr/local/cpython-3.6/bin/python (3.6.13) good compact
/usr/local/cpython-3.7/bin/python (3.7.0) good compact
/usr/local/cpython-3.8/bin/python (3.8.0) good compact
/usr/local/cpython-3.9/bin/python (3.9.0) good compact
/usr/local/cpython-3.10/bin/python (3.10.0) good compact

BTW, usually with pythons (the script which can be found at the URL above),
a little test program will be written to exit shell-true for success or
shell-false for failure.  But in this case I'm using the exit code not as
success+failure but as compact+notcompact.

Why are those keys so ordered?

Also, I realize that the keys could come up ordered somehow by accident,
but I tried with 30 values (not just 12), and still got the same
weirdness.  Naturally, as the number of key-value pairs goes up, the chance
of accidental ordering goes way down.

Thanks for reading!