3 ms·
Got the benchmarks working with a hardcoded 4-byte int pdqsort. pdqsort is of course faster, but this doesn't tell us anything about how good fluxsort really is
by mlochbaum 5y ago
Got the benchmarks working with a hardcoded 4-byte int pdqsort. pdqsort is of course faster, but this doesn't tell us anything about how good fluxsort really is because it doesn't inline the comparison (I've removed __attribute__ ((noinline)) and comparisons++ as bench.c suggests, which improves the speed but doesn't inline it).
| Name | Items | Type | Best | Average | Loops | Samples | Distribution |
| --------- | -------- | ---- | -------- | -------- | --------- | ------- | ---------------- |
| qsort | 100000 | 32 | 0.013530 | 0.013901 | 1 | 10 | random order |
| fluxsort | 100000 | 32 | 0.004837 | 0.005009 | 1 | 10 | random order |
| pdqsort | 100000 | 32 | 0.003661 | 0.003745 | 1 | 10 | random order |
Your graph doesn't show how fast pdqsort orders 4-byte integers. It shows how fast it orders them when required to use a comparison function, which is an arbitrary restriction and not what pdqsort is designed for.
- scandum 5y agoThe graph is with //#define cmp(a,b) ((a) > (b)) in quadsort.h uncommented. Looking forward to your next spin.
- mlochbaum 5y agoYou're right, with that setting fluxsort beats pdqsort slightly for either 1e5 or 1e6 random 4-byte ints. I'm really sorry; I shouldn't have assumed I knew what your benchmark looked like. Although I guess now I'm even more confused about why there are no pdqsort benchmarks in the repository? Beating it is really impressive! I'll be running my own timings, but do you know where the improvement comes from? Is the base case faster than insertion sort, is the partition faster, or both? I wasn't expecting a stable partition to beat an unstable one because it does twice as much data movement, but it wouldn't be the first time an algorithm using more memory beats one using less.
- scandum 5y agoMain reasons for not benching against pdqsort: 1. stability 2. worse performance on long doubles, and I don't know why 3. A variety of hard to explain performance differences. 4. pdqsort does better on generic data, which can be very important. So it's tricky to present a fair benchmark when two sorts behave very differently. As to performance advantages of fluxsort: 1. It has a faster insertion sort. 2. Branchless pseudomedian of 15 gives an advantage. 3. Partial loop unrolling with: while (ptx + 8 < pte) 4. Data movement should be nearly identical, if not better, with the recursive calls through the ptx pointer. In the optimal case the memcpy only triggers when the partition shrinks below 24 elements, and in half of those cases the partition will already be in main memory. So on random you could expect n / 2 extra data movements on top of ~ n log n moves.