9 ms·
Beating TimSort at Merging
- rkalla 5y agoExcellent read.
- agbell 5y agoTimSort is cool. In it's worst case it looks no better than merge sort, but give it some partially order data, or small amounts of data, where it uses insertion sort, and it really shines.
- thomas536 5y agoAre there similar relatively simple methods or simd tricks for multi-way merges?
- dragontamer 5y agoI 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 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.
- lyxell 5y agoInteresting 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 https://news.ycombinator.com/item?id=27718701
- agbell 5y agoThat'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.
- CogitoCogito 5y ago> It is interesting when our normal short hands for thinking about runtime complexity break down. Actually I think more interesting would be to write a python version following the algorithm of your C extension (i.e. only allow two lists, don't allow generators, don't return generators, etc). You could probably do that quite quickly and generate the same graphs. I would expect that python version to lie somewhere between your C extension and the heapq.merge() version which is more general. edit: If you were to do this, I wouldn't recommend using the python version in your blog since it pops the lists from the front. This seems to be O(n) in general: https://wiki.python.org/moin/TimeComplexity https://wiki.python.org/moin/TimeComplexity I did a 10 minute glance at the python source code and couldn't totally verify this (it needs more than 10 minutes...), but it makes sense for popping from anywhere but the back to cause a list copy to occur. Maybe this isn't technically necessary when popping from the front, but I couldn't verify it. Either way it's easy to avoid by just not mutating the input lists anyway so I don't see a good reason not to go that way.
- agbell 5y agoSo we could determine what gains I am getting are due to C and the specific compares and which are due just being 2 lists? That would be an interesting test. Maybe I'll do a follow-up. Thanks for reading the article. I suspect you know way more about C extensions in Python than I do. I saw you have a talk on this topic. I think you are totally right that pop is not the way to go, but using an offset to track the head, like the C example does. I actually put that in a footnote, because I was considering testing my python version but the SO answer mentioned pop being expensive. I think the simple version is still great as psuedo-code for communicating a solution though and hopefully it makes the c code a bit easier to follow once you've seen the python version.
- forrestthewoods 5y agoGreat post. I almost did a spit take when I read: > Timsort overcomes this disadvantage by being written in C rather than Python. Yeah, Python is SLOW. Thankfully the author dug into C. That was nice to see. Edit: lol I have no idea why this is being downvoted. Y’all weird.
- ww520 5y agoThat's what I suspected when reading the first part of the post where it states that heapq.merge() is slower than sort(). Hmm, isn't it comparing Apple to Orange since heapq.merge() is implement in Python and the system sort() would be in C?
- CogitoCogito 5y agoIt 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/6252670732c68420c2a8b3f0259559e45eed7610/Lib/heapq.py#L314-L392 https://github.com/python/cpython/blob/6252670732c68420c2a8b... It might also be since the python version has more options (like arbitrarily many iterables), but I presume it's the fact that the extension is written in C.
- typon 5y agoBecause it's written in python
- CogitoCogito 5y agoRe-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.
- masklinn 5y ago> Re-writing it in C wouldn't automatically make much of a difference. It probably would even with a line-for-line translation: you’d save all the interpreter overhead, function calls if there are any (I did not look), and most refcount traffic.
- CogitoCogito 5y agoMaybe. It's true you would save a certain amount of interpreter overhead and some refcount. How much that would help is not clear to me. So really I just see any speedups pure speculation honestly. Besides the interesting question isn't really whether it speeds up or not (it obviously will speed up at least a little bit with any non-sane implementation), but how _much_ it speeds up. If you gain 1% honestly who cares. If you gain 30%, then that's more interesting. And how close can you get with this more general version in C to the version in the blog post that is using a simplified implementation without all the extra features. Anyway I am curious to know the answer, but I don't personally feel like writing out the implementation. If you do, I'd be interested in seeing the results.
- benatkin 5y agoDoesn't explain why Earthly.dev is under the BSL.
- quibono 5y agoI don't know why you would expect a post with a title like this to touch on that, even though being wary of the BSL licence is fair.
- jhokanson 5y agoAs 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 ‘mergesort’ or ‘timsort’ is actually used, even if ‘mergesort’ is specified. User selection at a finer scale is not currently available." Awesome ... Also, apparently mergesort may also be done using radix sort for integers "‘mergesort’ and ‘stable’ are mapped to radix sort for integer data types."
- TheRealPomax 5y agoTurns 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 ;)
- tehjoker 5y agoThis 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.
- CogitoCogito 5y agoI 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.
- toxik 5y agoTangential but np.bincount is typically the fast version of np.unique. Not entirely the same thing, but it’s worth knowing about it.
- dang 5y agoPast TimSort threads, for anyone interested: Timsort, the Python sorting algorithm - https://news.ycombinator.com/item?id=21196555 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 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 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 https://news.ycombinator.com/item?id=9778243 - June 2015 (1 comment) Timsort - https://news.ycombinator.com/item?id=3214527 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 https://news.ycombinator.com/item?id=752677 - Aug 2009 (13 comments)
- elpakal 5y agoRecently learned that Swift also uses TimSort, really cool to see other language implementations: https://news.ycombinator.com/item?id=20884208 https://news.ycombinator.com/item?id=20884208
- actually_a_dog 5y agoI once had a Hackerrank problem that ultimately boiled down to "merge these sorted lists." I had 15 minutes, I think, to code the solution. I spent 10 of them deciding whether to use list.sort(), then finally just did it and cited the paper linked in On the Worst-Case Complexity of TimSort to claim linear time. I passed, and ultimately got the job.
- kzrdude 5y agoCould Cython be used for writing the fast module here instead?
- danbruc 5y agoThe first Python implementation is bad - removing the first element in each iteration is O(n), the C implementation gets this right by maintaining one index into each list instead of modifying the lists.
- XelNika 5y agoYes, it says so in footnote 1 in the article. It's also not the benchmarked code so it doesn't really matter.
- danbruc 5y agoI missed the footnote. My point was more that one could have compared this with the C implementation as heapq.merge is a different algorithm and so there is no actual comparison of the same algorithm in C and Python.
- min-cut 5y agoNot only that, but also list(a + b) is producing two different new lists since (a + b) produces a list and list() constructs a new list copy. The benchmark would be faster if the OP just did def sort_test(): m2 = a + b; m2.sort() instead of def sort_test(): m2 = list(a + b); m2.sort() EDIT: It seems like OP fixed this issue in perf.py, but left it in test.py
- agbell 5y agoYou can check it, but I'm pretty sure the difference is negligible. But yeah, all benchmarks are using the code in perf and the pop code is just to demonstrate. It is not benched. Edit: dropping the extra list() from the blog code examples.
- min-cut 5y agoI see about a 10% performance improvement on my local machine on the input in test.py when not constructing the unnecessary second list. I don't really buy that it reads nicer in prose since you can just do (a + b).sort() if you want. Plus, I feel like it's important for readability to not be unnecessarily redundant. Having list(a + b) code also risks creating misconceptions about how lists can be constructed and used in Python.
- CGamesPlay 5y agoI definitely used this to my advantage in ACM ICPC contests. Most of the students and professors wrote the problems and benchmarked against Java. However, on several problems, it boiled down to "write this specific algorithm for this class of problem, or use C." I once netted my team an extra problem after we timed out in Java and I just rewrote the teammate's solution in C++.
- peter422 5y agoOutside of some very specific parsing problems where Java standard library was very helpful, writing solutions in C was the way to go. Though while it could allow certain parts of the code to be less efficient, if you had completely the wrong algorithm it wasn’t going to save you.
- kilotaras 5y agoMy team used java in two cases: BigInteger or 'isProbableTime.' For everything else performance penalty was almost always unacceptable. C++ can also be sometimes finetuned enough to pass with unintended complexity (i.e. O(n lg n) instead of O(n)).
- kilotaras 5y agoisProbableTime -> isProbablePrime.
- tim-peters 5y agoTo get more gonzo, in CPython's list.sort(), the C code that actually merges two lists (which happen, in context, to be two contiguous array slices) is in listobject.c's `merge_at(()` function. That brings in the world of "galloping" (exponential search) optimizations, much faster than one-pair-at-a-time compares in many real-world cases. So that's a whole lot of additional complication, but it's the heart of what _really_ makes timsort shine in its "jaw dropping" cases. Tim (of "timsort" - which was an inside joke name at the start, because I never expected anything outside of CPython would use it ;-) ).
- borski 5y agoGosh, comments like these from the actual author are a reminder of why I love HN. :)
- barosl 5y agoI'm also amazed by the fact that that John Nagle from the popular Nagle's algorithm is still active on HN!
- viraptor 5y agoThere are lots of known people on HN. I started tagging HN usernames with a browser extension some time ago and sometimes I spot some really interesting exchanges given the context of what the posters worked on.
- deleted 5y ago[deleted]
- pg_bot 5y agoI was thinking about how to make sorting faster the other day and was toying around with the idea of a permutation sort. If you think about a list of items generally (at least) one of the permutations of the list is guaranteed to be the correct sort order. Theoretically you should be able to do a binary search to find a correct permutation since there should always be a comparison you can do to reduce the search space by half. You should be able to go faster if there is duplicated data since there are multiple permutations of the list that would work.
- saagarjha 5y agoAssuming constantly time comparison, the best you are going to be able to do is log(n!), which is O(n log n) by Stirling's approximation. But comparing a permutation is likely to be O(n), so you'll probably do worse than that.
- pg_bot 5y agoYou don't need to compare permutations you reduce the set of possible permutations until you reach the one that must be the answer. Theoretical performance should be O(log n)
- saagarjha 5y agoNo, I understand your algorithm, I’m just saying that you’ll start with n! permutations and halve that with each step. This will require log(n!) steps.
- tim-peters 5y agoSorry, nope. There aren't n permutations you're searching through, but the factorial of n to search through. That's the heart of the information-theoretic proof that no comparison-based sorting algorithm can do better, on average, than needing a number of comparisons equal to the base-2 logarithm of the factorial of n. Which, as already said, is O(n log n).
- 5y ago
- sam1r 5y agoThis is awesome. Thanks!