Haskell бенчмаркинг / Оптимизация nf / whnf нестрогого сокращения - PullRequest
Новая
       40

Haskell бенчмаркинг / Оптимизация nf / whnf нестрогого сокращения

5 голосов
/ 20 октября 2011

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

У меня сложилось впечатление, что нестрогая оценка позволяет GHC объединять операции так, чтобы данные итерировались только один раз, когда все функции записаны, чтобы упорядочить аргументы для облегчения сокращения.(И чтобы потенциально сократить количество операций, выполняемых с каждым датумом)

Чтобы проверить это, я написал следующий код: 

import Criterion.Main

main = defaultMain
       [ bench "warmup (whnf)" $ whnf putStrLn "HelloWorld",
         bench "single (whnf)" $ whnf single [1..10000000],
         bench "single (nf)"   $ nf   single [1..10000000],
         bench "double (whnf)" $ whnf double [1..10000000],
         bench "double (nf)"   $ nf   double [1..10000000]]

single :: [Int] -> [Int]
single lst = fmap (* 2) lst

double :: [Int] -> [Int]             
double lst =  fmap (* 3) $ fmap (* 2) lst

Сравнительный анализ с использованием библиотеки Criterion Я получаю следующие результаты: 

benchmarking warmup (whnf)
mean: 13.72408 ns, lb 13.63687 ns, ub 13.81438 ns, ci 0.950
std dev: 455.7039 ps, lb 409.6489 ps, ub 510.8538 ps, ci 0.950

benchmarking single (whnf)
mean: 15.88809 ns, lb 15.79157 ns, ub 15.99774 ns, ci 0.950
std dev: 527.8374 ps, lb 458.6027 ps, ub 644.3497 ps, ci 0.950

benchmarking single (nf)
collecting 100 samples, 1 iterations each, in estimated 107.0255 s
mean: 195.4457 ms, lb 195.0313 ms, ub 195.9297 ms, ci 0.950
std dev: 2.299726 ms, lb 2.006414 ms, ub 2.681129 ms, ci 0.950

benchmarking double (whnf)
mean: 15.24267 ns, lb 15.17950 ns, ub 15.33299 ns, ci 0.950
std dev: 384.3045 ps, lb 288.1722 ps, ub 507.9676 ps, ci 0.950

benchmarking double (nf)
collecting 100 samples, 1 iterations each, in estimated 20.56069 s
mean: 205.3217 ms, lb 204.9625 ms, ub 205.8897 ms, ci 0.950
std dev: 2.256761 ms, lb 1.590083 ms, ub 3.324734 ms, ci 0.950

Оптимизирует ли GHC функцию "double", чтобы список использовался только один раз (* 6)?Результаты nf показывают, что это так, потому что в противном случае среднее время вычислений для «double» было бы вдвое больше, чем для «single»

Какая разница, которая заставляет версию whnf работать так быстро?Я могу только предположить, что на самом деле ничего не выполняется (ИЛИ только первая итерация сокращения)

Использую ли я даже правильную терминологию?

1 Ответ

4 голосов
/ 20 октября 2011

Рассматривая ядро ​​(промежуточный код), сгенерированное GHC с использованием опции -ddump-simpl, мы можем подтвердить, что GHC действительно объединяет два приложения map в одно (используя -O2).Соответствующие части дампа: 

Main.main10 :: GHC.Types.Int -> GHC.Types.Int
GblId
[Arity 1
 NoCafRefs]
Main.main10 =
  \ (x_a1Ru :: GHC.Types.Int) ->
    case x_a1Ru of _ { GHC.Types.I# x1_a1vc ->
    GHC.Types.I# (GHC.Prim.*# (GHC.Prim.+# x1_a1vc 2) 3)
    }

Main.double :: [GHC.Types.Int] -> [GHC.Types.Int]
GblId
[Arity 1
 NoCafRefs
 Str: DmdType S]
Main.double =
  \ (lst_a1gF :: [GHC.Types.Int]) ->
    GHC.Base.map @ GHC.Types.Int @ GHC.Types.Int Main.main10 lst_a1gF

Обратите внимание, что есть только одно использование GHC.Base.map в Main.double, ссылаясь на комбинированную функцию Main.main10, которая добавляет 2 и умножает на 3.Это, вероятно, является результатом того, что GHC сначала вставил экземпляр Functor для списков, так что fmap становится map, а затем применяет правило перезаписи , которое позволяет объединить два приложения mapплюс еще несколько встроенных и других оптимизаций.

WHNF означает, что выражение вычисляется только для «самого внешнего» конструктора данных или лямбда-выражения.В данном случае это означает первый конструктор (:).Вот почему это намного быстрее, так как работа почти не выполняется.См. Мой ответ на Что такое нормальная форма слабой головы? для получения более подробной информации.

...