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

31–40 of 72 posts

Re: Beating TimSort at Merging

#31

Post by min-cut »

danbruc wrote: post #27

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

Not 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

Re: Beating TimSort at Merging

#32

Post by agbell »

min-cut wrote: post #31
danbruc wrote: post #27

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

Not 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

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

Re: Beating TimSort at Merging

#33

Post by danbruc »

XelNika wrote: post #28
danbruc wrote: post #27

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

Yes, it says so in footnote 1 in the article. It's also not the benchmarked code so it doesn't really matter.

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

Re: Beating TimSort at Merging

#34

Post by CGamesPlay »

I 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++.

Re: Beating TimSort at Merging

#35

Post by peter422 »

CGamesPlay wrote: post #34

I 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++.

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

Re: Beating TimSort at Merging

#36

Post by tim-peters »

To 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 ;-) ).

Re: Beating TimSort at Merging

#37

Post by borski »

tim-peters wrote: post #36

To 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 _r…

Gosh, comments like these from the actual author are a reminder of why I love HN. :)

Re: Beating TimSort at Merging

#38

Post by min-cut »

agbell wrote: post #32
min-cut wrote: post #31

Earlier quoted context omitted.

Not 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

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

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

Re: Beating TimSort at Merging

#39

Post by adamgordonbell »

tim-peters wrote: post #36

To 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 _r…

Wow. Thanks for writing it. I believe this is the part you are referring to: https://github.com/python/cpython/blob/main/Objects/listobje...

Re: Beating TimSort at Merging

#40

Post by agbell »

min-cut wrote: post #38
agbell wrote: post #32

Earlier quoted context omitted.

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

I 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 use…

Yeah, good point. I think you are right about it being incorrect. Updating...
Post reply on HN