[Larry]
"I don't care about performance" is not because I'm aching for Python to run my code slowly. It's because I'm 100% confident that the Python community will lovingly optimize the implementation.
I'm not ;-)
So when I have my language designer hat on, I really don't concern myself with performance. As I thought I said earlier in the thread, I think we should figure out the semantics we want first, and then we figure out how to make it fast.
Pretty much the opposite of how Python started. The original lists and dicts were deliberately designed to have dirt simple implementations, in reaction against ABC's "theoretically optimal" data structures that were a nightmare to maintain, and had so much overhead to support "optimality" in all cases that they were, in fact, much slower in common cases. There isn't magic waiting to be uncovered here: if you want O(1) deletion at arbitrary positions in an ordered sequence, a doubly linked list is _the_ way to do it. That's why, e.g., Raymond said he still uses a doubly linked list, instead of an ordered dict, in the LRU cache implementation. If that isn't clear, a cache can be maintained in least-to-most recently accessed order with an ordered dict like so: if key in cache: cached_value = cache.pop(key) # remove key else: compute cached_value assert key not in cache cache[key] = cached_value # most recently used at the end now return cached_value and deleting the least recently used is just "del cache[next(iter(cache))]" (off topic, just noting this is a fine use for the "first()" function that's the subject of a different thread). We _could_ structure an ordered dict's hash+key+value records as a doubly linked list instead (and avoid the need for O(N) reorganizations). But then we piss away much of the memory savings (to store the new links) that was the _point_ of compact dicts to begin with. So there was a compromise. No links, deletion on its own is O(1), but can periodically require O(N) under-the-covers table reorganizations to squash out the holes. "Suitable enough" for ordered dicts, but _thought_ to be unsuitable for ordered sets (which appear to have higher rates of mixing deletions with insertions - the LRU cache example being an exception). But there are also other optimizations in the current set implementation, so "fine, add the doubly linked list to sets but not to dicts" is only part of it. Which may or may not be possible to match, let alone beat, in an ordered set implementation. A practical barrier now is that Python is too mature to bank on loving optimizations _after_ a change to a core feature is released. It's going to need a highly polished implementation first. I certainly don't object to anyone trying, but it won't be me ;-)