rust-lang / rust-lang/rust

Faster Stdlib sort for short slices?

Open
#139,133 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

C-feature-request T-libs
Dominant language
Rust
Stars
119k
Forks
16.1k
PR merge metrics
PR metrics pending

Description

Where I need to sort many (like 100_000) times a small number of numbers (here small means 0 ..= 12), the built-in sort has shown me to be slower than a basic Insertion Sort implementation like this (this needs T to be Copy for simplicity):

fn insertion_sort<T: Copy + PartialOrd>(data: &mut [T]) -> &mut [T] {
    for i in 1 .. data.len() {
        let aux = data[i];
        let mut j = i;
        while j > 0 && data[j - 1] > aux {
            data[j] = data[j - 1];
            j -= 1;
        }
        data[j] = aux;
    }
    data
}

So perhaps the Rust stdlib sort(s) could call code like this when the input is small (I think an extra lenght test isn't going to cause damages).

(I've also noticed that the built-in un unstable sort of u32s adds about 5.5 kbytes to my binary, while this little Insertion Sort adds very little to the binary. I think this "problem" can't be solved, unless you want to add something like a small_sort() to the stdlib that only contains a basic algorithm like that).

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by benchmarking the built-in sort and the provided insertion_sort implementation across short slices, including the u32 binary-size observation. Read the standard library sort implementation and its existing benchmarks to identify where a small-input path could fit. Done means a measured recommendation or an accepted change with benchmark and binary-size evidence.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
performance
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.