在Rust和C中，遍历二维数组的性能比较。

Question

我是Rust的新手，最近一直在研究它。我对比了在Rust和C中通过索引访问数组的性能。

我写了这两个程序：

fn main() {

    let mut arr: [[i32; 1000]; 1000] = [[0; 1000]; 1000];

    for t in 0..1000 {
        for i in 0..1000 {
            for j in 0..1000 {
                arr[i][j] = (i * j) as i32;
            }
        }
    }
}

在 C 语言中：

#include <stdlib.h>
#include <string.h>

#define ARRSIZE 1000

int main() {

    int ** arr = malloc(sizeof(int*) * ARRSIZE);
    int i, j, t;

    for (i = 0; i < ARRSIZE; ++i) {
        arr[i] = malloc(sizeof(int) * ARRSIZE);
        memset((void*) arr[i], 0, sizeof(int) * ARRSIZE);
    }

    for (t = 0; t < ARRSIZE; ++t) {
        for (i = 0; i < ARRSIZE; ++i) {
            for (j = 0; j < ARRSIZE; ++j) {
                arr[i][j] = i * j;
            }
        }
    }

    for (i = 0; i < ARRSIZE; ++i) {
        free(arr[i]);
    }

    free(arr);

}

这个想法是创建一个1000x1000的二维数组，并在每次迭代中对每个元素进行简单的算术运算，共进行1000次迭代。

两者之间的性能差距很大（C版本需要近3秒，Rust版本需要45秒）。这正常吗？还是我在Rust版本中做错了什么？

编辑：我尝试禁用边界检查，结果相同。

谢谢。

- Robfz

---

如果在Rust中反转i和j的循环控制，但不改变循环内部的表达式会发生什么？这对Rust的性能有影响吗？ - Jonathan Leffler

请[编辑]您的问题，包括您如何编译每个程序。Rust和C都有优化和非优化版本，这会极大地影响时间。而且，您在C中使用堆分配，但在Rust中没有。 - Shepmaster

从未使用过 Rust； 0..1000 表达式如何处理？如果它没有被优化掉，并且每次迭代（和子迭代）都会实际构建某种范围对象，则可能会出现问题。 - Oka

如果我使用rustc的优化级别3（使用-C opt-level=3）启动程序，它将立即执行完毕。你在性能分析中启用了哪些优化？另外，你的两种代码并不相同。在Rust版本中，你在栈上使用了一个数组。而在C版本中，你使用了堆。这可能对Rust更有利，但我想指出的是，你并没有真正比较相同的情况。 - Cornstalks

C语言版本进行了1001次单独的分配（我不知道Rust是否也这样做）。请注意，可以编写一个只使用单个分配的C语言版本。 - M.M

我投票关闭此问题，因为提供的信息不足。有关程序性能的问题应包括用于编译该程序的命令。 - Matthieu M.

Answer 1

除了DK的答案之外，为了进行（或更准确地说是让其他人参与），我对程序进行了以下修改以进行测试： Rust:

#![feature(test)]
extern crate test;

fn main() {
    let mut arr: [[i32; 1000]; 1000] = [[0; 1000]; 1000];

    for _ in 0..1000 {
        for i in 0..1000 {
            for j in 0..1000 {
                arr[i][j] = (i * j) as i32;
            }
        }
    }
    test::black_box(arr);
}

C（使用堆栈，代码主要由DK编写）：

#define ARRSIZE 1000

int main() {
    int arr[ARRSIZE][ARRSIZE] = { { 0 } };
    int i, j, t;

    for (t = 0; t < ARRSIZE; ++t) {
        for (i = 0; i < ARRSIZE; ++i) {
            for (j = 0; j < ARRSIZE; ++j) {
                arr[i][j] = i * j;
            }
        }
    }
    asm ("" : : "r" (arr));
}

black_box和asm(...)被用于防止优化器删除所有代码。然而，我使用了clang而不是gcc来使其工作。因此相比较而言：

$ rustc -O test.rs      |      $ clang -O2 test.c 
$ time ./test           |      $ time ./a.out 
                        |    
real    0m0.537s        |      real    0m0.546s
user    0m0.532s        |      user    0m0.544s
sys     0m0.004s        |      sys     0m0.004s

这两个程序的运行时间差异比同一程序单次执行的时间差异还要大。我想说的是（DK已经说了）：差异应该是微不足道的。两者都应该做完全相同的工作；只是Rust还进行了边界检查。但在这种情况下，这些检查可能被LLVM优化器删除了。只需记住以发布模式构建即可。

- Lukas Kalbertodt

---

优秀的回答和比较。 - Cornstalks

在你的asm语句中添加一个"memory" clobber，告诉编译器它可以访问除了输入/输出之外的内存，因此内存内容需要反映C源代码。请参见此godbolt链接以获取一个工作版本，使用asm（“”：：“g”（arr）：“memory”）;来打败优化器。请注意，将数组初始化为零然后再存储到其中是浪费memset的做法。不幸的是，gcc和clang在循环之前无法优化掉清零操作。还要注意，在使用-ftree-vectorize时，gcc和clang将自动使用SSE / AVX进行矢量化。 - Peter Cordes

Answer 2

首先，我假设您已经编译了没有优化的代码，因为我无法在调试模式下重现您所描述的时间，该模式不会进行过度优化。在这种情况下，差异并不令人惊讶，因为Rust正在执行更多的工作，并且众所周知，在调试模式下生成的代码不够优化。

其次，这两个程序并不等价。C代码正在分配1001个堆数组，而Rust代码没有分配任何一个。因此，一旦您打开优化，Rust代码比C代码运行得更快。

现在我们需要修改C程序以避免分配。鉴于此：

#define ARRSIZE 1000

int main() {
    int arr[ARRSIZE][ARRSIZE] = { { 0 } };
    int i, j, t;

    for (t = 0; t < ARRSIZE; ++t) {
        for (i = 0; i < ARRSIZE; ++i) {
            for (j = 0; j < ARRSIZE; ++j) {
                arr[i][j] = i * j;
            }
        }
    }
}

我使用gcc -O（GCC 4.8.4）和rustc -O（Rust 1.7.0）编译的结果如下：

$ time ./c-2; time ./rs-1

real    0m0.335s
user    0m0.328s
sys 0m0.000s

real    0m0.002s
user    0m0.000s
sys 0m0.000s

这些测试内容太过简单，几乎毫无意义。 但情况变得更糟了。Rust 程序如此之快的原因是程序非常简单，LLVM 完全移除了它。程序没有可见的副作用，所以它只编译成一个立即退出的空二进制文件。

从这个基准测试中，没有有意义的信息可以获取，只能得出 Rust 生成的调试可执行文件很慢（这已经相对来说是众所周知的）。

- DK.

---

@MillieSmith：那么你正在对终端输出的值进行分析，因为这将是程序中最昂贵的部分（远远超过其他部分）。而且这不是一个非常有意义的比较。而且不仅 Rust 编译器会优化程序；只要打开任何有意义的优化，C 编译器也可能会这样做。 - Cornstalks

FYI，对于 rustc 来说，-O 更接近于 gcc 的 -O2。rustc 的 man 页面上写道，-O 等效于 -C opt-level=2。 - Cornstalks

@Cornstalks 在打印操作之前停止计时器。并且在两种语言中都使用计时器API。即不再使用“time”Linux命令。 - Millie Smith

@Cornstalks，如果计时器在释放模式下打开优化并且需要45秒才能启动自身并停止自身，那么该计时器API肯定有问题。OP基准测试使用了调试模式，这大大增加了时间，而本答案的基准测试则将整个程序优化掉了，这使得整个程序变得毫无用处。最好找到一个折中的方案。如果我所建议的在Rust中需要花费超过几秒钟的时间，那么这两种语言之间仍然存在相当大的差异。 - Millie Smith

@Cornstalks，从这两个基准测试中你无法判断这些编程语言是否表现相同。计时器API非常快速，启动和停止一个计时器只需要不到一秒钟的时间。你对这些基准测试的任何改进都是泛泛而谈，实际上还有很多可以做的改进。我的建议确实能够产生有价值的结果。 - Millie Smith