诊断性能问题

Question

我对Rust并不是很有经验，我试图诊断一个性能问题。下面是一段非常快的Java代码（运行时间为7秒），以及我认为应该等效的Rust代码。然而，Rust代码运行非常缓慢（是的，我也使用了--release编译），而且似乎还会溢出。将i32更改为i64只是推迟了溢出的发生时间，但仍然会发生。我怀疑我写的代码中存在一些错误，但是在长时间盯着问题后，我决定寻求帮助。

public class Blah {

    static final int N = 100;
    static final int K = 50;

    public static void main(String[] args) {
        //initialize S
        int[] S = new int[N];
        for (int n = 1; n <= N; n++) S[n-1] = n*n;

        // compute maxsum and minsum
        int maxsum = 0;
        int minsum = 0;
        for (int n = 0; n < K; n++) {
            minsum += S[n];
            maxsum += S[N-n-1];
        }

        // initialize x and y
        int[][] x = new int[K+1][maxsum+1];
        int[][] y = new int[K+1][maxsum+1];
        y[0][0] = 1;

        // bottom-up DP over n
        for (int n = 1; n <= N; n++) {
            x[0][0] = 1;
            for (int k = 1; k <= K; k++) {
                int e = S[n-1];
                for (int s = 0; s < e; s++) x[k][s] = y[k][s];
                for (int s = 0; s <= maxsum-e; s++) {
                    x[k][s+e] = y[k-1][s] + y[k][s+e];
                }
            }
            int[][] t = x;
            x = y;
            y = t;
        }

        // sum of unique K-subset sums
        int sum = 0;
        for (int s = minsum; s <= maxsum; s++) {
            if (y[K][s] == 1) sum += s;
        }
        System.out.println(sum);
    }

}

extern crate ndarray;

use ndarray::prelude::*;
use std::mem;

fn main() {
    let numbers: Vec<i32> = (1..101).map(|x| x * x).collect();

    let deg: usize = 50;

    let mut min_sum: usize = 0;
    for i in 0..deg {
        min_sum += numbers[i] as usize;
    }

    let mut max_sum: usize = 0;
    for i in deg..numbers.len() {
        max_sum += numbers[i] as usize;
    }

    // Make an array
    let mut x = OwnedArray::from_elem((deg + 1, max_sum + 1), 0i32);
    let mut y = OwnedArray::from_elem((deg + 1, max_sum + 1), 0i32);

    y[(0, 0)] = 1;

    for n in 1..numbers.len() + 1 {
        x[(0, 0)] = 1;
        println!("Completed step {} out of {}", n, numbers.len());
        for k in 1..deg + 1 {
            let e = numbers[n - 1] as usize;
            for s in 0..e {
                x[(k, s)] = y[(k, s)];
            }
            for s in 0..max_sum - e + 1 {
                x[(k, s + e)] = y[(k - 1, s)] + y[(k, s + e)];
            }
        }
        mem::swap(&mut x, &mut y);
    }

    let mut ans = 0;

    for s in min_sum..max_sum + 1 {
        if y[(deg, s)] == 1 {
            ans += s;
        }
    }

    println!("{}", ans);

}

- Sidious Lord

---

1. 你确定这个程序大约需要7秒运行吗？在我的机器上，它只需要不到2秒。
2. 这里没有任何溢出的可能性...你正在将2D数组x的值从2D数组y中赋值，而2D数组y中充满了0，并且永远不会更新为其他任何值...因此，2D数组x也只有0...你到底想做什么？我看不到溢出。

- Mostafa Ali

@MostafaAli 1）我能告诉你的是，我的电脑很老。Java程序需要7秒钟，而Rust程序需要几分钟才能完成。2）关于溢出。最终答案约为10^8，小于2^31-1=2147483647。最后，你对于零的理解是错误的。x和y并不全为零。 - Sidious Lord

抱歉，我错过了代码底部的部分，你在那里计算总和...最终得出了一些不同的逻辑。 - Mostafa Ali

Answer 1

一般情况下，为了诊断性能问题，我会执行以下步骤：

1. 获取基准时间或速率。最好创建一个只需要几秒钟的测试用例，因为分析器往往会使系统变慢一些。您还需要经常迭代。
2. 使用调试符号在发布模式下编译。
3. 在分析器中运行代码。我使用的是 OS X 上的 Instruments，但我也使用 valgrind。
4. 找到最热门的代码路径，思考为什么它会变慢，尝试一些方法，进行测量。

最后一步是最困难的部分。

---

在您的情况下，您有一个单独的实现可用作基准。比较这两个实现，我们可以看到您的数据结构不同。在Java中，您正在构建嵌套数组，但在Rust中，您正在使用ndarray crate。我知道该crate有一个很好的维护者，但我个人对其内部或最适合使用的用例一无所知。

因此，我重新编写了这个程序，使用了标准库中的Vec。

我还知道的另一件事是，直接访问数组并不像使用迭代器那样快。这是因为数组访问需要执行边界检查，而迭代器则将边界检查嵌入到自身中。这通常意味着使用Iterator上的方法。

另一个更改是尽可能执行批量数据传输。与逐个元素复制不同，移动整个切片，使用像copy_from_slice这样的方法。

通过这些更改，代码如下所示（对于变量名称不好，请见谅，我相信您可以想出语义化的名称）：

use std::mem;

const N: usize = 100;
const DEGREE: usize = 50;

fn main() {
    let numbers: Vec<_> = (1..N+1).map(|v| v*v).collect();

    let min_sum = numbers[..DEGREE].iter().fold(0, |a, &v| a + v as usize);
    let max_sum = numbers[DEGREE..].iter().fold(0, |a, &v| a + v as usize);

    // different data types for x and y!
    let mut x = vec![vec![0; max_sum+1]; DEGREE+1];
    let mut y = vec![vec![0; max_sum+1]; DEGREE+1];
    y[0][0] = 1;

    for &e in &numbers {
        let e2 = max_sum - e + 1;
        let e3 = e + e2;

        x[0][0] = 1;

        for k in 0..DEGREE {
            let current_x = &mut x[k+1];
            let prev_y = &y[k];
            let current_y = &y[k+1];

            // bulk copy
            current_x[0..e].copy_from_slice(&current_y[0..e]);

            // more bulk copy
            current_x[e..e3].copy_from_slice(&prev_y[0..e2]);

            // avoid array index
            for (x, y) in current_x[e..e3].iter_mut().zip(&current_y[e..e3]) {
                *x += *y;
            }
        }

        mem::swap(&mut x, &mut y);
    }

    let sum = y[DEGREE][min_sum..max_sum+1].iter().enumerate().filter(|&(_, &v)| v == 1).fold(0, |a, (i, _)| a + i + min_sum);

    println!("{}", sum);
    println!("{}", sum == 115039000);
}

• 2.060 秒 - Rust 1.9.0
• 2.225 秒 - Java 1.7.0_45-b18

在配备 2.3 GHz 英特尔 Core i7 处理器的 OS X 10.11.5 上。

我对 Java 不是很熟悉，不知道它能自动进行哪些优化。

我看到的最大潜力下一步是在执行加法时利用 SIMD 指令；这几乎就是 SIMD 的用途所在。

---

正如 Eli Friedman 指出的那样，通过将数组压缩起来避免使用数组索引 目前不是最具性能的方式。

采用下面的改变后，现在时间为 1.267s。

let xx = &mut current_x[e..e3];
xx.copy_from_slice(&prev_y[0..e2]);

let yy = &current_y[e..e3];
for i in 0..(e3-e) {
    xx[i] += yy[i];
}

这将生成汇编代码，看起来像是展开循环并使用SIMD指令：

+0x9b0    movdqu    -48(%rsi), %xmm0
+0x9b5    movdqu    -48(%rcx), %xmm1
+0x9ba    paddd     %xmm0, %xmm1
+0x9be    movdqu    %xmm1, -48(%rsi)
+0x9c3    movdqu    -32(%rsi), %xmm0
+0x9c8    movdqu    -32(%rcx), %xmm1
+0x9cd    paddd     %xmm0, %xmm1
+0x9d1    movdqu    %xmm1, -32(%rsi)
+0x9d6    movdqu    -16(%rsi), %xmm0
+0x9db    movdqu    -16(%rcx), %xmm1
+0x9e0    paddd     %xmm0, %xmm1
+0x9e4    movdqu    %xmm1, -16(%rsi)
+0x9e9    movdqu    (%rsi), %xmm0
+0x9ed    movdqu    (%rcx), %xmm1
+0x9f1    paddd     %xmm0, %xmm1
+0x9f5    movdqu    %xmm1, (%rsi)
+0x9f9    addq      $64, %rcx
+0x9fd    addq      $64, %rsi
+0xa01    addq      $-16, %rdx
+0xa05    jne       "slow::main+0x9b0"

- Shepmaster

---

事实证明，在这种情况下使用显式数组索引实际上更快；有关原因的讨论请参见 https://users.rust-lang.org/t/how-to-zip-two-slices-efficiently/2048/13。 - Eli Friedman