4 ms·

Are there benchmarks available for this kind of algorithm? If you come up with a fast sorting algorithm how would you go about making a case it's faster than cu

Are there benchmarks available for this kind of algorithm? If you come up with a fast sorting algorithm how would you go about making a case it's faster than currently used ones on real world data?

gleenn 8y ago
Well I think that ship has already sailed, Timsort is used in Java on Android and Python, so it's already seen massive adoption.
repsilat 8y ago
I'd hope people using it wouldn't have chosen it unless they had measured performance -- doubly so if the switched to it from something else. On the other hand, common third-party benchmarks may not be useful for measuring these sorts of improvements, which take advantage of common input distribution biases. "Real world workloads" is really too much of a simplification -- people sort all shapes and sizes of data. When JS engines started getting fast(er), every engine made their own preferred benchmark because they said existing ones didn't adequately show the real-world gains their engines were providing. We shouldn't be reflexively cynical about that. If they have made good-faith measurements, it is likely that old benchmarks were "unrepresentstive" in some way. Again, "real world benchmarking" is hard, and that applies just as much to yesterday's benchmarks as today's.
hyperpape 8y ago
You can go back and read the mailing list archives to see the benchmarks that were used by Python devs to decide on using Timsort: https://mail.python.org/pipermail/python-dev/2002-July/thread.html#26837 https://mail.python.org/pipermail/python-dev/2002-July/threa... You can also read Tim Peter's notes about the sort: https://bugs.python.org/file4451/timsort.txt https://bugs.python.org/file4451/timsort.txt That was back in 2002, so there's certainly been a lot of scrutiny since then. In particular, I've never actually read about Java sorting benchmarks, but there are tremendously sophisticated benchmarking tools/benchmarking experts in the Java world, so I imagine that it got a lot of analysis there.
- BeeOnRope 8y ago
  It's worth noting that Java doesnt exclusively use Timsort. Depeding on the data type and heuristics based mostly on the size of the input array, a simpler sort such as counting sort may be use. You can find a more detailed summary at: https://stackoverflow.com/a/41129231/149138 https://stackoverflow.com/a/41129231/149138
  - hyperpape 8y ago
    Cool find. I'd never actually realized that.
bradleyjg 8y ago
From the Rust link above there were these links to code for generating test patterns: https://github.com/notriddle/quickersort/blob/master/examples/perf_txt.rs#L63 https://github.com/notriddle/quickersort/blob/master/example... https://github.com/llvm-mirror/libcxx/blob/master/benchmarks/GenerateInput.hpp https://github.com/llvm-mirror/libcxx/blob/master/benchmarks... https://github.com/Morwenn/cpp-sort/blob/master/benchmarks/distributions.h https://github.com/Morwenn/cpp-sort/blob/master/benchmarks/d...
bjourne 8y ago
Probably more than you can shake a stick at: https://www.postgresql.org/message-id/CAEYLb_W%2B%2BUhrcWprzG9TyBVF7Sn-c1s9oLbABvAvPGdeP2DFSQ%40mail.gmail.com https://www.postgresql.org/message-id/CAEYLb_W%2B%2BUhrcWprz... :)
strainer 8y ago
I wrote a personal benchmark suite specifically to compare the Javascript port of Timsort to my own 'pet' Javascript sorting module 'Barsort.js' which was specialised to sorting Numbers, while Timsort also does strings quickly and takes custom comparators. I tested these distributions for arrays of 100 to 1000000 elements: descending ints ascending ints descending ints with maveric vals ascending ints with maveric vals equally distributed reals from -20 to 20 gaussian distribution -1 to 1 midspiked reals with duplicates -200 to 200 huge magnitude with gaps and duplicates and infinites equal-dist of ints 1 or 2 equal-dist of ints 1 2 3 equal-dist of ints 1 2 3 4 equal-dist of ints 1 2 3 4 5 Timsort seemed relatively a little slow with gaussian/normal and equal distributions, but still 10x faster or more than browsers native sort at the time. I was able to extend my pet sorting module to be quite competitive with Timsort's Javascript port. It was a captivating side project that I escaped from as soon as tests passed, its code not in a decent state, but is here - https://github.com/strainer/barsort https://github.com/strainer/barsort
justinclift 8y ago
> If you come up with a fast sorting algorithm how would you go about making a case it's faster than currently used ones on real world data? For analysing sorting algorithms - and related things which that leads into - there are established ways to determine their best, average, and worst case runtimes for input of a given size. If you're interested in learning this stuff, the video's here are useful and not math heavy: https://www.coursera.org/learn/algorithms-part1 https://www.coursera.org/learn/algorithms-part1 Technically it's explained using java. But it's mostly done using primitive data types (eg int, float, byte, ...). So it's very easy to follow along and copy the implementation, but translated to a different language (Go in my case, as I don't do java at all).

Are there benchmarks available for this kind of algorithm? If you come up with a fast sorting algorithm how would you go about making a case it's faster than currently used ones on real world data?

gleenn 8y ago

Well I think that ship has already sailed, Timsort is used in Java on Android and Python, so it's already seen massive adoption.

repsilat 8y ago

I'd hope people using it wouldn't have chosen it unless they had measured performance -- doubly so if the switched to it from something else. On the other hand, common third-party benchmarks may not be useful for measuring these sorts of improvements, which take advantage of common input distribution biases. "Real world workloads" is really too much of a simplification -- people sort all shapes and sizes of data. When JS engines started getting fast(er), every engine made their own preferred benchmark because they said existing ones didn't adequately show the real-world gains their engines were providing. We shouldn't be reflexively cynical about that. If they have made good-faith measurements, it is likely that old benchmarks were "unrepresentstive" in some way. Again, "real world benchmarking" is hard, and that applies just as much to yesterday's benchmarks as today's.

hyperpape 8y ago

You can go back and read the mailing list archives to see the benchmarks that were used by Python devs to decide on using Timsort: https://mail.python.org/pipermail/python-dev/2002-July/thread.html#26837 https://mail.python.org/pipermail/python-dev/2002-July/threa... You can also read Tim Peter's notes about the sort: https://bugs.python.org/file4451/timsort.txt https://bugs.python.org/file4451/timsort.txt That was back in 2002, so there's certainly been a lot of scrutiny since then. In particular, I've never actually read about Java sorting benchmarks, but there are tremendously sophisticated benchmarking tools/benchmarking experts in the Java world, so I imagine that it got a lot of analysis there.

BeeOnRope 8y ago
It's worth noting that Java doesnt exclusively use Timsort. Depeding on the data type and heuristics based mostly on the size of the input array, a simpler sort such as counting sort may be use. You can find a more detailed summary at: https://stackoverflow.com/a/41129231/149138 https://stackoverflow.com/a/41129231/149138
- hyperpape 8y ago
  Cool find. I'd never actually realized that.

bradleyjg 8y ago

From the Rust link above there were these links to code for generating test patterns: https://github.com/notriddle/quickersort/blob/master/examples/perf_txt.rs#L63 https://github.com/notriddle/quickersort/blob/master/example... https://github.com/llvm-mirror/libcxx/blob/master/benchmarks/GenerateInput.hpp https://github.com/llvm-mirror/libcxx/blob/master/benchmarks... https://github.com/Morwenn/cpp-sort/blob/master/benchmarks/distributions.h https://github.com/Morwenn/cpp-sort/blob/master/benchmarks/d...

bjourne 8y ago

Probably more than you can shake a stick at: https://www.postgresql.org/message-id/CAEYLb_W%2B%2BUhrcWprzG9TyBVF7Sn-c1s9oLbABvAvPGdeP2DFSQ%40mail.gmail.com https://www.postgresql.org/message-id/CAEYLb_W%2B%2BUhrcWprz... :)

strainer 8y ago

I wrote a personal benchmark suite specifically to compare the Javascript port of Timsort to my own 'pet' Javascript sorting module 'Barsort.js' which was specialised to sorting Numbers, while Timsort also does strings quickly and takes custom comparators. I tested these distributions for arrays of 100 to 1000000 elements: descending ints ascending ints descending ints with maveric vals ascending ints with maveric vals equally distributed reals from -20 to 20 gaussian distribution -1 to 1 midspiked reals with duplicates -200 to 200 huge magnitude with gaps and duplicates and infinites equal-dist of ints 1 or 2 equal-dist of ints 1 2 3 equal-dist of ints 1 2 3 4 equal-dist of ints 1 2 3 4 5 Timsort seemed relatively a little slow with gaussian/normal and equal distributions, but still 10x faster or more than browsers native sort at the time. I was able to extend my pet sorting module to be quite competitive with Timsort's Javascript port. It was a captivating side project that I escaped from as soon as tests passed, its code not in a decent state, but is here - https://github.com/strainer/barsort https://github.com/strainer/barsort

justinclift 8y ago

> If you come up with a fast sorting algorithm how would you go about making a case it's faster than currently used ones on real world data? For analysing sorting algorithms - and related things which that leads into - there are established ways to determine their best, average, and worst case runtimes for input of a given size. If you're interested in learning this stuff, the video's here are useful and not math heavy: https://www.coursera.org/learn/algorithms-part1 https://www.coursera.org/learn/algorithms-part1 Technically it's explained using java. But it's mostly done using primitive data types (eg int, float, byte, ...). So it's very easy to follow along and copy the implementation, but translated to a different language (Go in my case, as I don't do java at all).