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

Question

我有下面的基准测试迭代数组，将下一项设置为1加上前一项。如果当数字大于某个上限时，我设置条目到零，然后继续。最后我把所有的项加起来

问题:我怎样才能提高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特别感兴趣，因为它可以与最新版本的gcc在Windows 7中无缝构建。(对于构建指令的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"代码。

这里有一些你可以用不同的方式来写它，可能会帮助编译器做得更好:

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

由于边界检查，它可能很慢。在循环的每次迭代中，你都会调用"sub"one_answers"update"，它们都会(天真地)检查参数是否与数组的大小相匹配，然后如果超出了边界，就会抛出异常。您可以通过以下方式减少边界检查的惩罚:

• 使用Array之类的函数。modifyi，它可以知道输入和输出索引是有界限的(你仍然要为"sub"付费)
• 使用像ArraySlice这样的函数。foldli，在这里您还可以将上一个单元格的值传递给下一次迭代
• 使用不安全的数组访问(如果Poly/ML支持);查找"不安全"结构)。

由于整数溢出检查，它可能很慢。在每次添加之后，它都会检查结果是否无法表示，并进行分支以抛出异常。用Word32之类的东西。Word而不是int可能会提高性能。有时也有编译器标志来关闭它，尽管这样做是相当危险的，因为其他人的代码可能依赖于语言的这一部分。

大多数这些转换将使代码看起来更奇怪。我确实认为将前一个元素的值传递给循环函数而不是用Array.sub读取它会改善程序及其性能。你通常只有这个值

如果你关心性能，那么mlton是一个不错的选择。我在mingw64中使用x86_64二进制文件，它们为我工作，包括与C代码的链接。