51–60 of 104 posts
I'm not sure I've ever sorted an array or list. Rather I put things into sets or maps or built in index---I always wanted to access things later, or have an on-line data structure (which a sorted flat thing is not). This whole field is a waste of time, and anachronism from when the master copy was paper/pre-computer and computers were just doing the analytics.
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]
Notice that this is on random longs . Of course branch misprediction and memory bandwidth is going to crush you for a branchy sort... you'll be wrong like half the time, and the comparisons and swapping are trivial! Real world data isn't random, so I'd expect branch predictors to do much better with recognizing patterns. And your sorting isn't going to be as simple as sorting integers according to their values all th…
Sorting is the case study but not the insight. I think the cool/surprising part of the article is that doing more work can be faster... Even more memory work (which per conventional wisdom is not trivial!)
Yeah, I figured heap sort should be the standard because it has a worst case O(n*log(n)) complexity. But it does tend to do more swaps (a smarter implementation can avoid many writes), and the memory access is very cache-unfriendly. In practice it's just not used.
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.
Not necessarily. A branch-free algorithm can totally have a data dependency from the previous iteration of the loop to the next, making it impossible to vectorize.
That's true, although there are sometimes workarounds for that by modifying the algorithm to iterate over a small groups where there is still a data-dependency between iterations, but not within each group, allowing one to use SIMD. e.g. instead of delta compression over an array of integers where you subtract each integer from the prior one, you can subtract each group from the prior one with only a small loss of co…
Edit: I can't seem to locate that 4-way swapping algorithm, I swear it was posted to HN in the last year... somebody halp!
Earlier quoted context omitted.
This sort of vectorised pseudo branching is often used in SIMD algorithms
Yes... and the transformations are often non-trivial (especially when considering the possibility of out-of-bounds elements, which can't just safely be multiplied by zero--they might be a NaN, or on the edge of a page). It would be nice if there was a tool (or compiler option!) that could convert my branchy code into an "identical" (assuming floating-point associativity, etc.) branchless version.
1. https://eigen.tuxfamily.org/dox/group__TutorialArrayClass.ht...
The operations to count, nowadays, are not swaps or comparisons, which are very cheap, but instead pipeline stalls, which are very, very expensive.
It is easy to better-than-double the speed of vanilla quicksort with a three-line change in the partition step.
I’ve read that some vector instruction sets use masking instructions to avoid branching. You execute both arms of the conditional and discard the unwanted computation, which can be cheaper than an X% chance of a branch misprediction. Should CPUs include more masking instructions for regular, non-vectorized code as well?
32-bit ARM assembly language provided conditional execution for most instructions. This was dropped in the 64-bit instruction set. ( https://en.wikipedia.org/wiki/Predication_(computer_architec... , https://en.wikipedia.org/wiki/ARM_architecture#64-bit ) I imagine the architects had a clear picture of the advantages and disadvantages, and made a very well-informed decision. I guess that part of the reason might have…
Gcc will not under any circumstances produce two cmov instructions in a basic block, so that is your only alternative without dropping to asm. Clang is happy to produce two adjacent cmov instructions. Usually your ALUs are not otherwise so engaged as to make the number of operations involved costly.
I'm not sure I've ever sorted an array or list. Rather I put things into sets or maps or built in index---I always wanted to access things later, or have an on-line data structure (which a sorted flat thing is not). This whole field is a waste of time, and anachronism from when the master copy was paper/pre-computer and computers were just doing the analytics.
But some of us work on problems where performance of the sort does matter.
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]
2x-3x improvement doesn't seem like much for something that runs in parallel.
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