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

[Dima Tisnek]

Totally random thought:

Can lru_cache be simplified to use an ordered dict instead of dict +
linked list?

On 15 September 2016 at 20:30, Serhiy Storchaka <storchaka at gmail.com> wrote:
> On 15.09.16 19:13, Antoine Pitrou wrote:
>>
>> Since this micro-benchmark creates the keys in order just before
>> filling the dict with them, randomizing the insertion order destroys
>> the temporal locality of object header accesses when iterating over the
>> dict keys. *This* looks like the right explanation, not branch
>> mispredicts due to NULL checks.
>>
>> This also shows that a micro-benchmark that merely looks ok can actually
>> be a terrible proxy of actual performance.
>
>
> Thanks you for great explanation Antoine! I came to the same conclusions
> about randomized integers example, but didn't notice that this also is a
> main cause of the speed up of strings example.
>
>> As a further validation of this theory, let's dramatically decrease the
>> working set size on the initial benchmark:
>>
>> $ ./python -m timeit -s "d=dict.fromkeys(map(str,range(10**3)))"
>> "list(d)"
>>
>> -> Python 3.5: 100000 loops, best of 3: 10.9 usec per loop
>> -> Python 3.6: 100000 loops, best of 3: 9.72 usec per loop
>>
>> When the working set fits in the cache, this micro-benchmark is
>> only 12% slower on 3.5 compared to 3.6.
>> *This* much smaller difference (a mere 1.2ns difference per dict
>> element) could be attributed to eliminating the NULL checks, or to any
>> other streamlining of the core iteration logic.
>
>
> Yet one example, with random hashes and insertion order independent from the
> creation order.
>
> $ ./python -m timeit -s "import random; a = list(map(str, range(10**6)));
> random.shuffle(a); d = dict.fromkeys(a)" -- "list(d)"
>
> Python 3.5: 180, 180, 180 msec per loop
> Python 3.6: 171, 172, 171 msec per loop
>
> Python 3.6 is 5% faster and this looks closer to the actual performance.
>
>
>
> _______________________________________________
> 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