Issue 10025

Title
Implement LRUDict without OrderedDict
Priority
feature
Status
testing
Nosy list
albertca, ced, pokoli, reviewbot
Assigned to
ced
Keywords
review

Created on 2021-01-23.23:13:32 by ced, last changed 1 week ago by pokoli.

Messages

Author: [hidden] (ced) Tryton committer Tryton translator
Date: 2021-01-24.01:20:52

Last version is faster than original implementation and consume less memory.
lru-dict is not a possible alternative as it is missing default_factory.
And also time is not the only measure but memory usage is also. As lru-dict is using a dict and a list, it consumes more memory. I measured on similar test to be 10% more.

Author: [hidden] (albertca) Tryton committer
Date: 2021-01-24.00:48:52

As mentioned in the review, the proposed patch is much slower than current implementation.

However, using this script:

d = LRUDict(1000)
for x in range(10_000_000):
    d[x] = 1

I see a 5% performance improvement simply "inlining" _check_cache_size() code in __setitem__() method.

I also tested lru-dict (https://pypi.org/project/lru-dict/) and it is 5.8x faster than current implementation.

These are the results for the mentioned snippet (10M assignments):

  • Current core implementation: 7.8661s
  • Core implementation + inlining: 7.4633s
  • Proposed patch: 13.3959s
  • lru-dict: 1.3561s

All results are the median value of 5 runs.

Author: [hidden] (ced) Tryton committer Tryton translator
Date: 2021-01-23.23:13:30

This could be implemented only when we will drop support of Python3.6 because insertion-order preservation nature of dict as only be declared as specification of the language in Python 3.7.
The main advantage is that it prevent the creation of the doubly linked list of OrderedDict.

History
Date User Action Args
2021-03-31 12:08:51pokolisetnosy: + pokoli
2021-01-24 01:20:52cedsetmessages: + msg64061
2021-01-24 01:19:26reviewbotsetmessages: + msg64060
2021-01-24 00:48:52albertcasetmessages: + msg64059
nosy: + albertca
2021-01-23 23:45:08reviewbotsetmessages: + msg64058
nosy: + reviewbot
2021-01-23 23:14:53cedsetkeyword: + review
reviews: 327051002
status: in-progress -> testing
2021-01-23 23:13:32cedcreate

Showing 10 items. Show all history (warning: this could be VERY long)