Totally random thought:
Can lru_cache be simplified to use an ordered dict instead of dict +
On 15 September 2016 at 20:30, Serhiy Storchaka <storch...@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)))"
>> -> 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 mailing list