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

[INADA Naoki]

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>