为什么 Rust 的函数移植比 C++ 慢 2 倍？

Question

我有一个在 C++ 中计算字符串编辑距离的函数：

#include <string>
#include <vector>
#include <algorithm>

size_t sed_diff(const std::string & a, const std::string & b) {

    std::vector<size_t> cp(b.length() + 1);
    std::vector<size_t> cc(b.length() + 1);

    // Edit distance on postorder traversal.
    for (int j = 0; j <= b.length(); ++j) {
        cp[j] = j;
    }
    for (int i = 1; i <= a.length(); ++i) {
        cc[0] = i;
        for (int j = 1; j <= b.length(); ++j) {
            unsigned int c1 = a[i - 1];
            unsigned int c2 = b[j - 1];
            cc[j] = std::min({
                                     cp[j - 1] + ((c1 == c2) ? 0 : 1),
                                     cc[j - 1] + 1,
                                     cp[j] + 1
                             });
        }
        std::swap(cp, cc);
    }
    return cp[b.length()];
}

int main() {
    // call
    sed_diff(std::string("banana"), std::string("mango"));
    return 0;
}

我尝试用 Rust 代码重写相同的内容：

fn sed(s1: &[u8], s2: &[u8]) -> u32 {
    let mut cp = vec![0u32; s2.len() + 1];
    let mut cc = vec![0u32; s2.len() + 1];

    for i in 0..=s2.len() {
        cp[i] = i as u32;
    }

    for i in 1..=s1.len() {
        cc[0] = i as u32;
        for j in 1..=s2.len() {
            let c1 = s1[i - 1];
            let c2 = s2[j - 1];

            cc[j] = std::cmp::min(
                std::cmp::min(cp[j - 1] + if c1 == c2 { 0 } else { 1 }, cc[j - 1] + 1),
                cp[j] + 1,
            )
        }
        std::mem::swap(&mut cp, &mut cc);
    }
    cp[s2.len()]
}

fn main() {
    sed(
        String::from("banana").as_bytes(),
        String::from("mango").as_bytes(),
    );
}

在同一数据集上对代码进行基准测试时，C++ 代码平均运行时间约为 15 秒，而 Rust 编译的代码平均总运行时间约为 30 秒。

这两个测试都在嵌套的 for 循环中运行，使用 20 000 个输入字符串和 50 个测试字符串。

但我不明白，为什么 Rust 版本慢这么多？

Answer 1

听你说，听你说

评论中的讨论让我很好奇，所以我尝试了不同的变体。在讨论结果之前，让我们先澄清一下。 从结果中几乎没有什么可以概括的，当然也没有什么可推论的。这是一个非正式的学术练习。

编译器就是混杂变量的定义。哪个编译器、哪个设置、哪个版本、哪个目标平台都很重要。最好的是一个大的旧的

这取决于，任何说其他话的人都忽略了他们具体情况的警告，或者生活在几十年前，当时你可以使用“5个巧妙的技巧来提高性能”。

接下来，现代 CPU 是巫术。与 25 年前的整个 CPU 相比，流水线中的指令获取步骤可以拥有更多的晶体管/优化复杂性。举一个基本的例子，您的 CPU 可能会

重新排序实时输入的指令以避免出现 NOOP

，而这只是表面现象。

最后，我们正在讨论的事物类型在现实世界中几乎从不重要。当它们发生时，您必须首先进行测量和分析。永远不要一开始就担心这些类型的调整。

性能比较

我获取了 OP 代码并将其放入不同大小的循环中。我测试了4个版本：

原样
• • 3.33s | 3.52s | 3.30s | 3.31s
与
• get_unchecked

   和 

  get_unchecked_mut
  • 3.08s | 3.35s | 3.14s | 3.24s
照原样，但没有范围
• • 3.54s | 3.36s | 3.51s | 3.39s
无范围 +
• get_unchecked

   和 

  get_unchecked_mut
  • 3.12s | 3.18s | 3.16s | 3.37s

首先要注意的是，相对于我们尝试测量的任何差异，这里的误差幅度确实很高，这很有意义。这里的差异可能归结为 1-2 条指令。我需要运行更多样本并使用一些基本统计数据来肯定地说，未经检查的索引的优化速度更快，但是在不同的尺度上进行试验似乎确实存在一致的差异，我只分享了一些数字.

未经检查比不使用范围更重要，尽管我也不完全理解为什么范围在这里很重要。任何溢出/下溢风险都来自于以可能发生的方式设置的边界（最小值或最大值，以及可以在条件检查之前改变的任意输入）。我可能只是误解了这个论点:)

未经检查，

可能会稍微快一些。

为什么只是快一点？好吧，这里的差异再次很小。在纯实现中，唯一的区别是条件跳转，即 1 或 2 条指令，具体取决于 ISA。那只是……没什么。根本不具备现代计算机的规模。另外，我们还有分支预测。分支预测器应该很容易注意到很少触发的边界条件，并将其设为默认路径。

此外，虽然我没有花时间寻找所使用的确切 impl，但值得注意的是，在 Rust 标准库中，相关函数倾向于使用

这个宏，它实际上确实有一个运行时 if 语句。

我们没有考虑到 2 倍观察到的性能增量与逻辑上的差异。最多我能得到额外的 2-4%。

那么为什么 OPs C++ 速度这么快？

好吧，除非评论中的群体错过了一个想法，否则两者之间的逻辑存在细微差别似乎很大程度上是转移注意力。更有可能的是，OP 完整设置中的其他内容导致了差异。例如，字符串的使用方式是否与“完全相同”相同？是否曾经发生过复制而不是借用的情况？一个分配到堆而另一个使用常量吗？

外卖

这是一个耻辱

std::vector::at
1. 抛出，因为边界检查的差异看起来很小。同样，您需要进行适当的研究才能确定，但也许在 C++ 中，我们可以执行 Rust 风格的检查边界，然后恐慌，而不是允许内存访问冲突以几乎没有性能成本的方式提高安全性。
   永远不要依赖直觉来提高性能，特别是对于小代码片段和非算法/非数据结构差异或小数据集（例如，基于数组的树集可能比小元素计数上的哈希集更快）

2. 如果您得到奇怪的结果，则您可能看错了位置。运行分析器，查看实际花费时间的内容。