Why is my Rust implementation of InsertionSort slower than my C version?

Question

I decided to start learning a programming language to rewrite my programs. The first were a simple program from the second year at the university. But... look at the tests! Why is a simple insertion sort so slow?

Test on C:

ARRAY SIZE: 100000
< counting_sort:  0.003602
< insertion_sort: 8.273647
< heap_sort:      0.017918

Test on Rust:

ARRAY SIZE: 100000
< counting_sort:  PT0.039530982S
< insertion_sort: PT276.529915469S
< heap_sort:      PT0.117946209S

How can I improve my converted code?

C-version:

void insertion_sort(int a[], int length) {
    int i, j, value;
    for (i = 1; i < length; i++) {
        value = a[i];
        for (j = i - 1; j >= 0 && a[j] > value; j--) {
            a[j + 1] = a[j];
        }
        a[j + 1] = value;
    }
}

Rust-version:

pub fn insertion_sort(array: &mut [i32]) {
    let mut value;
    for i in 1..array.len() {
        value = array[i];
        let mut flag = true;
        for j in (0..i).rev() {
            if array[j] > value {
                array[j + 1] = array[j];
            } else {
                flag = false;
                array[j + 1] = value;
                break;
            }
        }
        if flag {
            array[0] = value;
        }
    }
}

I was not building in release mode. Even after compiling in release mode:

C-version (gcc -O3):

ARRAY SIZE: 100000
< counting_sort:  0.001252
< insertion_sort: 1.672351
< heap_sort:      0.008694

Rust-version (cargo build --release):

ARRAY SIZE: 100000
< counting_sort:  PT0.001556914S
< insertion_sort: PT3.291146043S
< heap_sort:      PT0.008269021S

Answer 1

Why is a simple insertion sort so slow?

I would be willing to bet it's the bounds checks on array access. You're doing a lot of them.

If you use iterators instead of direct accesses, you don't pay this penalty. I don't have a version with iterators handy for you, at the moment, unfortunately. Maybe someone else can contribute one. :)