On Tue, Sep 20, 2016 at 7:02 PM, INADA Naoki <songofaca...@gmail.com> wrote:
> On Tue, Sep 20, 2016 at 6:56 PM, Dima Tisnek <dim...@gmail.com> wrote:
>> Totally random thought:
>> Can lru_cache be simplified to use an ordered dict instead of dict +
>> linked list?
> I think so.
> See also: http://bugs.python.org/issue28199#msg276938

FYI, current dict implementation is not optimized for removing first
item like this:

// When hit max_size
Py_ssize_t pos;
PyObject *key;
if (PyDict_Next(d, &pos, &key, NULL)) {
    if (PyDict_DelItem(key) < 0) {
        // error.

So, before changing lru_cache implementation, I (or someone else) should rewrite
OrderedDict which has O(1) "remove first item" method. (At least
max_size is not None).

But both of OrderedDict and lru_cache improvements can't be in 3.6
since 3.6 is beta now.
I'll try it after 3.6rc1.

INADA Naoki  <songofaca...@gmail.com>
Python-Dev mailing list

Reply via email to