Haskell;выполнение пункта где

Question

Я анализировал влияние предложений 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] дважды .

...

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

...

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

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

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: я нашел возможно связанный вопрос , но не совсем.

Answer 1

Вы можете проверить ядро ​​GHC, используя -ddump-simpl, и наблюдать за оптимизированным кодом, созданным GHC.Ядро не так читабельно, как на 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 = enum from to) и вызывает ++.Здесь не было никаких вставок.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
      }

Здесь первое «перечисление from» [1..n] был встроен, и это также вызвало встраивание ++.Результирующая рекурсивная функция go_a1lX опирается только на : и базовую арифметику.Когда рекурсия заканчивается, возвращается n_a1lT, что является вторым "enum from to" [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]