This is not great news. A solution could be to make dict.ordered() force compaction -- if there are no deleted keys this would be a no-op. We'd have to be able to tell in constant time whether this is the case. But yeah, this would be a dangerous thing in the hands of folks below wizard level. Another solution could be to make dict.ordered() fail if there are deleted keys. But that's not a great experience either.

All in all I retract this idea.

On Fri, Jul 31, 2020 at 5:31 PM Stestagg <> wrote:
On Sat, 1 Aug 2020 at 00:32, Guido van Rossum <> wrote:
If true this would be a huge argument against adding indexing and slicing (other than the special case starting with 0). However, I don't think it's true. The dict implementation (again, starting in 3.6) actually stores the list of keys in a compact array, in the insertion order. The hash table stores indices into this array. Moreover, in order to implement the ordered property, you pretty much have to do this (since the hash table *definitely* isn't going to be ordered :-). So indexing and slicing into this array would seem to be possible, unless I am missing something. I'm CC"ing Inada Naoki because it's his code -- maybe he can enlighten us.

I’m not Inada Naoki :). So happy to be corrected, but I looked into this quite closely. 

The dict keys is compact only *until* you delete an item, at which point, a hole is left in the array, which defeats direct lookups (either by indexing or via a view).  Order preservation is still kept as code that iterates over dictionaries knows to just skip the holes. 

I’m unsure when/if compaction is called however. So there may be a technique for forcing the keys to be compacted again.  This would cause very unpredictable performance in the case of large dictionaries (a main use-case here)


Python-ideas mailing list --
To unsubscribe send an email to
Message archived at
Code of Conduct:

--Guido van Rossum (
Pronouns: he/him (why is my pronoun here?)