voracious_radix_sort 0.1.0

Very fast radix sort for all Rust primitive types and struct (except Array and tuple)
Documentation

Voracious sort

Dear visitor, welcome on our GitHub.

Introduction

This project's purpose is to have a Rust implementation of a state of the art radix sort.

We started with a single thread radix sort, but the goal is also to have a multithread radix sort.

This crate should be easy to use and the sort should be able to sort almost "everything". Radix sort is criticized because people think it can only sort unsigned integers. This project proves this wrong, Voracious sort can sort all Rust primitive types (except String, Tuple and Array for now) and custom struct. It is way faster than Rust standard sort and Rust unstable sort on most of the types and data distribution.

Because of Rust Orphan Rule, we chose not to support tuple sorting. You can use Struct instead.

You will find here:

  • Version
  • License
  • A word about the sort’s name
  • The documentation on how to use this sort,
  • Radix sort: basic notions,
  • Performance analysis,
  • For developers and researchers
  • References we used for this project,
  • Future work,

Version

Last version tested/used:

  • Rustc: 1.41.1 stable
  • Rustfmt: 1.4.11 stable
  • Cargo: 1.41.0 stable
  • Clippy: 0.0.212

License

This project is under the MIT license.

See the license file.

A word about the sort's name

When I asked what name to give to this sort, a colleague of mine proposed Voracious sort (Variation Of Radixsort Axelle Cleverly Imagined Over Uncountable Sessions). The name was fun so I took it. It is true that I spent uncountable sessions to code this project.

You can also think about it like someone very voracious of radish...

Documentation: How to use it ?

Since it is alreay explained in the crate documentation, we just provide the link:

And we assume that you know how to code in Rust...

Other implementation examples:

Radix sort: basic notions

Radix sort is a non-comparative sort. It requires a key and uses the binary representation to sort the input instead of a comparative function. Amongst radix sorts there are two sub groups:

  • LSD: Least Significant Digit; (or LSB: Least Significant Bit)
  • MSD: Most Significant Digit; (or MSB: Most Significant Bit)

Their differences are based on how the algorithm iterates through the binary representation.

Sorts can be stable or unstable; in general, LSD are stable whereas MSD tend to be unstable. Please note that the term stable can be ambiguous in the computer science field, we are refering to this one wikipedia page on sorting algorithm stability.

Sorts can be in place or out of place. A sort is said to be in place if it does not require more memory than the initial memory used by the input. A sort is said out of place if it does require more memory (usually, in order of O(n)). LSD sorts are out of place, and MSD sorts can be either one.

Diversion is something we do because radix sorts perform badly on small inputs. In order to avoid this loss of performance, a radix sort fallbacks on another sort when the input becomes too small. Insertion sort is very good for input's length less or equal to 32 elements. Diversion can occur at the beginning of the algorithm, we check the input's length and we choose the sort accordingly, or we trigger it at the end of recursive calls when the remaining input is small enough.

The radix itself, is the number of bits the sorting algorithm take into account per pass. The radix of choice is often 8, however, it may vary depending on your use case.

In a radix sort, you use an histogram which has a size of 2.pow(radix). Given a level[1] and a radix, we can compute the histogram. This histogram gives all the bucket sizes and thus, the algorithm knows where to move each elements. For a detail example, I let the reader read the Wikipedia page on radix sort.

[1]: If a radix of 8 is choosen, level 1 is the first 8 bits, level 2 is the next 8 following bits, and so on until there is no more bit to handle.

Performances

CAUTION: Performance tests have been done on a previous version of the code.

See raw benchmarck results in the results folder:

For each sort, 3 columns:

  • 1st column: time un micro second
  • 2nd column: standard deviation (if more than 1 iteration) in nano second
  • 3rd column: time per item in nano second

For developers and researchers

  • Voracious sort is a MSD radix sort. It is an improvement of the Ska sort and it uses the Verge sort pre-processing heuristic. Depending on the type and the input size, another sort might be choosen (LSD sort, Counting sort, etc...). The purpose is to implement a multithread radix sort (see Regions sort and the article).

  • DLSD (Diverting LSD radix sort) is a simpler version of the DFR sort with a different diversion and a variable radix (see article).

  • All sorts fallback on the PDQ sort (Rust Unstable sort) for very small inputs.

References

Future work

  • Add multithread sort.
  • Improve k-way-merge algorithm.
  • Add more generators (for tests).
  • Add a sort for String.