パターン撃退クイックソートで配列を並び替える

set -euo pipefail

WORKDIR="$(mktemp -d)"
trap 'rm -rf "$WORKDIR"' EXIT

cat > "$WORKDIR/Dockerfile" <<'EOF'
FROM rust:1.95.0

WORKDIR /app

RUN mkdir -p src

RUN cat > Cargo.toml <<'CARGO'
[package]
name = "rust-benchmark"
version = "0.1.0"
edition = "2021"

[profile.release]
lto = true
codegen-units = 1
panic = "abort"
CARGO

RUN cat > src/main.rs <<'RUST'
use std::{
    env,
    process::Command,
    time::{Duration, Instant},
};
const MIN_POWER: u32 = 8;
const MAX_POWER: u32 = 18;
const RUNS: usize = 8192;
fn insertion_sort(a: &mut [usize]) {
    for i in 1..a.len() {
        let mut j = i;
        while j > 0 && a[j - 1] > a[j] {
            a.swap(j - 1, j);
            j -= 1;
        }
    }
}

fn sift_down(a: &mut [usize], mut root: usize, end: usize) {
    loop {
        let child = root * 2 + 1;
        if child > end {
            break;
        }
        let mut swap_idx = child;
        if child < end && a[child] < a[child + 1] {
            swap_idx = child + 1;
        }
        if a[root] >= a[swap_idx] {
            break;
        }
        a.swap(root, swap_idx);
        root = swap_idx;
    }
}

fn heap_sort(a: &mut [usize]) {
    if a.len() <= 1 {
        return;
    }
    for start in (0..a.len() / 2).rev() {
        sift_down(a, start, a.len() - 1);
    }
    for end in (1..a.len()).rev() {
        a.swap(0, end);
        sift_down(a, 0, end - 1);
    }
}



const INSERTION_SORT_THRESHOLD: usize = 24;
const NINTHER_THRESHOLD: usize = 128;
const PARTIAL_INSERTION_SORT_LIMIT: usize = 8;

fn floor_log2(n: usize) -> usize {
    usize::BITS as usize - n.leading_zeros() as usize - 1
}

fn sort2(a: &mut [usize], i: usize, j: usize) {
    if a[j] < a[i] {
        a.swap(i, j);
    }
}

fn sort3(a: &mut [usize], i: usize, j: usize, k: usize) {
    sort2(a, i, j);
    sort2(a, j, k);
    sort2(a, i, j);
}

fn partial_insertion_sort_range(a: &mut [usize], lo: usize, hi: usize) -> bool {
    if hi <= lo {
        return true;
    }
    let mut limit = 0usize;
    for i in (lo + 1)..=hi {
        if a[i] < a[i - 1] {
            let tmp = a[i];
            let mut j = i;
            loop {
                a[j] = a[j - 1];
                j -= 1;
                if j == lo || !(tmp < a[j - 1]) {
                    break;
                }
            }
            a[j] = tmp;
            limit += i - j;
            if limit > PARTIAL_INSERTION_SORT_LIMIT {
                return false;
            }
        }
    }
    true
}

/// Partition `[lo, hi]` around pivot at `lo`. Equals go to the right.
/// Returns `(pivot_pos, already_partitioned)`.
fn partition_right_range(a: &mut [usize], lo: usize, hi: usize) -> (usize, bool) {
    let pivot = a[lo];
    let mut first = lo;
    let mut last = hi + 1;

    loop {
        first += 1;
        if !(a[first] < pivot) {
            break;
        }
    }

    if first - 1 == lo {
        loop {
            if first >= last {
                break;
            }
            last -= 1;
            if a[last] < pivot {
                break;
            }
        }
    } else {
        loop {
            last -= 1;
            if a[last] < pivot {
                break;
            }
        }
    }

    let already_partitioned = first >= last;
    while first < last {
        a.swap(first, last);
        loop {
            first += 1;
            if !(a[first] < pivot) {
                break;
            }
        }
        loop {
            last -= 1;
            if a[last] < pivot {
                break;
            }
        }
    }

    let pivot_pos = first - 1;
    a[lo] = a[pivot_pos];
    a[pivot_pos] = pivot;
    (pivot_pos, already_partitioned)
}

/// Partition `[lo, hi]` around pivot at `lo`. Equals go to the left.
fn partition_left_range(a: &mut [usize], lo: usize, hi: usize) -> usize {
    let pivot = a[lo];
    let mut first = lo;
    let mut last = hi + 1;

    loop {
        last -= 1;
        if !(pivot < a[last]) {
            break;
        }
    }

    if last + 1 == hi + 1 {
        loop {
            if first >= last {
                break;
            }
            first += 1;
            if pivot < a[first] {
                break;
            }
        }
    } else {
        loop {
            first += 1;
            if pivot < a[first] {
                break;
            }
        }
    }

    while first < last {
        a.swap(first, last);
        loop {
            last -= 1;
            if !(pivot < a[last]) {
                break;
            }
        }
        loop {
            first += 1;
            if pivot < a[first] {
                break;
            }
        }
    }

    a[lo] = a[last];
    a[last] = pivot;
    last
}

fn pattern_defeating_quick_sort_loop(
    a: &mut [usize],
    mut lo: usize,
    hi: usize,
    mut bad_allowed: usize,
    mut leftmost: bool,
) {
    while lo <= hi {
        let size = hi - lo + 1;
        if size < INSERTION_SORT_THRESHOLD {
            insertion_sort(&mut a[lo..=hi]);
            return;
        }

        let s2 = size / 2;
        if size > NINTHER_THRESHOLD {
            sort3(a, lo, lo + s2, hi);
            sort3(a, lo + 1, lo + (s2 - 1), hi - 1);
            sort3(a, lo + 2, lo + (s2 + 1), hi - 2);
            sort3(a, lo + (s2 - 1), lo + s2, lo + (s2 + 1));
            a.swap(lo, lo + s2);
        } else {
            sort3(a, lo + s2, lo, hi);
        }

        if !leftmost && !(a[lo - 1] < a[lo]) {
            lo = partition_left_range(a, lo, hi) + 1;
            if lo > hi {
                return;
            }
            continue;
        }

        let (pivot_pos, already_partitioned) = partition_right_range(a, lo, hi);
        let l_size = pivot_pos - lo;
        let r_size = hi - pivot_pos;
        let highly_unbalanced = l_size < size / 8 || r_size < size / 8;

        if highly_unbalanced {
            if bad_allowed == 0 {
                heap_sort(&mut a[lo..=hi]);
                return;
            }
            bad_allowed -= 1;

            if l_size >= INSERTION_SORT_THRESHOLD {
                a.swap(lo, lo + l_size / 4);
                a.swap(pivot_pos - 1, pivot_pos - l_size / 4);
                if l_size > NINTHER_THRESHOLD {
                    a.swap(lo + 1, lo + (l_size / 4 + 1));
                    a.swap(lo + 2, lo + (l_size / 4 + 2));
                    a.swap(pivot_pos - 2, pivot_pos - (l_size / 4 + 1));
                    a.swap(pivot_pos - 3, pivot_pos - (l_size / 4 + 2));
                }
            }

            if r_size >= INSERTION_SORT_THRESHOLD {
                a.swap(pivot_pos + 1, pivot_pos + (1 + r_size / 4));
                a.swap(hi, hi + 1 - r_size / 4);
                if r_size > NINTHER_THRESHOLD {
                    a.swap(pivot_pos + 2, pivot_pos + (2 + r_size / 4));
                    a.swap(pivot_pos + 3, pivot_pos + (3 + r_size / 4));
                    a.swap(hi - 1, hi - (r_size / 4));
                    a.swap(hi - 2, hi - (1 + r_size / 4));
                }
            }
        } else if already_partitioned
            && (pivot_pos == lo || partial_insertion_sort_range(a, lo, pivot_pos - 1))
            && (pivot_pos >= hi || partial_insertion_sort_range(a, pivot_pos + 1, hi))
        {
            return;
        }

        if pivot_pos > lo {
            pattern_defeating_quick_sort_loop(a, lo, pivot_pos - 1, bad_allowed, leftmost);
        }
        lo = pivot_pos + 1;
        leftmost = false;
        if lo > hi {
            return;
        }
    }
}

fn pattern_defeating_quick_sort(a: &mut [usize]) {
    if a.len() <= 1 {
        return;
    }
    let bad_allowed = floor_log2(a.len());
    pattern_defeating_quick_sort_loop(a, 0, a.len() - 1, bad_allowed, true);
}


fn benchmark_sort(array: &mut [usize]) {

    pattern_defeating_quick_sort(array);

}

fn is_non_decreasing(a: &[usize]) -> bool {
    a.windows(2).all(|w| w[0] <= w[1])
}

fn same_multiset(a: &[usize], b: &[usize]) -> bool {
    if a.len() != b.len() {
        return false;
    }

    let mut left = a.to_vec();
    let mut right = b.to_vec();
    left.sort_unstable();
    right.sort_unstable();
    left == right
}

fn check_correctness_case(label: &str, mut input: Vec<usize>) {
    let original = input.clone();

    benchmark_sort(&mut input);

    if !is_non_decreasing(&input) {
        panic!("correctness case {}: output is not sorted", label);
    }

    if !same_multiset(&input, &original) {
        panic!("correctness case {}: elements were lost or added", label);
    }
}

fn few_unique_values(size: usize, unique: usize, seed: u64) -> Vec<usize> {
    let mut state = seed;

    (0..size)
        .map(|_| {
            state ^= state << 13;
            state ^= state >> 7;
            state ^= state << 17;
            (state as usize % unique) + 1
        })
        .collect()
}

fn run_correctness_checks() {
    check_correctness_case("empty", vec![]);
    check_correctness_case("single", vec![42]);
    check_correctness_case("duplicates", vec![3, 1, 3, 2, 1, 2]);
    check_correctness_case("sorted", vec![1, 2, 3, 4, 5]);
    check_correctness_case("reverse", vec![5, 4, 3, 2, 1]);
    check_correctness_case("all_equal", vec![7, 7, 7, 7]);
    check_correctness_case("skewed_range", vec![1_000_000, 2, 1_000_001, 1, 999_999]);
    // Static-buffer Grail skips the in-buffer build when key collection is sparse
    // (ideal_buffer = false). Exercising that path catches regressions in buffer gating.
    check_correctness_case(
        "few_keys_len16",
        vec![2, 2, 2, 2, 2, 2, 2, 2, 4, 3, 1, 2, 3, 4, 1, 4],
    );
    for seed in 0..32 {
        check_correctness_case(
            &format!("few_keys_len32_seed_{seed}"),
            few_unique_values(32, 4, seed),
        );
    }
}


fn shuffled(size: usize, seed: u64) -> Vec<usize> {
    let mut v: Vec<usize> = (1..=size).collect();

    let mut state = seed;

    for i in (1..size).rev() {
        state ^= state << 13;
        state ^= state >> 7;
        state ^= state << 17;

        let j = (state as usize) % (i + 1);

        v.swap(i, j);
    }

    v
}

fn memory_usage_kb() -> usize {
    // VmHWM (peak RSS, KiB). Reported memory subtracts a per-size baseline that only
    // holds the input array, so the table reflects auxiliary space during sorting.
    let contents = std::fs::read_to_string("/proc/self/status")
        .unwrap_or_default();

    for line in contents.lines() {
        if let Some(rest) = line.strip_prefix("VmHWM:") {
            let kb = rest
                .split_whitespace()
                .next()
                .unwrap_or("0")
                .parse::<usize>()
                .unwrap_or(0);

            return kb;
        }
    }

    0
}

fn micros(d: Duration) -> u128 {
    d.as_micros()
}

fn input_array(size: usize, seed: u64) -> Vec<usize> {
    shuffled(size, seed)
}

fn run_baseline(size: usize) -> usize {
    let _hold = input_array(size, 1);
    memory_usage_kb()
}

fn run_once(size: usize, seed: usize) -> (u128, usize) {
    let mut array = input_array(size, seed as u64);

    let start = Instant::now();

    benchmark_sort(&mut array);

    let elapsed = start.elapsed();
    let mem = memory_usage_kb();

    let expected: Vec<usize> = (1..=size).collect();
    if array != expected {
        panic!(
            "sort failed with seed {} for size {}",
            seed,
            size
        );
    }

    (micros(elapsed), mem)
}

fn run_baseline_child(args: &[String]) {
    let size = args[2].parse::<usize>().expect("invalid size");
    let mem = run_baseline(size);
    println!("{}", mem);
}

fn run_child(args: &[String]) {
    let size = args[2].parse::<usize>().expect("invalid size");
    let seed = args[3].parse::<usize>().expect("invalid seed");
    let (elapsed_us, mem) = run_once(size, seed);
    println!("{} {}", elapsed_us, mem);
}

fn main() {
    let args: Vec<String> = env::args().collect();
    if args.get(1).is_some_and(|arg| arg == "--baseline-once") {
        run_baseline_child(&args);
        return;
    }
    if args.get(1).is_some_and(|arg| arg == "--run-once") {
        run_child(&args);
        return;
    }

    run_correctness_checks();

    println!(
        "| {:>10} | {:>15} | {:>15} | {:>15} | {:>15} |",
        "Size",
        "Average time",
        "Maximum time",
        "Average memory",
        "Maximum memory"
    );

    println!(
        "|{:-<11}:|{:-<16}:|{:-<16}:|{:-<16}:|{:-<16}:|",
        "",
        "",
        "",
        "",
        ""
    );

    for power in MIN_POWER..=MAX_POWER {
        let size = 1usize << power;

        let baseline_output = Command::new(env::current_exe().expect("failed to find current executable"))
            .arg("--baseline-once")
            .arg(size.to_string())
            .output()
            .expect("failed to run benchmark baseline process");

        if !baseline_output.status.success() {
            panic!(
                "benchmark baseline process failed: {}",
                String::from_utf8_lossy(&baseline_output.stderr)
            );
        }

        let baseline_stdout = String::from_utf8(baseline_output.stdout)
            .expect("baseline process returned non-UTF-8 output");
        let baseline_mem = baseline_stdout
            .split_whitespace()
            .next()
            .expect("missing baseline memory usage")
            .parse::<usize>()
            .expect("invalid baseline memory usage");

        let mut total_time: u128 = 0;
        let mut max_time: u128 = 0;

        let mut total_mem: usize = 0;
        let mut max_mem: usize = 0;

        for seed in 1..=RUNS {
            let output = Command::new(env::current_exe().expect("failed to find current executable"))
                .arg("--run-once")
                .arg(size.to_string())
                .arg(seed.to_string())
                .output()
                .expect("failed to run benchmark child process");

            if !output.status.success() {
                panic!(
                    "benchmark child process failed: {}",
                    String::from_utf8_lossy(&output.stderr)
                );
            }

            let stdout = String::from_utf8(output.stdout)
                .expect("child process returned non-UTF-8 output");
            let mut fields = stdout.split_whitespace();
            let elapsed_us = fields
                .next()
                .expect("missing elapsed time")
                .parse::<u128>()
                .expect("invalid elapsed time");
            let mem = fields
                .next()
                .expect("missing memory usage")
                .parse::<usize>()
                .expect("invalid memory usage");

            total_time += elapsed_us;

            if elapsed_us > max_time {
                max_time = elapsed_us;
            }

            let aux_mem = mem.saturating_sub(baseline_mem);

            total_mem += aux_mem;

            if aux_mem > max_mem {
                max_mem = aux_mem;
            }
        }

        let avg_time = total_time / RUNS as u128;
        let avg_mem = total_mem / RUNS;

        println!(
            "| {:>10} | {:>15} | {:>15} | {:>15} | {:>15} |",
            size,
            format!("{}.{:06}", avg_time / 1_000_000, avg_time % 1_000_000),
            format!("{}.{:06}", max_time / 1_000_000, max_time % 1_000_000),
            avg_mem,
            max_mem
        );
    }
}
RUST

RUN cargo build --release

CMD ["./target/release/rust-benchmark"]
EOF

docker build -t rust-benchmark "$WORKDIR"
docker run --rm --init rust-benchmark