Beating TimSort at Merging

#1

Post by andrewstetsenko » Tue, Jul 13, 2021, 4:46 PM UTC

Beating TimSort at Merging
earthly.dev

Re: Beating TimSort at Merging

#2

Post by rkalla » Tue, Jul 13, 2021, 5:13 PM UTC

Excellent read.

Re: Beating TimSort at Merging

#3

Post by agbell » Tue, Jul 13, 2021, 5:19 PM UTC

TimSort 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.

Re: Beating TimSort at Merging

#4

Post by thomas536 » Tue, Jul 13, 2021, 5:41 PM UTC

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

Re: Beating TimSort at Merging

#5

Post by lyxell » Tue, Jul 13, 2021, 5:44 PM UTC

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

Re: Beating TimSort at Merging

#6

Post by forrestthewoods » Tue, Jul 13, 2021, 5:45 PM UTC

Great 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.

Re: Beating TimSort at Merging

#7

Post by CogitoCogito » Tue, Jul 13, 2021, 5:45 PM UTC

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 presume it's the fact that the extension is written in C.

Re: Beating TimSort at Merging

#8

Post by benatkin » Tue, Jul 13, 2021, 5:46 PM UTC

Doesn't explain why Earthly.dev is under the BSL.

Re: Beating TimSort at Merging

#9

Post by typon » Tue, Jul 13, 2021, 5:48 PM UTC

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: Beating TimSort at Merging

#10

Post by jhokanson » Tue, Jul 13, 2021, 5:50 PM UTC

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 ‘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."