Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Beating TimSort at Merging

earthly.dev

Post reply on HN
Print view View original

11–20 of 72 posts

Re: Beating TimSort at Merging

#11

Post by nightpool »

CogitoCogito wrote: post #7

It seems like the built in heapq.merge() should be as fast as the implementation here. I mean if it's really just merging sorted lists, why wouldn't it be as fast as this implementation? edit: Okay one reason is that heapq.merge is written in python: https://github.com/python/cpython/blob/6252670732c68420c2a8b... It might also be since the python version has more options (like arbitrarily many iterables), but I presu…

TFA explains this, although they never actually links the StackOverflow answer that they quote from.

> CPython’s list.sort is implemented in C (avoiding interpreter overhead), while heapq.merge is mostly implemented in Python, and optimizes for the “many iterables” case in a way that slows the “two iterables” case.

Going to the original StackOverflow answer, we can see the same user (ShadowRanger) expanding on this in a comment: https://stackoverflow.com/questions/464342/combining-two-sor...

> The selling point for heapq.merge is that it doesn't require either the inputs or the outputs to be list; it can consume iterators/generators and produces a generator, so huge inputs/outputs (not stored in RAM at once) can be combined without swap thrashing. It also handles merging an arbitrary number of input iterables with lower overhead than might be expected (it uses a heap to coordinate the merging, so the overhead scales with the log of the number of iterables, not linearly, but as noted, that doesn't matter for the "two iterable" case).

Re: Beating TimSort at Merging

#12

Post by dragontamer »

thomas536 wrote: post #4

Are there similar relatively simple methods or simd tricks for multi-way merges?

I dunno about "multiway merge". But your standard 2-way merge is SIMD-optimized by having a binary-search across the "diagonals" of the so-called mergepath.

Leading to O(lg(p * sqrt(2))) time for the longest comparison diagonal, where "p" is the number of processors. Including thread divergence, that's O(N/p * lg(p * sqrt(2))) total work done, or assuming constant-p, O(N) of work per 2-way SIMD merge (with a large "p" providing an arbitrarily large speedup: but in practice is probably limited to 1024 for modern GPU architectures. Since modern GPUs only really "gang up" into 1024-CUDA thread blocks / workgroups efficiently)

https://web.cs.ucdavis.edu/~amenta/f15/GPUmp.pdf

This provides a natural way at allowing ~1024 CUDA threads in a singular block to sort a list at O(n * log(n)) efficiently.

Re: Beating TimSort at Merging

#13

Post by dang »

Past TimSort threads, for anyone interested:

Timsort, the Python sorting algorithm - https://news.ycombinator.com/item?id=21196555 - Oct 2019 (131 comments)

On the Worst-Case Complexity of TimSort - https://news.ycombinator.com/item?id=17883461 - Aug 2018 (74 comments)

Timsort is a sorting algorithm that is efficient for real-world data - https://news.ycombinator.com/item?id=17436591 - July 2018 (77 comments)

Functional verification with mechanical proofs of TimSort [pdf] - https://news.ycombinator.com/item?id=9778243 - June 2015 (1 comment)

Timsort - https://news.ycombinator.com/item?id=3214527 - Nov 2011 (27 comments)

Java has switched from Mergesort to TimSort - https://news.ycombinator.com/item?id=752677 - Aug 2009 (13 comments)

Re: Beating TimSort at Merging

#14

Post by [deleted] »

CogitoCogito wrote: post #7

It seems like the built in heapq.merge() should be as fast as the implementation here. I mean if it's really just merging sorted lists, why wouldn't it be as fast as this implementation? edit: Okay one reason is that heapq.merge is written in python: https://github.com/python/cpython/blob/6252670732c68420c2a8b... It might also be since the python version has more options (like arbitrarily many iterables), but I presu…

[deleted]

Re: Beating TimSort at Merging

#15

Post by CogitoCogito »

nightpool wrote: post #11
CogitoCogito wrote: post #7

It seems like the built in heapq.merge() should be as fast as the implementation here. I mean if it's really just merging sorted lists, why wouldn't it be as fast as this implementation? edit: Okay one reason is that heapq.merge is written in python: https://github.com/python/cpython/blob/6252670732c68420c2a8b... It might also be since the python version has more options (like arbitrarily many iterables), but I presu…

TFA explains this, although they never actually links the StackOverflow answer that they quote from. > CPython’s list.sort is implemented in C (avoiding interpreter overhead), while heapq.merge is mostly implemented in Python, and optimizes for the “many iterables” case in a way that slows the “two iterables” case. Going to the original StackOverflow answer, we can see the same user (ShadowRanger) expanding on this i…

Yeah looking at the all the features of the heapq.merge() version, I kind of doubt implementing it in C would speed it up much at all.

edit: Yeah I now see where the author mentioned the design philosophy of the python version. It was a bit burried, but it answers my question like you say. I personally find that to be the most interesting part.

Re: Beating TimSort at Merging

#16

Post by TheRealPomax »

jhokanson wrote: post #10

As someone that rarely works with Python lists, as opposed to numpy arrays, I was pleasantly surprised to see numpy does what I would expect in providing a mergesort option. I'm surprised Python doesn't, other than via heapq and only implemented in Python (according to my reading of the post and a very quick Google search). Oops, just for fun the numpy documentation currently states: "The datatype determines which of…

Turns out that at least in terms of performance, everyone using numpy is fine with this. It just needs to run fast enough, not as fast as possible ;)

Re: Beating TimSort at Merging

#17

Post by CogitoCogito »

typon wrote: post #9
CogitoCogito wrote: post #7

It seems like the built in heapq.merge() should be as fast as the implementation here. I mean if it's really just merging sorted lists, why wouldn't it be as fast as this implementation? edit: Okay one reason is that heapq.merge is written in python: https://github.com/python/cpython/blob/6252670732c68420c2a8b... It might also be since the python version has more options (like arbitrarily many iterables), but I presu…

Because it's written in python

Re-writing it in C wouldn't automatically make much of a difference. Of course a C implementation wouldn't be slower (at minimum you could flatten out the byte-code sequence and use the generated C api calls), but it wouldn't necessarily be noticeably faster. Given the features of the python version, it might very well be the case that writing the same code in C wouldn't speed things up if the same use-cases were supported. Though I would be curious to know if it actually would speed up significantly.

Re: Beating TimSort at Merging

#18

Post by tehjoker »

TheRealPomax wrote: post #16
jhokanson wrote: post #10

As someone that rarely works with Python lists, as opposed to numpy arrays, I was pleasantly surprised to see numpy does what I would expect in providing a mergesort option. I'm surprised Python doesn't, other than via heapq and only implemented in Python (according to my reading of the post and a very quick Google search). Oops, just for fun the numpy documentation currently states: "The datatype determines which of…

Turns out that at least in terms of performance, everyone using numpy is fine with this. It just needs to run fast enough, not as fast as possible ;)

This is not true. I have written many libraries to improve on the performance of numpy for image processing applications. Sort backs many operations, such as unique, that result in painfully slow code.

Re: Beating TimSort at Merging

#19

Post by adamgordonbell »

lyxell wrote: post #5

Interesting read. This post seems to be written by Adam Gordon Bell who is also the host of the excellect CoRecursive podcast. Recently featured at HN in The Untold Story of SQLite [0]. [0]: https://news.ycombinator.com/item?id=27718701

That's me. Thanks for reading it and listening to the podcast. The SQLite episode is now nearly the most listened to, thanks to hacker news.

On Merging lists: I was caught off guard by recommendation to use sort to merge sorted lists. Everyone I mentioned it to was surprised as well so I thought it was worthy of some investigation. This is my first C extension in Python and I got help so someone else might be able to do even better than this.

It is interesting when our normal short hands for thinking about runtime complexity break down.

Re: Beating TimSort at Merging

#20

Post by CogitoCogito »

tehjoker wrote: post #18
TheRealPomax wrote: post #16

Earlier quoted context omitted.

Turns out that at least in terms of performance, everyone using numpy is fine with this. It just needs to run fast enough, not as fast as possible ;)

This is not true. I have written many libraries to improve on the performance of numpy for image processing applications. Sort backs many operations, such as unique, that result in painfully slow code.

I too have written a lot of extension code to speed up numpy code. It's often not even especially difficult since any code at that level tends to be very algorithmic and looks essentially the same if written in numpy or C++. Having control of the memory layout and algorithms can be a huge win.

Of course I don't _usually_ do this, but that's just be most of the code I write doesn't need it. But it's not at all some crazy sort of thing to do.

Post reply on HN