3 ms·

Fluxsort: A stable adaptive partitioning comparison sort

68 points by signa11 5y ago

gigatexal 5y ago
Hmm I kinda want to create a Python package for this.
mettamage 5y ago
Perhaps others think differently about this but after all the interview prep I have done, I can appreciate posts like this a lot. It seems I have gained a new appreciation of a topic! Which is something I am grateful for :)
Blikkentrekker 5y ago
> Fluxsort starts out with an analyzer that detects fully sorted arrays and sorts reverse order arrays using n comparisons. It also obtains a measure of presortedness and switches to quadsort if the array is less than 25% random. This makes me wonder? is it worth it to do a neural a.i. sort by simply training it? I assume it would be hard to prove that the resulting a.i. is actually infallible and always produces a sorted output, but perhaps it could for practical measures sort faster than most current algorithms.
- stingraycharles 5y ago
  You mean using a neural network for sorting? I think it will be very expensive, as sorting algorithms usually take low level performance optimizations such as cache locality into consideration, and neural networks are a poor fit for this type of thing.
  - HelloNurse 5y ago
    The currently en vogue deep and large neural networks are not only designed to have an affordable but significant evaluation cost (probably not competitive with really cheap techniques, like the partitioning and medians of this Fluxsort) but also to justify this cost with the recognition of fairly subtle patterns: wasted on rough and general worst-case guarantees, positively dangerous with arbitrarily crafted inputs.
    - stingraycharles 5y ago
      Do you have an example of a sorting algorithm that uses a neural network that’s on par with other sorting algorithms in terms of performance? It just seems so counter-intuitive to me that neural networks are an efficient way to handle this, but I would be happy if proven wrong.
- somethingAlex 5y ago
  There's no neural network you could train using supervised learning to solve sorting in the general case. To train a neural network, the training set and test set need to come from a common probability distribution but the inputs of sorting algorithms can be random. There's no relation between what you could possibly train your network on and what you'd ask it to do. Put another way - the input and output of your model would have zero correlation. There's nothing to train the model to pick up on. Interesting related work: Graves[0] trained a "neural Turing machine" to encode instructions for a basic sorting algorithm. [0] https://arxiv.org/abs/1410.5401 https://arxiv.org/abs/1410.5401
mlochbaum 5y ago
This is BlockQuicksort with stable partitioning, pumped up with selective benchmarks (if I sound irritated about this, it's because I've just called out the author[0] on this exact issue). I understand that worse performance should be expected for a stable sort, but what possible reason is there to leave out benchmarks against the most closely related algorithm? Worse, a stable version of BlockQuicksort is pointless, which is to say that it is actually impossible for there to be a practical use case for Fluxsort. The branchless partitioning technique is relevant only if comparison doesn't depend on branching, which means the input array needs to consist machine-native types, and in fact Fluxsort limits itself to integers and long double. On these inputs stability isn't an observable property! The result of Fluxsort will be indistinguishable from that of any other quicksort (okay, I guess it will keep negative and positive zeros in the original order for floats, but an integer-based comparison could also accomplish this). So all you get is a slower sort that uses more memory. There are use cases for stable partitioning, such as sort-by or arg-sort, but as written Fluxsort can't do these. The statistical method to decide whether to use quicksort or Quadsort—checking the ratio of comparisons between adjacent pairs of elements that are smaller versus greater—is really interesting. It applies to the mergesort versus quicksort problem in general. The use of the ptx pointer is definitely not novel and I think it's a stretch to even describe it as a brain-twister. It's the obvious way to do branchless stable partitioning. This is good work! It's well-written and well-explained, and clearly points in the direction of practical applications. However, it's presented in a way that suggests that it's a good drop-in sorting algorithm, when instead it's more of a research effort. Beware! [0] https://news.ycombinator.com/item?id=27793636 https://news.ycombinator.com/item?id=27793636
- scandum 5y ago
  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/868645661871046696/unknown.png 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.

68 points by signa11 5y ago

Hmm I kinda want to create a Python package for this.

Perhaps others think differently about this but after all the interview prep I have done, I can appreciate posts like this a lot. It seems I have gained a new appreciation of a topic! Which is something I am grateful for :)

Blikkentrekker 5y ago

> Fluxsort starts out with an analyzer that detects fully sorted arrays and sorts reverse order arrays using n comparisons. It also obtains a measure of presortedness and switches to quadsort if the array is less than 25% random. This makes me wonder? is it worth it to do a neural a.i. sort by simply training it? I assume it would be hard to prove that the resulting a.i. is actually infallible and always produces a sorted output, but perhaps it could for practical measures sort faster than most current algorithms.

stingraycharles 5y ago
You mean using a neural network for sorting? I think it will be very expensive, as sorting algorithms usually take low level performance optimizations such as cache locality into consideration, and neural networks are a poor fit for this type of thing.
- HelloNurse 5y ago
  The currently en vogue deep and large neural networks are not only designed to have an affordable but significant evaluation cost (probably not competitive with really cheap techniques, like the partitioning and medians of this Fluxsort) but also to justify this cost with the recognition of fairly subtle patterns: wasted on rough and general worst-case guarantees, positively dangerous with arbitrarily crafted inputs.
  - stingraycharles 5y ago
    Do you have an example of a sorting algorithm that uses a neural network that’s on par with other sorting algorithms in terms of performance? It just seems so counter-intuitive to me that neural networks are an efficient way to handle this, but I would be happy if proven wrong.
somethingAlex 5y ago
There's no neural network you could train using supervised learning to solve sorting in the general case. To train a neural network, the training set and test set need to come from a common probability distribution but the inputs of sorting algorithms can be random. There's no relation between what you could possibly train your network on and what you'd ask it to do. Put another way - the input and output of your model would have zero correlation. There's nothing to train the model to pick up on. Interesting related work: Graves[0] trained a "neural Turing machine" to encode instructions for a basic sorting algorithm. [0] https://arxiv.org/abs/1410.5401 https://arxiv.org/abs/1410.5401

mlochbaum 5y ago

This is BlockQuicksort with stable partitioning, pumped up with selective benchmarks (if I sound irritated about this, it's because I've just called out the author[0] on this exact issue). I understand that worse performance should be expected for a stable sort, but what possible reason is there to leave out benchmarks against the most closely related algorithm? Worse, a stable version of BlockQuicksort is pointless, which is to say that it is actually impossible for there to be a practical use case for Fluxsort. The branchless partitioning technique is relevant only if comparison doesn't depend on branching, which means the input array needs to consist machine-native types, and in fact Fluxsort limits itself to integers and long double. On these inputs stability isn't an observable property! The result of Fluxsort will be indistinguishable from that of any other quicksort (okay, I guess it will keep negative and positive zeros in the original order for floats, but an integer-based comparison could also accomplish this). So all you get is a slower sort that uses more memory. There are use cases for stable partitioning, such as sort-by or arg-sort, but as written Fluxsort can't do these. The statistical method to decide whether to use quicksort or Quadsort—checking the ratio of comparisons between adjacent pairs of elements that are smaller versus greater—is really interesting. It applies to the mergesort versus quicksort problem in general. The use of the ptx pointer is definitely not novel and I think it's a stretch to even describe it as a brain-twister. It's the obvious way to do branchless stable partitioning. This is good work! It's well-written and well-explained, and clearly points in the direction of practical applications. However, it's presented in a way that suggests that it's a good drop-in sorting algorithm, when instead it's more of a research effort. Beware! [0] https://news.ycombinator.com/item?id=27793636 https://news.ycombinator.com/item?id=27793636

scandum 5y ago
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/868645661871046696/unknown.png 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.