最快的用于FOR循环的编程语言

Question

我正在寻找最适合我正在构建的分析模型的编程语言。主要考虑因素是运行 FOR 循环的速度。

一些细节：

• 该模型需要对数组中的一组元素执行大量（每个条目约30次，在12个周期内）操作 -- 数组中有约300k行和150列。其中大多数操作都是逻辑性质的，例如，如果place(i) = 1，则j(i) = 2。
• 我已经使用Octave构建了此模型的早期版本--在Amazon EC2 m2.xlarge实例上运行它需要约55小时（它使用了约10 GB的内存，但我完全可以为其提供更多内存）。Octave/Matlab无法执行逐元素逻辑运算，因此需要大量的for循环--我相当确定我已经向量化了尽可能多的内容--剩下的循环是必需的。我已经让octave-multicore与此代码配合使用，这使得一些改进成为可能（当我在8个EC2核心上运行它时，速度降低了约30%），但最终会因文件锁定等问题而不稳定。 +我真的希望能够实现运行时间的飞跃--我知道实际使用Matlab可能会让我获得多达50%的改进，从某些基准测试中可以看出，但这是成本禁止的。当开始这项工作时，最初的计划是实际运行蒙特卡罗模拟，但以55小时的运行时间来看，这完全不切实际。
• 下一个版本将从头开始进行完全重建（出于知识产权等原因，如果没有其他原因，我不会深入讨论），因此我完全开放任何编程语言。我最熟悉Octave/Matlab，但已经涉猎了R、C、C++、Java。如果解决方案涉及将数据存储在数据库中，则我也精通SQL。我会为此学习任何语言--我们正在寻找的不是复杂的功能，不涉及与其他程序的接口等，因此不太担心学习曲线。

那么，就所有这些而言，哪种编程语言对于 FOR 循环最快？ 从SO和Google的搜索结果来看，Fortran和C排名靠前，但在深入研究之前，希望能得到更多建议。

谢谢！

- Noah

---

这可能是一个愚蠢的问题，但在一行上执行的操作是否会影响其他行的计算结果？ - Roman

在某些地方，它们确实会这样做，但目前最耗时的函数（约占运行时间的80％）并没有这样做。 - Noah

正如其他人所建议的，我会选择Fortran。在可能的情况下使用元素函数，对于无法在整个数组的部分上执行的操作，请使用FOR和DO。一些操作的某些部分是否可以并行化？此外，考虑Fortran如何在内存中存储数据。谨慎选择索引和操作顺序也可以带来一些速度提升。 - Rook

我建议你在C语言中编写最计算密集的循环，不使用向量化技术，然后观察GCC如何处理它——它应该能够自动对操作进行向量化（取决于所执行的操作——但听起来你的最计算密集的循环与上下文无关，这有助于向量化）。 - porges

如果你可以将工作外包给GPU，那么语言的选择将取决于是否存在一个足够好的GPU库。 - Hamish Grubijan

我知道这个问题很老了，但我想说的是，你的解决方案需要确保在这些数组上有有效的索引。 - Worthy7

Answer 1

当这个for循环被CPU执行时，它看起来并不比这个复杂：

for(int i = 0; i != 1024; i++) 翻译成

mov r0, 0           ;;start the counter    
top:

;;some processing

add r0, r0, 1       ;;increment the counter by 1
jne top: r0, 1024   ;;jump to the loop top if we havn't hit the top of the for loop (1024 elements)

;;continue on

正如你所看到的，这个问题足够简单，你无法进行很好的优化[1]...请将注意力转向算法层面。

首先考虑缓存局部性。查找矩阵乘法和交换i和j索引的经典示例。

编辑：作为第二步尝试，建议评估迭代之间的数据依赖关系以及数据在您的“矩阵”中的局部性之间的依赖关系的算法。这可能是并行化的好选择。

[1]存在一些微小的优化可能，但这些不会产生您所寻求的速度提升。

- Paul Nathan

---

如果原帖作者使用Octave或Matlab，并且可以将他的算法向量化，那么他可以看到巨大的速度提升。然而，如果他确实无法再进行向量化（如原帖中所述），必须依赖循环，那么该算法可能不适合Matlab，改用编译语言可以使速度增加一个数量级。 - MarkD

Answer 2

~300k * ~150 * ~30 * ~12 = ~16G 次迭代，对吗？ 这个数量级的基本操作在任何编译语言和任何像样的CPU上都应该可以在几分钟内（如果不是几秒钟）完成。 Fortran、C/C++都可以表现得几乎一样好。即使是像Java和C#这样的托管语言，也只会稍微落后一点（如果有的话）。

如果您遇到 ~16G 次迭代需要运行 55 个小时的问题，这意味着它们远非基本操作（每秒 80k？这太荒谬了），因此我们可能需要了解更多信息。（正如已经建议的那样，磁盘访问限制了性能吗？是网络访问吗？）

- Rotsor

---

Octave不是一种编译语言，所以不确定这是否改变了时间观点。没有磁盘/网络访问，因为Octave将所有数据存储在内存中。在耗时的循环中有排序和查找操作--例如，对10个元素的列表进行排序，然后查找排序数组中给定元素的位置（这可以使用rank函数完成，但我尚未能够找到Octave/Matlab中直接的rank函数）。不确定这是否符合非原始的要求... - Noah

当然，对10个元素进行排序并不是一个原始操作（更像是大约40个操作），但这仍然不能解释我遇到的性能瓶颈。我从未使用过Octave，也不了解它的性能，但根据你告诉我们的情况，我相信任何编译语言都可以做得更好。你只需要选择更方便的那个（你更熟悉的）。顺便说一下，在编译语言中限制你性能的不是for循环，而是排序和内存访问。 - Rotsor

@Noah FYI，在Matlab中，您可以从sort()函数的第二个返回参数中获取排名顺序。 - dkantowitz

Answer 3

正如@Rotsor所说，16G次操作/55小时大约是每秒80,000次操作，或者每12.5微秒一次操作。这是每个操作的很多时间。

这意味着你的循环不是性能不佳的原因，而是内部循环中的内容需要花费时间。而Octave是一种解释语言。仅这一点就意味着降速一个数量级。

如果你想要速度，首先需要使用编译语言。然后你需要进行性能调优（也称为分析）或者在指令级别上单步调试。这将告诉你它实际上在做什么。一旦你把它变得不浪费周期，更高级的硬件、核心、CUDA等将为你提供并行加速。但如果你的代码需要不必要的循环，那么这样做是愚蠢的。(这是一个性能调优的例子-通过删除冗余代码，加速了43倍.) 我无法相信有这么多回应者在谈论Matlab、APL和其他矢量化语言。它们都是解释器，提供简洁的源代码，但这与快速执行完全不同。当涉及到底层时，它们与其他语言一样受限于相同的硬件。请注意保留HTML标签。

---

添加：为了让你明白我的意思，我刚刚在这台老旧的笔记本上运行了这段C++代码，它执行了16G次操作，耗时94秒，每次迭代约6纳秒。（我简直不敢相信你要看着那个东西照顾2整天。）

void doit(){
  double sum = 0;
  for (int i = 0; i < 1000; i++){
    for (int j = 0; j < 16000000; j++){
      sum += j * 3.1415926;
    }
  }
}

- Mike Dunlavey

---

同意-在现代处理器上，12.5微秒是很长的时间。我对自己的笔记本电脑（联想W500）进行了基准测试，每个循环迭代花费5 纳秒（特别是在大型1维int数组中初始化值的C# foreach循环）。 - Bevan

@Bevan：是的，这跟我得到的差不多。 - Mike Dunlavey

Answer 4

就绝对速度而言，可能是Fortran，其次是C，再其次是C++。在实际应用中，使用任何一种编写良好的代码，并使用一个良好的编译器进行编译，都应该足够快。

编辑-通常情况下，在使用编译语言（例如-if语句）的代码中，使用任何类型的循环或分叉，与解释性语言相比都能获得更好的性能。

举个例子，在我最近进行的一个项目中，数据大小和操作大约为您所述问题的3/4，但像您的代码一样，几乎没有空间进行向量化，并需要大量循环。将代码从matlab转换为C ++后，运行时间从16-18小时缩短到大约25分钟。

- MarkD

---

我想不出在C和C++中for循环会有任何不同的理由。如果您在C++中操作某些过于复杂的数据类型，可能会使其变慢，但没有明显的理由这样做。只要不费力地在for循环中使用虚拟方法，这可能会带来非常小的虚表开销，并且我预计一个合理编写的C++版本将编译成与C版本相同的二进制代码。话虽如此，问题是错误的。for循环是特定语言语法的产物，它们的性能不能有用地进行比较。 - wrosecrans

C和C++之间的区别并不是由于语言本身，而是由于人们使用语言的方式。举个简单的例子，如果你在C++中的循环内部增加一个向量，你可能没有意识到这是多么昂贵的操作，但如果你在C中手动分配内存，那就容易看出来了。 - Larry Wang

Answer 5

对于您所讨论的问题，Fortran 可能是您的首选。最接近的第二选择可能是 C++。一些 C++ 库使用“表达式模板”来在这种任务上比 C 更快地运行。不完全确定它们是否对您有用，但 C++ 至少可以与 C 一样快，甚至可能更快。

至少在理论上，Ada 也可以具有竞争力，但我已经很久没有像这样使用它了，所以我不敢推荐它——不是因为它不好，而是因为我没有足够了解当前 Ada 编译器的情况，无法做出明智的评论。

- Jerry Coffin

Answer 6

任何编译语言都应该在大致相等的条件下执行循环。

如果您可以用它的术语来阐述您的问题，您可能想查看CUDA或OpenCL，并在GPU上运行矩阵代码-尽管这对于有许多条件的代码不太好。

如果您想留在传统的CPU上，您可以使用SSE散布/聚集和位掩码操作来阐述您的问题。

- Pete Kirkham

Answer 7

可能是针对您所使用的平台的汇编语言。但是编译器（特别是专门针对单个平台的特殊编译器（例如Analog Devices或TI DSP））通常与人类一样出色甚至更好。此外，编译器通常知道您不知道的技巧。例如，上述DSP支持零开销循环，编译器将知道如何优化代码以使用这些循环。

- Chris

Answer 8

C++在使用for循环进行矩阵计算时并不快速。事实上，C语言在这方面表现特别差。请参见good math bad math。

我听说C99有__restrict指针可以帮助解决问题，但我对此了解甚少。

Fortran仍然是数值计算的首选语言。

- Robert Cooper

---

“Goto语句被认为是有害的”--艾兹格·迪科斯彻，1968年 - Jason S

Answer 9

Matlab可以执行逐元素逻辑运算，而且通常非常快速。

以下是我电脑上（AMD Athalon 2.3GHz w/3GB）的一个快速示例：

d=rand(300000,150);
d=floor(d*10);

>> numel(d(d==1))
ans =
     4501524

>> tic;d(d==1)=10;toc;
Elapsed time is 0.754711 seconds.

>> numel(d(d==1))
ans =
     0
>> numel(d(d==10))
ans =
     4501524

总的来说，我发现Matlab的运算符非常快速，只需要找到一种直接使用矩阵运算符表达算法的方法即可。

- dkantowitz

Answer 10

数据是如何存储的？您的执行时间可能更受到I/O（特别是磁盘或更糟的网络）的影响，而不是语言本身。

假设对行的操作是正交的，我会选择C#并使用PLINQ来利用所有可能的并行性。

- Justin R.

---

由于OP提到了Octave，我猜他正在使用Octave通常在内存中作为数组存储的正常矩阵/数组存储方式。在这种情况下，我猜测语言确实是导致减速的原因，因为Matlab和Octave在循环方面非常慢而出名。 - MarkD

数据在启动时全部从磁盘加载（大约占用了 55 小时运行时间的 10 分钟），并且在整个运行时期间都存储在内存中。我认为磁盘 I/O 时间是我没有看到 octave-multicore 更大改进的原因（它依赖于将作业文件写入一个共同目录，供一组监视该目录的从属进程，然后重新组合它们）。 - Noah