heapsort

Full source code

C++

// -*- mode: c++ -*-
// $Id$
// http://www.bagley.org/~doug/shootout/

#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <cstdio>

using namespace std;

#define IM 139968
#define IA   3877
#define IC  29573

double
gen_random(double max) {
    static long last = 42;
    return( max * (last = (last * IA + IC) % IM) / IM );
}

void
heapsort(int n, double *ra) {
    int i, j;
    int ir = n;
    int l = (n >> 1) + 1;
    double rra;

    for (;;) {
        if (l > 1) {
            rra = ra[--l];
        } else {
            rra = ra[ir];
            ra[ir] = ra[1];
            if (--ir == 1) {
                ra[1] = rra;
                return;
            }
        }
        i = l;
        j = l << 1;
        while (j <= ir) {
            if (j < ir && ra[j] < ra[j+1]) { ++j; }
            if (rra < ra[j]) {
                ra[i] = ra[j];
                j += (i = j);
            } else {
                j = ir + 1;
            }
        }
        ra[i] = rra;
    }
}

int
main(int argc, char *argv[]) {
#ifdef SMALL_PROBLEM_SIZE
#define LENGTH 800000
#else
#define LENGTH 8000000
#endif
    int N = ((argc == 2) ? atoi(argv[1]) : LENGTH);
    double *ary;
    int i;
    
    /* create an array of N random doubles */
    ary = (double *)malloc((N+1) * sizeof(double));
    for (i=1; i<=N; i++) {
        ary[i] = gen_random(1);
    }

    heapsort(N, ary);

    printf("%.10f\n", ary[N]);
    free(ary);
    return(0);
}

Rust

// Adapted from https://github.com/llvm/llvm-test-suite and
// http://www.bagley.org/~doug/shootout/
use std::env;

#[cfg(feature = "small_problem_size")]
const LENGTH: usize = 800000;

#[cfg(not(feature = "small_problem_size"))]
const LENGTH: usize = 8000000;

const IM: i64 = 139968;
const IA: i64 = 3877;
const IC: i64 = 29573;

fn get_random(last_random: &mut i64, max: f64) -> f64 {
    let new_last = (*last_random * IA + IC) % IM;
    *last_random = new_last;
    return max * (new_last as f64) / (IM as f64);
}

fn heapsort(n: usize, ra: &mut Vec<f64>) {
    let mut i: usize;
    let mut j: usize;
    let mut ir = n;
    let mut l = (n >> 1) + 1;
    let mut rra: f64;

    loop {
        if l > 1 {
            l -= 1;
            rra = ra[l];
        } else {
            rra = ra[ir];
            ra[ir] = ra[1];
            ir -= 1;
            if ir == 1 {
                ra[1] = rra;
                return;
            }
        }
        i = l;
        j = l << 1;
        while j <= ir {
            if j < ir && ra[j] < ra[j+1] { j += 1; }
            if rra < ra[j] {
                ra[i] = ra[j];
                i = j;
                j += i;
            } else {
                j = ir + 1;
            }
        }
        ra[i] = rra;
    }
}

fn main() {
    let mut args = env::args();
    let n = if args.len() == 2 {
        args.nth(1).unwrap().parse::<usize>().unwrap()
    } else {
        LENGTH
    };

    let mut last_random: i64 = 42;

    let mut ary = Vec::<f64>::new();
    ary.resize_with(n + 1, Default::default);
    for i in 1..=n {
        ary[i] = get_random(&mut last_random, 1.0);
    }

    heapsort(n, &mut ary);

    println!("{:.10}", ary[n]);
}

Porting notes

Replacing a C++ block-scoped static variable with a locally-scoped local variable

C++

inline double gen_random(double max) {
    static long last = 42;
    return( max * (last = (last * IA + IC) % IM) / IM );
}

Rust

fn gen_random(last_random: &mut i64, max: f64) -> f64 {
    let new_last = (*last_random * IA + IC) % IM;
    *last_random = new_last;
    return max * (new_last as f64) / (IM as f64);
}
...

fn main() {
    ...
    let mut last_random: i64 = 42;

    for i in 1..=n {
        ary[i] = get_random(&mut last_random, 1.0);
    }
    ...

Rust doesn't support a static variable nested in a function or block scope.

Furthermore, Rust doesn't allow a mutable global (static) variable without using a thread-safe mechanism such as a mutex.

To avoid the mutex overhead, the Rust version uses a locally scoped local variable last_random in the main function and passes its mutable reference to the gen_random function. This is safe because the lifetime of the variable covers the entire uses of the gen_random function.

I interpret this as Rust discouraging casual uses of global variables and encouraing uses of locally scoped thread-local data for thread safety reasons.

Using usize variables intead of int

C++

void
heapsort(int n, double *ra) {
    int i, j;
    int ir = n;
    int l = (n >> 1) + 1;

Rust

#![allow(unused)]
fn main() {
fn heapsort(n: usize, ra: &mut Vec<f64>) {
    let mut i: usize;
    let mut j: usize;
    let mut ir = n;
    let mut l = (n >> 1) + 1;
    ...
}

The Rust version uses the index variables of type `usize` instead of
`int`. This is more idiomatic because of the more explict distinction
between `usize` and `int` for vector indices in Rust.

## Writing an infinite loop

C++
```cpp
    for (;;) {
        ...
    }
}

Rust

#![allow(unused)]
fn main() {
    loop {
        ...
    }
}

In Rust, an infinite loop, which unconditionally loops (often with a `break` or `return` in the loop body), is written with the `loop` keyword, which is analogous to `for (;;) { ... }` or `while (true) { ... }` in C++.

## Formatting floating point values to show 10 digits after the decimal point

C++
```cpp
    printf("%.10f\n", ary[N]);
}

Rust

#![allow(unused)]
fn main() {
    println!("{:.10}", ary[n]);
}

Since printf formats a double to show the 6 digits after the decimal point by default, the Rust version uses the format specifier {:.6} to achieve the similar.