Hacker News Reader

Comment by scandum | Hacker News Reader

I get the impression you wrote your response rather hastily.

Here's a bench of fluxsort vs pdqsort on strings:

    |      Name |    Items | Type |     Best |  Average |  Compares | Samples |     Distribution |
    | --------- | -------- | ---- | -------- | -------- | --------- | ------- | ---------------- |
    |  fluxsort |   100000 |   64 | 0.011804 | 0.012044 |   2003293 |     100 |    random string |
    |   pdqsort |   100000 |   64 | 0.012423 | 0.012512 |   1859192 |     100 |    random string |

If you can sort strings you can sort tables, where stability matters.

Here's a graph of relative performance on 100K 32 bit integers.

https://media.discordapp.net/attachments/737457171377160203/...

As for the ptx pointer's use, I'm not aware of a prior implementation.

As for selective benchmarking, that's a selective accusation.

View on HN

Gah, I did misunderstand some things. The picture is now worse than I realized! EDIT: and yet also better; see https://news.ycombinator.com/item?id=27951017 . It's hard to get it working right but this is a really fast algorithm.

fluxsort takes a function pointer and has no way to inline it. The fluxsort.c is included from fluxsort.h (this is not standard style by the way; template files should have a .h suffix), so the compiler might choose to inline it, and the benchmarks use noinline on the comparison functions to avoid this.

BlockQuicksort makes no sense without inlined comparisons. Yes, pdqsort allows a comparison function in order to be a general-purpose sort, but this isn't the case that it targets.

Are these benchmarks run with inline comparisons? Seems pretty hard to get bench.c to inline anything since test_sort takes a comparison function as input (though I'm working on it).

My biggest complaint about all scandum's sorting algorithms is that it doesn't support guaranteed inlined comparisons. Without this feature, the result depends on the compiler behavior, making the results hard to interpret. This point has been raised many times at reddit/hacker news but the dev is strong minded.

You can uncomment

    //#define cmp(a,b) (*(a) > *(b))

in quadsort.h for primitive inline comparisons.

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.

The graph is with //#define cmp(a,b) ((a) > (b)) in quadsort.h uncommented.

Looking forward to your next spin.

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

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

I think I mistook the README's comment about ptx as being about the branchless partition logic when it's talking about the overall recursive structure (i.e. which arguments are passed to flux_partition calls). That could be new although I kind of doubt it. The way it uses the two buffers is fairly similar to what I've seen called a "ping-pong merge".

Reply on news.ycombinator.com