INADA Naoki <songofaca...@gmail.com> added the comment:
> 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.
----------
_______________________________________
Python tracker <rep...@bugs.python.org>
<https://bugs.python.org/issue32338>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe:
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
