Делаем эффективные числа в Хаскеле - PullRequest
Новая
       17

Делаем эффективные числа в Хаскеле

11 голосов
/ 01 декабря 2011

Меня вдохновил этот пост под названием " Интересны только быстрые языки ", чтобы посмотреть на предложенную им проблему (суммируя пару миллионов чисел из вектора) в 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 говорит мне, что потребовалось около 0,22 с для 3 миллионов номеров и 2,69 для 30 миллионов.

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

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

Ответы [ 4 ]

23 голосов
/ 01 декабря 2011

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

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

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

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, поскольку он интенсивно использует stream fusion , который в этомcase может полностью исключить структуру данных, превратив вашу программу в эффективный, плотный цикл.

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

14 голосов
/ 01 декабря 2011

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

$ 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 - это тип без коробки) - сначала без оптимизации потом с: 

$ 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 голосов
/ 01 декабря 2011

Если вы используете достаточно большие векторы, Vector Unboxed может оказаться непрактичным.Для меня чистые (ленивые) списки быстрее, если размер вектора> 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 имеет большое значение, как и следовало ожидать!

3 голосов
/ 01 декабря 2011

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

...