> Raymond: Would you mind to explain why you close the issue?

On python-dev, Inada suggested he would drop this issue if Guido approved regular dicts having guaranteed order.  That occurred and I closed this issue.

The other reasons were listed earlier in this thread and on my python-dev post.   Roughly, the OP is making the wrong trade-offs, trying to optimize what regular dicts are already good at.  The OrderedDict aspires to be good at other things and to serve as an alternative to regular dicts in situations that aren't favorable to regular dicts.

The OP seems to be infinitely persistent on this subject eventhough I've clearly stated that I do not approve of this going forward.  No amount of talking seems to convince him of the merits of doubly linked list.  In the LRU case, when the cache is large enough, there will be a high hit rate.  With a doubly-linked list, all that is entailed is a single dict lookup for the link and a fast link update (all currently done in C with beautifully clean and efficient code).  Without a doubly-linked list, we have to remove an element from the dictionary (leaving a hole), then re-add the element at the end and then periodically run and an O(n) compaction.  The current design doesn't have any of that cost.

The current ordered dict could run move_to_end() a billion times in succession and never trigger an O(n) resize or compaction.  The OP either doesn't get this or doesn't care about what ordered dicts were actually designed to be good at.

The current design was done on purpose.  There were explicitly rejected alternatives.  For example, we could have keep a regular dictionary augmented by a list, just appending and periodically compacting.  This would have given faster iteration, less memory usage, and a simpler implementation; however, it was explicitly rejected because doubly-linked lists could gracefully handle frequent semi-random deletions, insertions, and moves-to-end points.  For example, the compact dict would perform terribly for repeated move to front operations.

When I get time over the holidays, I will build some examples where the proposed patch causes performance to crater.  In the mean time, I have other important things to work on (documenting and testing the new dict guarantees, features for 3.7 before the freeze, etc).