On Sat, 1 Aug 2020 at 00:32, Guido van Rossum firstname.lastname@example.org 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)