Title: Possible performance improvement for heaqq.merge()
Type: enhancement Stage: patch review
Components: Library (Lib) Versions: Python 3.9
Status: open Resolution:
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: Dennis Sweeney, bbayles, rhettinger, tim.peters
Priority: normal Keywords: patch

Created on 2019-11-29 02:44 by Dennis Sweeney, last changed 2020-02-10 01:28 by Dennis Sweeney.

File name Uploaded Description Edit Dennis Sweeney, 2019-11-29 02:44 Dennis Sweeney, 2019-11-29 03:06
Pull Requests
URL Status Linked Edit
PR 17422 open Dennis Sweeney, 2019-12-01 03:05
PR 17729 closed Dennis Sweeney, 2019-12-28 10:18
PR 18427 open Dennis Sweeney, 2020-02-10 01:28
Messages (5)
msg357631 - (view) Author: Dennis Sweeney (Dennis Sweeney) * Date: 2019-11-29 02:44
Although the implementation of the heapq.merge function uses an underlying heap structure, its behavior centers on iterators. For this reason, I believe there should either be an alias to this function in the itertools module or at least a recipe in the itertools docs describing the use of heapq.merge.

Furthermore, I have an implementation (attached) of heapq.merge that is twice as fast for two iterables (as used in mergesort and other common cases), and is faster for up to 6 or 7 iterables. I think it would be nice to special-case this for small numbers of iterables for this significant speedup.
msg357632 - (view) Author: Dennis Sweeney (Dennis Sweeney) * Date: 2019-11-29 03:06
The following seems like it is a short, readable recipe for itertools.
msg357664 - (view) Author: Dennis Sweeney (Dennis Sweeney) * Date: 2019-11-30 21:57
Disregard it would skip over a value that had already been retrieved from the iterator when the loop finished.
msg357665 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-11-30 22:10
Several thoughts:

* heapq.merge() could have plausibly been in the itertools module instead of the heapq module.  However, since it already has a home, there is no reason to move it or to create duplication with an intermodule dependency.  We certainly don't have a rule that the itertools module must house everything accepts an iterator as an input and returns an iterator in the output.

* The iter_merge() recipe is a bit sprawling and IMHO not a useful teaching aid (a primary goal of the itertools recipe), so it doesn't have much documentation value.  Instead, consider submitting this to the "more-itertools" project which is referenced by the docs.  There it would likely be used directly rather than as a recipe.

* Over the next few days, I'll take a closer look at the binary tree approach versus a heap approach.  I like how it intrinsically avoids the overhead of the 4-tuple while maintaining order, but I want to test how well it does with slow comparison keys (i.e. does the total number of comparisons get worse).  Am not sure whether the tree needs to be rebalanced as some of the input streams become exhausted.  I have a vague recollection that Knuth's TAOCP deemed the heap approach to be algorithmically superior, but need to dig out my books to be verify that.

* We could just build-out the current heapq.merge() code to include a special case for only two input iterables.  That would speed-up a common case by avoiding the overhead of tracking a 4-tuple for each element.  If you want to submit a PR for that, I would be happy to take a close look and verify the timings.

* It might be interesting to time the pure python variants against "sorted(chain(a, b, c, d, e))".  It isn't quite an apples-to-apples comparison because the latter pulls all the data in memory and it doesn't the runs pre-segregated, but it might give a sense of how well merge() could do if we decided to go gonzo on optimizations.  Until now, we've been satisfied with letting the heap structure minimize the number of comparisons and there hasn't been a focus on reducing the constant factor overhead.
msg358968 - (view) Author: Dennis Sweeney (Dennis Sweeney) * Date: 2019-12-28 22:09
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.
Date User Action Args
2020-02-10 01:28:45Dennis Sweeneysetpull_requests: + pull_request17803
2019-12-28 22:09:05Dennis Sweeneysetmessages: + msg358968
2019-12-28 10:18:50Dennis Sweeneysetpull_requests: + pull_request17174
2019-12-01 03:59:27bbaylessetnosy: + bbayles
2019-12-01 03:05:25Dennis Sweeneysetkeywords: + patch
stage: patch review
pull_requests: + pull_request16903
2019-11-30 22:13:46rhettingersetnosy: + tim.peters
2019-11-30 22:10:36rhettingersettitle: Iterable merge performance and inclusion in itertools -> Possible performance improvement for heaqq.merge()
2019-11-30 22:10:16rhettingersetmessages: + msg357665
2019-11-30 21:57:30Dennis Sweeneysetmessages: + msg357664
2019-11-30 21:07:09rhettingersetassignee: rhettinger
versions: - Python 2.7, Python 3.5, Python 3.6, Python 3.7, Python 3.8
2019-11-29 03:06:21Dennis Sweeneysetfiles: +

messages: + msg357632
2019-11-29 03:01:55xtreaksetnosy: + rhettinger
2019-11-29 02:44:21Dennis Sweeneycreate