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

Raymond Hettinger added the comment: Thanks. I'll look at this shortly. We're getting much closer. Just so that I don't lose other work I've done, am uploading new_merge2.py with in-line iterative tree construction of the initial tree. -- Added file:

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

Dennis Sweeney added the comment: key_and_reverse.py employs the same strategy as winners.py, but uses lists as the nodes of the tree rather than using Node instances. It also eliminates the recursion of treeify, and adds (with neither much of a performance hit nor much code duplication)

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

Dennis Sweeney added the comment: I mostly like new_merge.py too, especially the dynamic reduction of the tree. However, it looks like ``list(merge([2],[1],[1]))`` currently fails, and I think what's missing is the following in the sibling-promotion: + if sibling.left is not

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

Raymond Hettinger added the comment: Am leaning toward the iterative approach in new_merge.py because it most directly implements the core concept of storing the data in a binary tree. Merits: no recursion, no nested generators, avoids the clutter of left-empty and right-empty checks, easy

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

Change by Dennis Sweeney : Added file: https://bugs.python.org/file49167/losers.py ___ Python tracker ___ ___ Python-bugs-list mailing list

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

Change by Dennis Sweeney : Removed file: https://bugs.python.org/file49165/losers.py ___ Python tracker ___ ___ Python-bugs-list mailing

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

Dennis Sweeney added the comment: It seems to me that the code sprawl mostly comes from the separate handling of the four keyed/unkeyed and forward/reverse cases, which as far as I can tell requires a branch in the innermost loop if not unrolled into separate cases. I think

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

Change by Dennis Sweeney : Added file: https://bugs.python.org/file49166/recursive_merge.py ___ Python tracker ___ ___ Python-bugs-list

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

Change by Dennis Sweeney : Added file: https://bugs.python.org/file49165/losers.py ___ Python tracker ___ ___ Python-bugs-list mailing list

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

Change by Dennis Sweeney : Added file: https://bugs.python.org/file49164/tournament_heap.py ___ Python tracker ___ ___ Python-bugs-list

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

Change by Dennis Sweeney : Removed file: https://bugs.python.org/file48748/merge_recipe.py ___ Python tracker ___ ___ Python-bugs-list

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

Change by Dennis Sweeney : Removed file: https://bugs.python.org/file49156/recursive_merge.py ___ Python tracker ___ ___ Python-bugs-list

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

Change by Dennis Sweeney : Removed file: https://bugs.python.org/file48747/iter_merge.py ___ Python tracker ___ ___ Python-bugs-list

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

Change by Raymond Hettinger : Removed file: https://bugs.python.org/file49158/new_merge.py ___ Python tracker ___ ___ Python-bugs-list

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

Change by Raymond Hettinger : Added file: https://bugs.python.org/file49160/new_merge.py ___ Python tracker ___ ___ Python-bugs-list

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

Change by Raymond Hettinger : Added file: https://bugs.python.org/file49158/new_merge.py ___ Python tracker ___ ___ Python-bugs-list

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

Change by Raymond Hettinger : Removed file: https://bugs.python.org/file49157/new_merge.py ___ Python tracker ___ ___ Python-bugs-list

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

Raymond Hettinger added the comment: For comparison, I'm attaching an iterative version that manipulates the tree nodes with all local variables. Try it out and see what you think. -- Added file: https://bugs.python.org/file49157/new_merge.py ___

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

Dennis Sweeney added the comment: The attached recursive_merge.py should be much less ugly and still somewhat performant. It should be the same algorithm as that PR, just written recursively rather than iteratively. I got some text files from http://www.gwicks.net/dictionaries.htm and

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

Raymond Hettinger added the comment: The nested generators approach looks promising. I hope you keep working on that :-) I'm not too keen on PR 18427 because it is a massive explosion in code volume and complexity. With some continued effort, I expect we'll get to something much simpler and

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

Dennis Sweeney added the comment: As Serhiy suggested, keeping the algorithm but moving the Python implementation to be a generator again (as I recently changed in PR 18427) gives another performance boost (although this unrolling is many lines of code). Timing the C implementation:

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

Serhiy Storchaka added the comment: Are there any algorithmic optimizations in the Python version or it was just rewritten from a generator function to a class? If yes, how hard to keep the functional design? -- ___ Python tracker

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

Raymond Hettinger added the comment: Serhiy, I've got this one. It will still take a little to get to it, but I've already invested work in it. The code idea is plausible but I want to think it through for both CPython and PyPy. -- ___ Python

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

Dennis Sweeney added the comment: My suspicion was confirmed about PyPy (My PyPy here is Python 3.6.1 (784b254d6699, Apr 16 2019, 12:10:48) [PyPy 7.1.1-beta0 with MSC v.1910 32 bit] on win32). In what follows, "heapq2.py" had exactly the `class merge` Python implementation from PR 18427.

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

Dennis Sweeney 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

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

Serhiy Storchaka added the comment: Sorry, I did not notice that there is a C implementation in PR 18427. Changes in the Python implementations are so larger that I though this is the goal of the PR. Often the most clear and efficient way to implement an iterator in Python is to write a

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

Dennis Sweeney added the comment: First, as I posted at https://github.com/python/cpython/pull/17729#issuecomment-571864662, there is a theoretical advantage of fewer comparisons in all cases, and the new algorithm would be especially dominant when one iterable keeps winning. (I'm given to

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

Serhiy Storchaka added the comment: This is a large change. And making heaqq.merge a class looks unrelated to the declared goal. I afraid it may add significant overhead. Since this is an optimization, could you please provide any benchmarks which we can use to check the performance boost?

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

Change by Dennis Sweeney : -- pull_requests: +17803 pull_request: https://github.com/python/cpython/pull/18427 ___ Python tracker ___

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

Dennis Sweeney added the comment: PR 17729 is a C implementation of a non-recursive "flattening" of the the recursive-lazy-mergesort algorithm into a tournament whose state is a tree of losers of comparisons. -- ___ Python tracker

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

Change by Dennis Sweeney : -- pull_requests: +17174 pull_request: https://github.com/python/cpython/pull/17729 ___ Python tracker ___

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

Change by bbayles : -- nosy: +bbayles ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

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

Change by Dennis Sweeney : -- keywords: +patch pull_requests: +16903 stage: -> patch review pull_request: https://github.com/python/cpython/pull/17422 ___ Python tracker ___

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

Change by Raymond Hettinger : -- nosy: +tim.peters ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

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

Change by Raymond Hettinger : -- title: Iterable merge performance and inclusion in itertools -> Possible performance improvement for heaqq.merge() ___ Python tracker ___