Как повысить производительность массива в PolyML?
У меня есть следующий тест, который перебирает массив,
установка следующей записи на один плюс предыдущая запись. Если
число становится больше определенного предела, я установил запись
в ноль, и продолжить. Затем в конце я суммирую записи
в массиве.
Вопрос: как я могу улучшить результаты тестов для 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, потому что
он легко интегрируется в 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 ()*)
и код 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;
}
Решение
Я не думаю, что с вашей программой что-то не так. По моему опыту, mlton — самый эффективный компилятор SML с большим отрывом, особенно для «C-подобного» кода.
Вот несколько способов написать это по-другому, что может помочь компилятору работать лучше:
Возможно, что Poly / ML упаковывает каждый элемент массива. Бокс означает выделение объекта, который содержит целочисленное значение, а не просто сохранение плоского массива целых чисел. Это очень дорого: у вас гораздо больше выделений, косвенных ссылок, худшего локального кэша и более дорогого GC. Это своего рода фундамент для компилятора, но вы можете получить лучшую производительность, если будете использовать мономорфный массив, такой как IntArray.array или Word32Array.array. Это необязательные части Основы: http://sml-family.org/Basis/mono-array.html
Это может быть медленным из-за проверки границ. На каждой итерации цикла вы выполняете вызовы «sub» и «update», каждый из которых (наивно) проверяет соответствие аргумента размеру массива, а затем выполняет ветвь, чтобы выдать исключение, если оно выходит за пределы. Вы можете уменьшить штраф за проверку границ следующим образом:
- Использование функции, такой как Array.modifyi, которая может знать, что индексы ввода и вывода находятся в границах (вы все равно заплатите за «sub»)
- Используя такую функцию, как ArraySlice.foldli, где вы также можете передавать значение из предыдущей ячейки в следующую итерацию
- Использование небезопасного доступа к массиву (если Poly / ML поддерживает его; ищите «небезопасную» структуру).
Это может быть медленно из-за целочисленных проверок переполнения. Здесь после каждого добавления он проверяет, не может ли быть представлен результат, и выдает исключение. Использование чего-то вроде Word32.word вместо int может повысить производительность. Также иногда есть флаги компилятора для отключения этого, хотя это довольно опасная вещь, так как код других людей может зависеть от этой части языка.
Большинство из этих преобразований сделают код более странным. Я думаю, что это улучшит как вашу программу, так и ее производительность, передав значение предыдущего элемента вашей функции loopI, а не считывая его с Array.sub. Вы обычно просто имели это значение.
Если вы беспокоитесь о производительности, однако, млтон это путь. Я использую двоичные файлы x86_64 с mingw64, и они работают для меня, в том числе и для связи с кодом C.
Другие решения