如何提高PolyML中的数组基准测试性能？

Question

我有下面的基准，它迭代一个数组，将下一个条目设置为一个加前一个条目。如果数字大于某一上限，我将条目设置为零，然后继续。最后，我对数组中的条目进行求和。

问:如何改进PolyML的基准测试结果？

“泰晤士报”在Ubuntu x86-64上的内容如下：

polyml (using CFLAGS=O3) = 
1250034994

real    0m54.207s
user    0m52.604s
sys 0m0.792s

g++ (O3) = 
1250034994

real    0m4.628s
user    0m4.578s
sys 0m0.028s

我可以让mlton运行几乎和c代码(5.2s)一样快，但我对PolyML特别感兴趣，因为它在Windows7中与最新版本gcc无缝构建。(有关在Windows 7上使用MSYS / MSYS2和mingw编译器构建MSYS2的说明，请参见http://lists.inf.ed.ac.uk/pipermail/polyml/2015-August/001593.html)

在windows 7上，我在使用最新版本的gcc (类似于https://github.com/MLton/mlton/issues/61#issuecomment-50982499中的版本)构建最新版本的mlton时遇到了问题。

SML代码是：

val size:int = 50000;
val loops:int = 30000;
val cap:int = 50000;

val data:int array = Array.array(size,0);


fun loop () = 
  let 
    fun loopI i = 
      if i = size then
        let val _ = () in
          Array.update(data,0,Array.sub(data,size-1));
          ()
        end
      else 
        let val previous = Array.sub(data,i-1) 
            val use = if previous > cap then 0 else previous in
          Array.update(data,i,use+1);
          loopI (i+1)
      end
  in loopI 1 end

fun benchmarkRun () = 
  let
    fun bench i = 
      if i = loops then ()
      else let val _ = () in 
             loop ();
             bench (i+1)
           end
  in bench 1 end

fun sum (i,value) =
  if i = size then value 
  else sum(i+1,value+Array.sub(data,i))

fun main () = let val _ = () in 
  benchmarkRun();
  print (Int.toString (sum (0,0)));
  print "\n"
  end

(*val _ = main ()*)

c++代码是：

#include <iostream>
#include <vector>
using namespace std;

int size = 50000;
int loops = 30000;
int cap = 50000;

vector<int> data(size);

void loop(){
  int previous, use;
  for(int i=1; i<size; i++){
    previous = data[i-1];
    if(previous > cap){
      use = 0;
    }else{
      use = previous;
    }
    data[i] = use + 1;
  }
  data[0] = data[size-1];
}

void benchmarkRun(){
  for(int i=1; i<loops; i++){
    loop();
  }
}

int sum(){
  int res = 0;
  for(int i=0; i<size; i++){
    res += data[i];
  }
  return res;
}

int main(){
  benchmarkRun();
  cout<<sum()<<endl;
}

Answer 1

我不认为你的节目有什么问题。在我的经验中，mlton是性能最好的SML编译器，尤其是对于“C类”代码。

以下是您可以以不同方式编写它的一些方法，这些方法可能有助于编译器更好地完成任务：

可能Poly正在对数组的每个元素进行装箱。装箱意味着分配一个包含整数值的对象，而不仅仅是存储一个平面整数数组。这是非常昂贵的:您有更多的分配，间接，更糟糕的缓存局部性，和更昂贵的GC。这对编译器来说是基本的，但是如果使用像IntArray.array或Word32Array.array这样的单形数组，可能会获得更好的性能。这些是基础的可选部分：http://sml-family.org/Basis/mono-array.html

这可能是缓慢的，因为边界检查。循环中的每一次迭代都执行一个“子”和“更新”调用，每个调用都将(天真地)检查数组大小的参数，然后分支，如果异常在外部，则抛出异常。您可以通过以下方法减少对边界检查的惩罚：

• 使用像Array.modifyi这样的函数，它可以知道输入和输出索引在范围内(您仍然需要支付"sub")
• 使用像ArraySlice.foldli这样的函数，您也可以将值从上一个单元格传递到下一个迭代。
• 使用不安全的数组访问(如果Poly/ML支持它，请查找“不安全”结构)。

由于整数溢出检查，它可能比较慢。在这里，每次添加之后，它都会检查结果是否无法表示，并在分支中抛出异常。使用像Word32.word这样的词代替int可以提高性能。有时也会有编译器标记来关闭它，尽管这是非常危险的事情，因为其他人的代码可能依赖于语言的这一部分。

大多数这些转换都会使代码看起来更奇怪。我确实认为，将前一个元素的值传递给您的loopI函数，而不是用Array.sub读取它，将会提高您的程序及其性能。你通常就是这么有价值的。

不过，如果你关心的是性能，那就该走了。我在mingw64中使用mingw64二进制文件，它们为我工作，包括针对C代码的链接。