I guess what `lru_cache` needs is atomic push-pop: on hit: pop(this) + push_back(this) on miss: pop_front() + push_back(this)
I reckon, if flat array is lazy (i.e. can grow larger than no. of keys), then *amortised* push-pop performance is not hard to achieve. Overall, it sounds more like heap queue; And it's a great example of feature creep -- once ordered dicts are builtin, every one and their niece wants to use them, not necessarily what they were originally envisioned for. By comparison, **kwargs and **meta are statistically mostly immutable. Perhaps distinct specialisations are better? On 20 September 2016 at 13:11, INADA Naoki <songofaca...@gmail.com> wrote: > 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 > Python-Dev@python.org > https://mail.python.org/mailman/listinfo/python-dev > Unsubscribe: > https://mail.python.org/mailman/options/python-dev/dimaqq%40gmail.com _______________________________________________ Python-Dev mailing list Python-Dev@python.org https://mail.python.org/mailman/listinfo/python-dev Unsubscribe: https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
