Хаскелл; исполнение предложения where

Я анализировал влияние предложений where на производительность программ на Haskell.

В Haskell, Мастерство функционального программирования, Томпсон, глава 20.4 я нашел следующий пример:

exam1 :: Int -> [Int]
exam1 n = [1 .. n] ++ [1 .. n]

exam2 :: Int -> [Int]
exam2 n = list ++ list
  where list = [1 .. n]

и, цитирую,

Время, затрачиваемое на вычисление [exam1], будет равно O(n), а используемое пространство будет равно O(1), но нам придется вычислять выражение [1 .. n] дважды.

...

Эффект [exchange2] заключается в вычислении списка [1 .. n] один раз, так что мы сохраняем его значение после его вычисления, чтобы иметь возможность использовать его снова.

...

Если мы сохраняем что-то, ссылаясь на это в предложении where, мы должны заплатить штраф в виде места, которое оно занимает.

Поэтому я схожу с ума и думаю, что флаг -O2 должен справиться с этим и выбрать для меня наилучшее поведение. Я анализирую временную сложность этих двух примеров с помощью Criterion.

import Criterion.Main

exam1 :: Int -> [Int]
exam1 n = [1 .. n] ++ [1 .. n]

exam2 :: Int -> [Int]
exam2 n = list ++ list
  where list = [1 .. n]

m :: Int
m = 1000000

main :: IO ()
main = defaultMain [ bench "exam1" $ nf exam1 m
                   , bench "exam2" $ nf exam2 m
                   ]

Я компилирую с -O2 и нахожу:

benchmarking exam1
time                 15.11 ms   (15.03 ms .. 15.16 ms)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 15.11 ms   (15.08 ms .. 15.14 ms)
std dev              83.20 μs   (53.18 μs .. 122.6 μs)

benchmarking exam2
time                 76.27 ms   (72.84 ms .. 82.75 ms)
                     0.987 R²   (0.963 R² .. 0.997 R²)
mean                 74.79 ms   (70.20 ms .. 77.70 ms)
std dev              6.204 ms   (3.871 ms .. 9.233 ms)
variance introduced by outliers: 26% (moderately inflated)

Какая разница! С чего бы это? Я думал, что exam2 должен быть быстрее, но память неэффективна (согласно цитате выше). Но нет, на самом деле он намного медленнее (и, вероятно, больше памяти неэффективно, но это нужно проверить).

Возможно, это медленнее, потому что [1 .. 1e6] нужно хранить в памяти, а это занимает много времени. Что вы думаете?

PS: я нашел возможно, связанный с этим вопрос, но не совсем.


performance time-complexity haskell space-complexity
person Dominik Schrempf    schedule 29.04.2019    source источник
comment
Похоже, что во втором примере компилятору не удалось встроить list, поэтому он фактически вычисляет его, сохраняет в памяти и читает из памяти.   -  person talex    schedule 29.04.2019
comment
@talex Встраивание let x = expensiveComputation in f x x в общем случае может быть вредным, поскольку может привести к двойному вычислению x. Используя where, у нас может быть аналогичная проблема. Я думаю, что GHC довольно консервативен в отношении встраивания в этом случае, поскольку это может привести к проблемам с производительностью (например, выполнение двух рекурсивных вызовов вместо одного может привести к экспоненциальному взрыву).   -  person chi    schedule 29.04.2019
comment
@chi да, но в этом случае встраивание вообще не приводит к вычислениям. Он будет вычисляться на лету.   -  person talex    schedule 29.04.2019
comment
@talex Я согласен, но я не ожидаю, что GHC поймет, что в этом случае он может безопасно встраиваться. Определение того, когда можно, а когда нельзя встроить, выглядит нетривиально.   -  person chi    schedule 29.04.2019

Ответы (1)


arrow_upward
6
arrow_downward

Вы можете проверить GHC Core с помощью -ddump-simpl и просмотреть оптимизированный код, созданный GHC. Core не так читабелен, как Haskell, но обычно можно понять, что происходит.

Для exam2 получаем обычный скучный код:

exam2
  = \ (n_aX5 :: Int) ->
      case n_aX5 of { GHC.Types.I# y_a1lJ ->
      let {
        list_s1nF [Dmd=<S,U>] :: [Int]
        [LclId]
        list_s1nF = GHC.Enum.eftInt 1# y_a1lJ } in
      ++ @ Int list_s1nF list_s1nF
      }

Грубо говоря, это определяет list_s1nF как [1..n] (eftInt = перечисление от до) и вызывает ++. Здесь не произошло встраивания. GHC боялся встраивать list_s1nF, так как он используется дважды, а встраивание определения в таком случае может быть вредным. Действительно, если let x = expensive in x+x встроено, expensive может быть пересчитано дважды, что плохо. Здесь GHC доверяет программисту, думая, что если он использовал let / where, то хочет, чтобы он вычислялся только один раз. Отсутствие встроенного list_s1nF предотвращает дальнейшую оптимизацию.

Таким образом, этот код выделяет list = [1..n], а затем копирует его, что приводит к 1:2:...:n:list, где хвостовой указатель сделан так, чтобы указывать на исходный список. Копирование произвольного списка требует следования цепочке указателей и выделения ячеек для нового списка, что интуитивно дороже, чем [1..n], которому нужно только выделить ячейки для нового списка и сохранить счетчик.

Вместо этого exam1 оптимизирован гораздо дальше: после небольшой распаковки

exam1
  = \ (w_s1os :: Int) ->
      case w_s1os of { GHC.Types.I# ww1_s1ov ->
      PerfList.$wexam1 ww1_s1ov
      }

мы получаем фактическую рабочую функцию.

PerfList.$wexam1
  = \ (ww_s1ov :: GHC.Prim.Int#) ->
      let {
        n_a1lT :: [Int]
        [LclId]
        n_a1lT = GHC.Enum.eftInt 1# ww_s1ov } in
      case GHC.Prim.># 1# ww_s1ov of {
        __DEFAULT ->
          letrec {
            go_a1lX [Occ=LoopBreaker] :: GHC.Prim.Int# -> [Int]
            [LclId, Arity=1, Str=<L,U>, Unf=OtherCon []]
            go_a1lX
              = \ (x_a1lY :: GHC.Prim.Int#) ->
                  GHC.Types.:
                    @ Int
                    (GHC.Types.I# x_a1lY)
                    (case GHC.Prim.==# x_a1lY ww_s1ov of {
                       __DEFAULT -> go_a1lX (GHC.Prim.+# x_a1lY 1#);
                       1# -> n_a1lT
                     }); } in
          go_a1lX 1#;
        1# -> n_a1lT
      }

Здесь было встроено первое «перечисление от до» [1..n], и это также вызвало встраивание ++. Полученная рекурсивная функция go_a1lX опирается только на : и базовую арифметику. Когда рекурсия завершена, возвращается n_a1lT, который является вторым "перечислением от до" [1..n]. Это не встроено, так как больше не будет запускаться оптимизация.

Здесь список не создается, а затем копируется, поэтому мы получаем лучшую производительность.

Обратите внимание, что это также создает оптимизированный код:

exam3 :: Int -> [Int]
exam3 n = list1 ++ list2
  where list1 = [1 .. n]
        list2 = [1 .. n]

а также это, поскольку GHC не будет автоматически кэшировать результат функций, поэтому их можно встроить.

exam4 :: Int -> [Int]
exam4 n = list () ++ list ()
  where list () = [1 .. n]
person chi    schedule 29.04.2019
comment
Благодарю вас! Каково ваше мнение относительно использования предложений let/where? Я часто использую их в ситуациях, когда присвоение имен подвыражениям полезно для удобочитаемости и уменьшения избыточности кода; и в этих случаях я вообще не думаю о производительности (на самом деле я думал, что использование where в exam2 приведет к выигрышу в скорости). Или есть способ написать более читаемый и менее избыточный код (например, экзамен2), который работает так же быстро, как экзамен1? - person Dominik Schrempf; 30.04.2019
comment
@DominikSchrempf Я использую let/where, чтобы сначала структурировать код для удобства чтения. Затем, если производительность вызывает беспокойство, я могу внести некоторые коррективы. Если let x = ... используется только один раз, нет никакой разницы, и компилятор, вероятно, встроит его. Если она используется дважды или более, нужно спросить себя, хочу ли я, чтобы эта информация сохранялась и использовалась повторно? или дешевле его пересчитать?. Обычно, если x имеет фиксированный размер памяти (например, это одно целое число), лучше использовать его повторно. Если вместо этого это список/дерево/что угодно, это зависит. В вашем коде я мог бы использовать [1..n]++[1..n], exam3 или exam4 выше. - person chi; 30.04.2019
comment
@DominikSchrempf Производительность Haskell, по общему признанию, является чем-то вроде черной магии. Не так очевидно увидеть, что происходит, поскольку оптимизатор может либо сделать большую работу, либо неожиданно не сделать этого. Лень также затрудняет оценку производительности. Тем не менее, с некоторым опытом можно быстро узнать о наиболее распространенных ловушках производительности и о том, как их избежать. Например. известно, что если вы часто используете ++, передавая большие списки в качестве первого аргумента, особенно рекурсивно, вероятно, лучше использовать списки различий вместо простых списков. - person chi; 30.04.2019