Since regular dicts are now ordered by default, the OrderedDict import is no longer necessary.

Please don't do this.
del d[next(iter(d))] is not O(1) on current dict implementation.
OrderedDict is designed for such use cases. Please keep using it.

This is surprising. But OrderedDict also can be O(N) here.

Do you have benchmarking results Inada?

This is surprising. But OrderedDict also can be O(N) here.

Current dict implementation doesn't skip empty entries.
So next(iter(D)) takes time.
On the other hand, OrderedDict uses doubly-linked list to find first entry.

(I fixed it in compact ODict branch, but it added one word to dict)

Do you have benchmarking results Inada?

$ ./python -m perf timeit -s 'cache={}' -- '
for i in range(10000):
    if len(cache) > 512:
        del cache[next(iter(cache))]
    cache[i]=i
'
.....................
Mean +- std dev: 6.81 ms +- 0.08 ms

$ ./python -m perf timeit -s 'from collections import OrderedDict; cache=OrderedDict()' -- '
for i in range(10000):
    if len(cache) > 512:
        cache.popitem(last=False)
    cache[i]=i
'
.....................
Mean +- std dev: 3.75 ms +- 0.07 ms

Performance difference is measurable even when N is only 512.

Maybe, we can use hack similar to Python 3.5 had for O(1) popitem().
When entries[0].key==NULL, (Py_ssize_t)entries[0].value can be index
to first known non-empty entry.

Hmm, 0.3 μs for each lookup may be negligible compared to re.compile() speed?

del d[next(iter(d))] is not O(1) on current dict implementation.

We are talking about a dictionary of 512 items in the worst case. On such very tiny collection, benchmarking matters more than O(...) complexity ;-)

We are talking about a dictionary of 512 items in the worst case. On such very tiny collection, benchmarking matters more than O(...) complexity ;-)

You're right. Rob Pike said:

"Fancy algorithms are slow when n is small, and n is usually small."
http://users.ece.utexas.edu/~adnan/pike.html

• del cache[next(iter(cache))] happens only when sre.compile() is called.
• del cache[next(iter(cache))] is much faster than sre.compile().

OK, performance difference is negligible, surely.

New changeset b931bd0 by Serhiy Storchaka in branch 'master':
bpo-32338: OrderedDict import is no longer needed in re. (bpo-4891)
b931bd0

New changeset 39441fc by Miss Islington (bot) in branch '3.7':
bpo-32338: OrderedDict import is no longer needed in re. (GH-4891)
39441fc