如何提高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代碼。