81–90 of 104 posts
There's an even better branch-free (super scalar) sorting algorithm: "In-place Parallel Super Scalar Samplesort (IPS4o)" which we started using: https://github.com/SaschaWitt/ips4o https://arxiv.org/abs/1705.02257 As an example, to sort 10 million random longs on my computer it takes std::sort 766 ms (roughly in line with Andrei's numbers) and ips4o::sort takes 274 ms. [edit:formatting]
You might want to mention if are affiliated with the algorithm you are promoting. ipsofacto ~ ips4o
https://dlang.org/blog/2020/05/14/lomutos-comeback/ gives a 404 error. And archive.org ( http://web.archive.org/cdx/search/cdx?url=https://dlang.org/... ) is also getting nothing but 404s, so it's not a problem on my end. I'm not really sure what's wrong with this site, since other commenters seem not to have noticed a problem.
Alexandrescu's branch-free code in this article is a thing of beauty, in the same sort of rugged way that Stepanov's code is.
To anyone interested in a deeper treatment of quicksort and variants thereof, I can recommend Sebastian Wild's PhD thesis on that topic: https://kluedo.ub.uni-kl.de/frontdoor/deliver/index/docId/44...
Off topic: Is it common practice for a dissertation at a German university to be written in English?
Earlier quoted context omitted.
Indeed, AVX512 instructions can sort 16 int32 or well-behaved float values optimally, with no branches. It is a good final pass to any other algorithm.
You mean sorting within a vector register? Can you provide a link or something? I can't find info on this
Earlier quoted context omitted.
Putting things in a map or set is almost invariably slower, often much slower, than a smart sort. If performance doesn't matter, then go ahead. Most often sort performance doesn't matter, or anyway most of the time is spent elsewhere. People do use Python or Bash in production, without shame. But some of us work on problems where performance of the sort does matter.
Sure, it is slower, but my point is not that I sort by doing `Map.toList . map.fromList` but that I don't immediately turn the map back to a list . The sorting literature is optimizing a thing I don't need to to do.
Earlier quoted context omitted.
2x-3x improvement doesn't seem like much for something that runs in parallel.
The 274 ms is for the sequential version of the algorithm (on my i7-9750 laptop). On my office Xeon E5-2690 machine when using multiple threads the runtime decreases like this 840 ms for std::sort 372 ms for IPS4o sequentially 201 ms for 2 threads 104 ms for 4 threads 53 ms for 8 threads 33 ms for 16 threads
How does it behave with almost-sorted data?
Hoare partitioning can also be implemented in a branchless manner, my algorithm pdqsort does this: https://github.com/orlp/pdqsort
Thanks! I tried that too, but it's slower than Lomuto. Forgot to mention in the article.
That is very strange. I can not reproduce your results in C++, using your code.
On my machine (Threadripper 2950x, 64 bit Windows 10, GCC 10.1.0 from MSYS2 MinGW64) my algorithm performs best and your branchless version ends up slower than your branchy one:
$ g++ -std=c++17 -O3 -DNDEBUG -DLOMUTO lomuto.cpp && a 10000000
min_milliseconds=828.1250
median_milliseconds=890.6250
$ g++ -std=c++17 -O3 -DNDEBUG -DLOMUTO_BRANCHY lomuto.cpp && a 10000000
min_milliseconds=671.8750
median_milliseconds=671.8750
$ g++ -std=c++17 -O3 -DNDEBUG -DPDQSORT lomuto.cpp && a 10000000
min_milliseconds=343.7500
median_milliseconds=343.7500
$ g++ -std=c++17 -O3 -DNDEBUG -DLOMUTO lomuto.cpp && ./a.out 10000000
min_milliseconds=514.8051
median_milliseconds=536.1984
$ g++ -std=c++17 -O3 -DNDEBUG -DLOMUTO_BRANCHY lomuto.cpp && ./a.out 10000000
min_milliseconds=688.2471
median_milliseconds=698.9603
$ g++ -std=c++17 -O3 -DNDEBUG -DPDQSORT lomuto.cpp && ./a.out 10000000
min_milliseconds=340.1935
median_milliseconds=344.7432
I didn't change the benchmark, I only added pdqsort to yours, my full changes are the simple inclusion of 1 header and 3 lines of code: https://github.com/orlp/lomuto/commit/29381176f49e3588f6882c...
In order for any interested readers to reproduce, simply clone https://github.com/orlp/lomuto and run the above commands.
Earlier quoted context omitted.
Sure, it is slower, but my point is not that I sort by doing `Map.toList . map.fromList` but that I don't immediately turn the map back to a list . The sorting literature is optimizing a thing I don't need to to do.
Just because you’re not using it directly doesn’t mean that you’re not benefiting from those optimization in those layers you are depending on.
Earlier quoted context omitted.
The 274 ms is for the sequential version of the algorithm (on my i7-9750 laptop). On my office Xeon E5-2690 machine when using multiple threads the runtime decreases like this 840 ms for std::sort 372 ms for IPS4o sequentially 201 ms for 2 threads 104 ms for 4 threads 53 ms for 8 threads 33 ms for 16 threads
That's really interesting! How does it behave with almost-sorted data?
There's also some logic to handle the case where there are a lot of equal elements which also results in faster performance than the completely random case.