FOR循环的最快语言

Question

我正在试图找出我正在构建的分析模型的最佳编程语言.主要考虑因素是它运行FOR循环的速度.

一些细节:

• 该模型需要对数组中的一组元素执行大量(每次输入约30次,超过12次循环)操作 - 阵列中有大约300k行和~150列.这些操作中的大多数本质上是逻辑的,例如,如果place(i)= 1,则j(i)= 2.
• 我使用Octave构建了这个模型的早期版本 - 在Amazon EC2 m2.xlarge实例上运行它需要大约55个小时(它使用~10 GB的内存,但我非常乐意在内存中添加更多内存它).Octave/Matlab不会进行元素逻辑运算,因此需要大量的for循环 - 我相对确定我已经尽可能地向量化了 - 剩下的循环是必要的.我已经得到了八度多核以使用这个代码,这有一些改进(当我在8个EC2内核上运行时减速约30%),但最终会因文件锁定等而变得不稳定.+我真的寻找运行时的一个步骤变化 - 我知道实际使用Matlab可能会让我从一些基准测试中获得50%的改进,但这是成本过高的.
• 下一个版本将是从头开始的完整重建(出于IP原因,我不会进入其他任何事情),所以我完全接受任何编程语言.我最熟悉Octave/Matlab,但涉及R,C,C++,Java.如果解决方案涉及将数据存储在数据库中,我也熟练使用SQL.我将学习任何语言 - 这些并不是我们正在寻找的复杂功能,没有与其他程序的接口等,所以不要太在意学习曲线.

所有这些都说明了什么是FOR循环中最快的编程语言？从搜索SO和Google,Fortran和C泡沫到顶部,但在潜入其中之前寻找更多建议.

谢谢!

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]有一些微观优化可能,但那些不会产生你正在寻找的加速.

Answer 2

~300k * ~150 * ~30 * ~12 = ~16G迭代,对吗？在任何体面的CPU上,任何编译语言都应该在几分钟内(如果不是几秒钟)完成这些原始操作.Fortran,C/C++几乎同样应​​该这样做.即使是托管语言,例如Java和C#,也只会略微落后(如果有的话).

如果你有一个运行55小时~16G迭代的问题,这意味着它们远非原始(每秒80k？这太荒谬了),所以也许我们应该知道更多.(正如已经建议的那样,磁盘访问限制性能？它是网络访问吗？)

Answer 3

正如@Rotsor所说,16G操作/ 55小时约为每秒80,000次操作,或每12.5微秒一次操作.这是每次操作的大量时间.

这意味着你的循环不是导致性能不佳的原因,而是在最里面的循环中花费时间.Octave是一种解释性语言.仅这一点就意味着一个数量级的减速.

如果你想要速度,首先需要使用编译语言.然后,您需要进行性能调整(也称为分析),或者只需在指令级别的调试器中单步执行.这将告诉你它在心中的实际行动.一旦你把它带到不浪费周期的地方,更漂亮的硬件,内核,CUDA等将为你带来并行性加速.但是,如果您的代码花费了不必要的多个周期,那就太愚蠢了.(这是一个性能调整的例子 - 通过修剪脂肪来加速43倍.)

我无法相信响应者谈论matlab,APL和其他矢量化语言的数量.那些是口译员.他们给你简洁的源代码,这是不是在所有同样的事情,快执行.当涉及到裸机时,它们会被硬件与其他语言卡在一起.

补充:为了向您展示我的意思,我只是在这台发霉的旧笔记本电脑上运行了这个16G操作的C++代码,它花了94秒,或者每次迭代大约6ns.(我不敢相信你宝贝 - 整整2天都坐了那个东西.)

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

Answer 4

就绝对速度而言，可能是 Fortran 其次是 C，其次是 C++。在实际应用中，用这三种语言中的任何一种编写良好的代码，使用下降编译器编译应该会非常快。

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

举个例子，在我最近正在进行的一个项目中，数据大小和操作大约是您在这里讨论的大小的 3/4，但是像您的代码一样，矢量化的空间很小，并且需要大量循环播放。将代码从 matlab 转换为 C++ 后，运行时间从 16-18 小时减少到大约 25 分钟。