[issue38938] Possible performance improvement for heaqq.merge()

[Dennis Sweeney]

Dennis Sweeney <sweeney.dennis650 at gmail.com> added the comment:

The existing Python implementation is benefiting from the C accelerators for heapify and heapreplace. When forcing pure python using test.support, I get these results:

.\python.bat -m pyperf timeit -s "from random import random; from collections import deque; from test import support; merge = support.import_fresh_module('heapq', blocked=['_heapq']).merge; iters = [sorted(random() for j in range(1_000)) for i in range(20)]" "deque(merge(*iters), maxlen=0)"

    Master: Mean +- std dev: 73.1 ms +- 8.4 ms
    PR: Mean +- std dev: 63.7 ms +- 7.8 ms

I think I remember getting similarly slightly-better results out of PyPy, but I will double-check.

So while the existing "mixed-c-and-Python" implementation would be deleted, the "true pure-Python" implementation would get faster and the pure-c implementation would be created much faster. Is that an acceptable trade-off?

Regarding using a generator for the Python implementation, is it okay if type(heapq.merge) gives <class 'function'> for the Python implementation but <class 'type'> for the c implementation? How much seemingly-irrelevant variation like this is acceptable between the APIs?

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue38938>
_______________________________________