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

[Dennis Sweeney]

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

less_movement.py is my favorite so far. It still handles key and reverse,
but using instance attributes instead of the list indices I tried before.
It does this by only advancing the "key" and "leaf" attributes up toward
the root (where the key is just the value if key is None), while the value
is stored only in the leaf. Since the "value" attribute is no longer used
except for at the leaves, we can pack a leaf's value into its left slot
and reduce the number of slots.

This seems to run very well on pypy and it looks like it would be pretty
receptive to a c implementation, which I would be happy to work on.

----------
title: Possible performance improvement for heaqq.merge() -> Possible performance improvement for heapq.merge()
versions: +Python 3.10 -Python 3.9
Added file: https://bugs.python.org/file49198/less_movement.py

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