为什么我的InsertionSort的Rust实现比我的C版本慢？

Question

我决定开始学习一门编程语言来重写我的程序。第一个是大学二年级的一个简单的项目。但是..。看看这些测试！为什么简单的插入排序这么慢？

C++的测试：

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

铁锈测试：

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

如何改进转换后的代码？

C-版本：

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-版本：

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;
        }
    }
}

我不是在发布模式下构建的。即使在发布模式下编译之后也是如此：

C-版本(gcc -O3)：

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

Rust-版本(cargo build --release)：

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

Answer 1

为什么简单的插入排序会这么慢？

我敢打赌这是数组访问的边界检查。你已经做了很多了。

如果你使用迭代器而不是直接访问，你不会为此付出代价。不幸的是，目前我手头上还没有一个带迭代器的版本。也许其他人可以贡献一个。:)