[issue44555] Dictionary operations are LINEAR for any dictionary (for a particular code).

[Daniel Fleischman]

Daniel Fleischman <danielfleischman at gmail.com> added the comment:

Thank you again, Dennis.

I would disagree with your conclusion for mainly 3 reasons:

1. The linked list proposal would increase the memory usage by 2 Py_ssize_t per entry, plus another 2 for the whole dictionary. I don't think this is an overwhelming amount of extra memory for Python, but of course it's open for discussion. Insertions and removals would become marginally slower (I'll try to measure it), membership wouldn't suffer, and iteration would become O(1) per element iterated on. 

2. I think that this case is covered by "Dynamic Mappings" in the document you've linked to.

3. This is not about the ordering in ducts being first or second nature. Please read the example in bad_dict_example.py to see a bad case where hearing over a dict of size 1 can take milliseconds.

I want to reiterate (pun not intended) that this is not a use case for me, but it surprised me that dictionaries display this behavior. It's not hard to imagine a real use case where it just happens that someone deletes elements from a dictionary in insertion order. Or that someone deletes all keys but the last inserted (in any order), resulting in a dictionary that takes way too long to iterate on. 


Thank you for the discussion. :)

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue44555>
_______________________________________