Как повысить производительность массива в 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, потому что он полностью интегрируется в Windows 7 с последней версией gcc. (Инструкции по сборке polyML в Windows 7 с MSYS / MSYS2 и компилятором mccw gcc см. По адресу http://lists.inf.ed.ac.uk/pipermail/polyml/2015-August/001593.html).

В Windows 7 у меня были проблемы со сборкой последней версии mlton с последней версией gcc (проблема, аналогичная той, что описана в https://github.com/MLton/mlton/issues/61)

Код 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. Это необязательные части основы: 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.