Выполнение эффективных чисел в Haskell

Меня вдохновил этот пост под названием " Только интересные языки интересны", чтобы посмотреть на предлагаемую им проблему (суммируя пару миллион чисел от вектора) в Haskell и сравнить его результаты.

Я новичок Haskell, поэтому я действительно не знаю, как правильно правильно или как это сделать эффективно, моя первая попытка этой проблемы заключалась в следующем. Обратите внимание, что я не использую случайные числа в векторе, так как я не уверен, как это сделать в хорошем смысле. Я также печатаю материал, чтобы обеспечить полную оценку.

import System.TimeIt

import Data.Vector as V

vector :: IO (Vector Int)
vector = do
  let vec = V.replicate 3000000 10
  print $ V.length vec
  return vec

sumit :: IO ()
sumit = do
  vec <- vector
  print $ V.sum vec

time = timeIt sumit

Загрузив это в GHCI и запустив time, я скажу, что для запуска на 3 миллиона номеров потребовалось около 0,22, а для 30 миллионов номеров - 2,69 с.

По сравнению с результатами авторов блога 0.02s и 0.18s в Lush это намного хуже, что заставляет меня думать, что это можно сделать лучше.

Примечание. Для выполнения вышеуказанного кода требуется пакет TimeIt. cabal install timeit получит его для вас.

Ответы

Ответ 1

Прежде всего, поймите, что GHCi - это интерпретатор, и он не разработан очень быстро. Чтобы получить более полезные результаты, вы должны скомпилировать код с включенными оптимизациями. Это может иметь огромное значение.

Кроме того, для любого серьезного бенчмаркинга кода Haskell я рекомендую использовать criterion. Он использует различные статистические методы для обеспечения надежных измерений.

Я изменил ваш код на использование критерия и удалил инструкции печати, чтобы мы не синхронизировали ввод-вывод.

import Criterion.Main
import Data.Vector as V

vector :: IO (Vector Int)
vector = do
  let vec = V.replicate 3000000 10
  return vec

sumit :: IO Int
sumit = do
  vec <- vector
  return $ V.sum vec

main = defaultMain [bench "sumit" $ whnfIO sumit]

Компилируя это с помощью -O2, я получаю этот результат на довольно медленном нетбуке:

$ ghc --make -O2 Sum.hs
$ ./Sum 
warming up
estimating clock resolution...
mean is 56.55146 us (10001 iterations)
found 1136 outliers among 9999 samples (11.4%)
  235 (2.4%) high mild
  901 (9.0%) high severe
estimating cost of a clock call...
mean is 2.493841 us (38 iterations)
found 4 outliers among 38 samples (10.5%)
  2 (5.3%) high mild
  2 (5.3%) high severe

benchmarking sumit
collecting 100 samples, 8 iterations each, in estimated 6.180620 s
mean: 9.329556 ms, lb 9.222860 ms, ub 9.473564 ms, ci 0.950
std dev: 628.0294 us, lb 439.1394 us, ub 1.045119 ms, ci 0.950

Итак, я получаю среднее значение чуть более 9 мс со стандартным отклонением меньше миллисекунды. Для более крупного теста я получаю около 100 мс.

Включение оптимизаций особенно важно при использовании пакета vector, поскольку он сильно использует потоковое объединение, которое в этом случае полностью исключает структуру данных, превращая вашу программу в эффективный, плотный цикл.

Также может быть целесообразно поэкспериментировать с новым генератором кода на основе LLVM, используя опцию -fllvm. Он, по-видимому, хорошо подходит для числового кода.

Ответ 2

Исходный файл, не скомпилированный, затем скомпилированный без оптимизации, затем скомпилированный с простым флагом оптимизации:

$ runhaskell boxed.hs  
3000000
30000000
CPU time:   0.35s

$ ghc --make boxed.hs -o unoptimized 
$ ./unoptimized
3000000
30000000
CPU time:   0.34s



$ ghc --make -O2 boxed.hs 
$ ./boxed
3000000
30000000
CPU time:   0.09s

Ваш файл с import qualified Data.Vector.Unboxed as V вместо import qualified Data.Vector as V (Int - тип unboxable) - сначала без оптимизации, а затем:

$ ghc --make unboxed.hs -o unoptimized
$ ./unoptimized
3000000
30000000
CPU time:   0.27s


$ ghc --make -O2 unboxed.hs 
$ ./unboxed
3000000
30000000
CPU time:   0.04s

Итак, скомпилируйте, оптимизируйте... и по возможности используйте Data.Vector.Unboxed

Ответ 3

Попробуйте использовать unboxed vector, хотя я не уверен, делает ли он заметную разницу в этом случае. Отметим также, что сравнение немного несправедливо, потому что векторный пакет должен полностью оптимизировать вектор цели (эта оптимизация называется потоковым слиянием).

Ответ 4

Если вы используете достаточно большие векторы, Vector Unboxed может стать непрактичным. Для меня чистые (ленивые) списки быстрее, если размер векторa > 50000000:

import System.TimeIt

sumit :: IO ()
sumit = print . sum $ replicate 50000000 10

main :: IO ()
main = timeIt sumit

Я получаю следующее:

Unboxed Vectors
CPU time:   1.00s

List:
CPU time:   0.70s

Изменить. Я повторил критерий с использованием критерия и сделал sumit чистым. Код и результаты:

код:

import Criterion.Main

sumit :: Int -> Int
sumit m = sum $ replicate m 10

main :: IO ()
main = defaultMain [bench "sumit" $ nf sumit 50000000]

Результаты:

warming up
estimating clock resolution...
mean is 7.248078 us (80001 iterations)
found 24509 outliers among 79999 samples (30.6%)
  6044 (7.6%) low severe
  18465 (23.1%) high severe
estimating cost of a clock call...
mean is 68.15917 ns (65 iterations)
found 7 outliers among 65 samples (10.8%)
  3 (4.6%) high mild
  4 (6.2%) high severe

benchmarking sumit
collecting 100 samples, 1 iterations each, in estimated 46.07401 s
mean: 451.0233 ms, lb 450.6641 ms, ub 451.5295 ms, ci 0.950
std dev: 2.172022 ms, lb 1.674497 ms, ub 2.841110 ms, ci 0.950

Похоже, что print имеет большое значение, как и следовало ожидать!