Repository navigation
Save OrderedDict import in re #76519
Description
Activity
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.
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
bugs.python.org fields: