[Python-Dev] Python 3.6 dict becomes compact and gets a private version; and keywords become ordered

[Dima Tisnek]

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 <songofacandy at gmail.com> wrote:
> On Tue, Sep 20, 2016 at 7:02 PM, INADA Naoki <songofacandy at gmail.com> wrote:
>> On Tue, Sep 20, 2016 at 6:56 PM, Dima Tisnek <dimaqq at 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  <songofacandy at gmail.com>
> _______________________________________________
> Python-Dev mailing list
> Python-Dev at python.org
> https://mail.python.org/mailman/listinfo/python-dev
> Unsubscribe: https://mail.python.org/mailman/options/python-dev/dimaqq%40gmail.com