如何提高 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.2 秒），但我对 PolyML 特别感兴趣，因为它在 Windows 7 中与最新版本的 gcc 无缝构建。（有关 polyML 的构建说明在 Windows 7 上使用 MSYS / MSYS2 和 mingw gcc 编译器参见 http://lists.inf.ed.ac.uk/pipermail/polyml/2015-August/001593.html)

在 windows 7 我在构建最新版本的带有最新版本 gcc 的 mlton（与中的问题类似 https://github.com/MLton/mlton/issues/61#issuecomment-50982499 )

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-like" 代码。

这里有一些不同的写法，可能有助于编译器做得更好：

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

由于边界检查，它可能会很慢。通过循环的每次迭代都会执行 "sub" 和 "update" 调用，每个调用都会（天真地）检查参数是否与数组的大小相对应，然后如果超出范围则分支以抛出异常。您可以通过以下方式减少边界检查的惩罚：

使用像 Array.modifyi 这样的函数，它可以知道输入和输出索引在范围内（您仍然需要为 "sub" 付费）
使用类似 ArraySlice.foldli 的函数，您还可以将值从前一个单元格传递到下一个迭代
使用不安全的数组访问（如果 Poly/ML 支持它；寻找 'Unsafe' 结构）。

由于整数溢出检查，它可能会很慢。在每次添加之后，它会检查结果是否无法表示，然后分支以抛出异常。使用 Word32.word 之类的东西而不是 int 可能会提高性能。有时也有用于关闭此功能的编译器标志，尽管这是一件非常危险的事情，因为其他人的代码可能依赖于这部分语言。

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

不过，如果您关心性能，那么 mlton 是您的不二之选。我将 x86_64 二进制文件与 mingw64 一起使用，它们对我有用，包括链接 C 代码。

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

How to improving array benchmark performance in PolyML?

c++

benchmarking

sml

polyml

mlton