为何Rust实现的编辑距离函数比C++版本慢2倍？

核心性能差异原因 #

1. 编译优化级别差异
   你用G的-O3编译C代码，但Rust默认Release模式仅启用-O2优化。-O3会开启更多指令级优化、循环展开等特性，这是性能差距的主要来源。

2. min函数的编译优化差异
   C++的std::min({...})允许编译器直接生成针对三个值取最小的最优指令序列；而Rust中嵌套的std::cmp::min调用，编译器可能无法完全优化为同等高效的指令，产生额外分支开销。

3. 微小的类型转换开销
   Rust中usize（64位）转u32的操作虽无功能问题，但会引入微小的额外开销；同时C++使用int作为循环变量（你的字符串长度远小于int上限），编译器对32位整数循环的优化略优于64位usize。

具体优化步骤 #

1. 提升Rust编译优化级别 #

编译时启用最高优化级别并针对当前CPU优化，可通过命令行：

cargo build --release --config profile.release.opt-level=3 --config profile.release.target-cpu=native

或在Cargo.toml中配置：

[profile.release]
opt-level = 3
target-cpu = "native"
lto = true # 开启链接时优化，进一步提升性能

2. 优化min函数写法 #

将嵌套min调用改为数组迭代取最小，让编译器更容易生成和C++一致的高效指令：

cc[j] = [
    cp[j - 1] + if c1 == c2 { 0 } else { 1 },
    cc[j - 1] + 1,
    cp[j] + 1,
]
.iter()
.copied()
.min()
.unwrap();

3. 减少不必要的类型转换 #

由于你的字符串长度不超过105，完全在u32范围内，将循环变量改为u32避免类型转换开销：

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

    for i in 0..=len_s2 {
        cp[i as usize] = i;
    }

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

            cc[j as usize] = [
                cp[(j - 1) as usize] + if c1 == c2 { 0 } else { 1 },
                cc[(j - 1) as usize] + 1,
                cp[j as usize] + 1,
            ]
            .iter()
            .copied()
            .min()
            .unwrap();
        }
        std::mem::swap(&mut cp, &mut cc);
    }
    cp[len_s2 as usize]
}

4. 复用向量减少内存分配（可选） #

如果测试中多次调用sed函数，可提前创建向量并复用，避免重复分配内存的开销：

fn sed_reuse(s1: &[u8], s2: &[u8], cp: &mut Vec<u32>, cc: &mut Vec<u32>) -> u32 {
    let len_s1 = s1.len() as u32;
    let len_s2 = s2.len() as u32;
    
    cp.resize((len_s2 + 1) as usize, 0);
    cc.resize((len_s2 + 1) as usize, 0);

    for i in 0..=len_s2 {
        cp[i as usize] = i;
    }

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

            cc[j as usize] = [
                cp[(j - 1) as usize] + if c1 == c2 { 0 } else { 1 },
                cc[(j - 1) as usize] + 1,
                cp[j as usize] + 1,
            ]
            .iter()
            .copied()
            .min()
            .unwrap();
        }
        std::mem::swap(cp, cc);
    }
    cp[len_s2 as usize]
}

// 测试时复用向量
fn main() {
    let mut cp = Vec::new();
    let mut cc = Vec::new();
    // 嵌套循环调用sed_reuse
}

完成上述优化后，Rust版本的性能应接近甚至超过C++版本。若仍有差距，可对比两者的汇编代码，确认编译器生成的指令是否一致。

内容的提问来源于stack exchange，提问作者Lukáš Moravec