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

Question

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

У меня сложилось впечатление, что нестрогая оценка позволяет 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 настолько быстрой? Я могу только предположить, что на самом деле ничего не выполняется (ИЛИ только первая итерация сокращения)

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

Answer 1

Рассматривая ядро ​​(промежуточный код), сгенерированный 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 означает, что выражение вычисляется только для "самого внешнего" конструктора данных или лямбда-выражения. В этом случае это означает, что первый (:) конструктор. Вот почему это намного быстрее, так как работа почти не выполняется. Смотрите мой ответ на вопрос " Что такое нормальная форма слабой головы?" Больше подробностей.