> 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.