为什么当我移除边界检查时，我的代码运行速度变慢了？

Question

我正在使用Rust编写线性代数库。

我有一个函数，可以获取给定行和列的矩阵单元格的引用。此函数以一对断言开始，用于检查行和列是否在范围内：

#[inline(always)]
pub fn get(&self, row: usize, col: usize) -> &T {
    assert!(col < self.num_cols.as_nat());
    assert!(row < self.num_rows.as_nat());
    unsafe {
        self.get_unchecked(row, col)
    }
}

在紧密循环中，我认为跳过边界检查可能会更快，因此我提供了一个get_unchecked方法：

#[inline(always)]
pub unsafe fn get_unchecked(&self, row: usize, col: usize) -> &T {
    self.data.get_unchecked(self.row_col_index(row, col))
}

奇怪的是，当我使用这些方法来实现矩阵乘法（通过行和列迭代器）时，我的基准测试显示，如果我检查边界，它实际上会快约33％。为什么会这样呢？

我已经在两台不同的计算机上尝试过了，一台运行Linux，另一台运行OSX，两者都显示了这种效果。

完整的代码在github上。相关文件是lib.rs。感兴趣的函数包括：

- 在第68行的get - 在第81行的get_unchecked - 在第551行的next - 在第796行的mul - 在第1038行的matrix_mul（基准测试）

请注意，我正在使用类型级别数字来参数化我的矩阵（也可以通过虚标记类型进行动态大小），因此基准测试正在将两个100x100矩阵相乘。

更新：

我大幅简化了代码，删除了与基准测试无关的内容并删除了通用参数。我还编写了一个不使用迭代器的乘法实现，该版本不会导致相同的效果。请参见此处以获取代码的此版本。克隆minimal-performance分支并运行cargo bench将对两个不同的乘法实现进行基准测试（请注意，开始时断言被注释掉了）。

还值得注意的是，如果我更改get*函数以返回数据的副本而不是引用（f64而不是&f64），则效果会消失（但整体速度略慢）。

- Bradley Hardy

---

又是那个老问题：你是否使用编译器优化（使用“--release”标志）进行编译？;) - Lukas Kalbertodt

对于生锈问题一无所知：您的基准测试是否合理？缓存效应、方差、测试数据同步等等。 - sascha

@LukasKalbertodt 看看我的更新。代码可能不像你想的那么简洁，但是从大约1000行减少到了约200行，并且我已经放弃了使事情更难以理解的泛型。 - Bradley Hardy

也许当您检查边界时，编译器可以更积极地进行优化？ - HiDefender

最好的做法是编译独立的二进制文件，并使用 objdump -D来识别相关紧密循环中使用的机器指令。 - dpc.pw

Answer 1

这并不是一个完整的答案，因为我没有测试我的说法，但这可能可以解释一下。无论如何，确定的方法是生成LLVM IR和汇编输出。如果您需要LLVM IR的手册，可以在这里找到：http://llvm.org/docs/LangRef.html。

话说回来，假设您有以下代码：

#[inline(always)]
pub unsafe fn get_unchecked(&self, row: usize, col: usize) -> &T {
    self.data.get_unchecked(self.row_col_index(row, col))
}

这里的编译器将其转换为间接加载，这在紧密循环中可能会被优化。有趣的是，每次加载都有可能出错：如果您的数据不可用，它将触发越界。

在边界检查与紧密循环结合的情况下，LLVM做了一个小技巧。因为加载在紧密循环（矩阵乘法）中，并且由于边界检查的结果取决于循环的边界，所以它将从循环中删除边界检查，并将其放置在循环周围。换句话说，循环本身将保持完全相同，但增加了额外的边界检查。

换句话说，代码完全相同，只有一些细微的差别。

那么有什么变化吗？两件事：

1.如果我们有额外的边界检查，就不可能再出现越界加载的情况。这可能会触发以前无法实现的优化。然而，考虑到通常如何实现这些检查，这不会是我的猜测。

2.还要考虑的另一件事是，“不安全”这个词可能会触发某些行为，例如添加附加条件、锁定数据或禁用GC等。我不确定Rust中的确切行为；查看LLVM IR是了解这些细节的唯一方法。

- atlaste