如何提高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特别感兴趣，因为 它使用最新版本的gcc在Windows 7中无缝地构建。 （对于MSYS/MSYS2和MinGW gcc编译器看到http://lists.inf.ed.ac.uk/pipermail/polyml/2015-August/001593.html为polyML 构建说明在Windows 7）

在Windows 7上我有问题，构建最新版本 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”代码。

下面是一些你可以写不同的方式，这可能有助于编译器做得更好：

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

由于边界检查可能会很慢。每进行一次循环迭代，你都会执行一个“sub”和“update”调用，每个调用都会（天真地）检查参数与数组大小的关系，然后在超出范围时分支引发异常。您可能能够减少从边界的点球被检查：

• 使用像Array.modifyi一个功能，它可以知道，输入和输出指数超出范围（你还是会支付“子” ）
• 使用像ArraySlice.foldli，在这里也可以从先前单元传递值到下一次迭代
• 使用不安全的数组访问（如果多晶硅/ ML支持它的功能;寻找一个“不安全”的结构）。

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

大部分这些转换都会使代码看起来更加怪异。我认为它会改善你的程序和性能，将先前的元素值传递给你的loopI函数，而不是用Array.sub读出它。你通常只有这个价值。

如果你关心性能，不过，mlton是要走的路。我在mingw64中使用x86_64二进制文件，它们适用于我，包括链接C代码。