Как улучшить производительность теста массива в 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 запустить почти так же быстро, как и с-код (5.2s), но я особенно заинтересован в 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 У меня были проблемы, строящие последнюю версию mlton с последней версией GCC (аналогичный вопрос к что в 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()*) 

и с ++ кода:

#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, который может знать, что входные и выходные показатели находятся в пределах (вы все еще платить за «суб»)
• Использование функции типа ArraySlice.foldli, где вы также можете передавать значение из предыдущей ячейки на следующую итерацию
• Использование небезопасных доступов к массиву (если Poly/ML поддерживает его, найдите структуру «Небезопасная»).

Это может быть медленным из-за целых проверок переполнения. Здесь после каждого добавления он проверяет, не может ли результат быть представлен, а ветви - для исключения. Используя что-то вроде Word32.слово вместо int может повысить производительность. Есть также иногда флаги компилятора, чтобы отключить это, хотя это довольно опасная вещь, поскольку код других людей может зависеть от этой части языка.

Большинство этих преобразований сделают код более странным. Я думаю, что это улучшит как вашу программу, так и ее производительность, чтобы передать значение предыдущего элемента вашей функции loopI вместо того, чтобы читать ее с помощью Array.sub. У вас обычно была такая ценность.

Если вы беспокоитесь о производительности, то, тем не менее, mlton - это путь. Я использую бинарные файлы x86_64 с mingw64, и они работают для меня, включая связь с C-кодом.