Неопровержимый шаблон не пропускает память при рекурсии, но почему?

Question

mapAndSum Функция в блоке кода полностью объединяет map а также sum (не бери в голову, что другой sum применяется в основной функции, она просто служит для того, чтобы сделать вывод компактным). map вычисляется лениво, а sum вычисляется с использованием накопительного параметра. Идея состоит в том, что результатом map можно использовать, не имея полного списка в памяти, и (только) после этого sum доступно "бесплатно". Основная функция указывает, что у нас была проблема с неопровержимыми образцами при вызове mapAndSum, Позвольте мне объяснить эту проблему.

Согласно стандарту Haskell, пример неопровержимого образца let (xs, s) = mapAndSum ... in print xs >> print s переводится на

(\ v ->    print (case v of { (xs, s) -> xs })
        >> print (case v of { (xs, s) -> s }))
$ mapAndSum ...

И, следовательно, оба print вызовы содержат ссылку на всю пару, что приводит к тому, что весь список хранится в памяти.

Мы (мой коллега Тони Дитце и я) решили это с помощью явного case утверждение (сравните "плохо" против "хорошо2"). Кстати, выяснение этого заняло у нас значительное количество времени..!

Теперь то, что мы не понимаем, состоит из двух частей:

• Почему mapAndSum работа в первую очередь? Он также использует неопровержимый шаблон, поэтому он также должен хранить весь список в памяти, но это явно не так. И преобразование let в case заставит функцию вести себя совершенно неинформативно (до такой степени, что стек переполняется; каламбур не предназначен).

  Мы взглянули на "основной" код, сгенерированный GHC, но насколько мы могли его интерпретировать, он фактически содержал тот же перевод let как тот, что выше. Так что здесь нет никакой подсказки, а больше путаницы.

• Почему "плохо"? работать при выключенной оптимизации, а не при включенной?

Одно замечание, касающееся нашего фактического приложения: мы хотим добиться потоковой обработки (преобразования формата) большого текстового файла, в то же время накапливая некоторое значение, которое затем записывается в отдельный файл. Как указано, мы добились успеха, но эти два вопроса остаются, и ответы могут улучшить наше понимание GHC для предстоящих задач и проблем.

Спасибо!

{-# LANGUAGE BangPatterns #-}

-- Tested with The Glorious Glasgow Haskell Compilation System, version 7.4.2.

module Main where


import Control.Arrow (first)
import Data.List (foldl')
import System.Environment (getArgs)


mapAndSum :: Num a => (a -> b) -> [a] -> ([b], a)
mapAndSum f = go 0
  where go !s (x : xs) = let (xs', s') = go (s + x) xs in (f x : xs', s')
                       -- ^ I have no idea why it works here. (TD)
        go !s []       = ([], s)


main :: IO ()
main = do
  let foo  = mapAndSum (^ (2 :: Integer)) [1 .. 1000000 :: Integer]
  let sum' = foldl' (+) 0
  args <- getArgs
  case args of
    ["bad" ]  -> let (xs, s) = foo in print (sum xs) >> print s
    ["bad?"]  -> print $ first sum' $ foo
              -- ^ Without ghc's optimizer, this version is as memory
              -- efficient as the “good” versions
              -- With optimization “bad?” is as bad as “bad”. Why? (TD)
    ["good1"] -> print $ first' sum' $ foo
                   where first' g (x, y) = (g x, y)
    ["good2"] -> case foo of
                    (xs, s) -> print (sum' xs) >> print s
    ["good3"] -> (\ (xs, s) -> print (sum' xs) >> print s) $ foo
    _ -> error "Sorry, I do not understand."

Answer 1

Позвольте мне сначала ответить, почему mapAndSome может работать хорошо вообще: вы видите (очень вероятно) эффект оптимизации, описанный Филипом Уодлером в " Устранении некоторых утечек пространства с помощью сборщика мусора". Краткое резюме: Если сборщик мусора видит стук формы fst x а также x уже оценивается для конструктора кортежа, например (y,z)заменит fst x от yвозможно освобождая z если это не упоминается где-либо еще.

В вашем коде s' будет, как только результат go оценивается как кортеж, и после одного раунда GCing не сохраняет ссылку на кортеж, но будет заменен накопленным параметром.

Теперь давайте рассмотрим другие закономерности, исследуя ядро. foo привязка компилируется в:

foo_r2eT :: ([Type.Integer], Type.Integer)

foo_r2eT =
  case $wgo_r2eP mapAndSum1 lvl2_r2eS
  of _ { (# ww1_s2d7, ww2_s2d8 #) ->
  (ww1_s2d7, ww2_s2d8)
  }

Вот код в "bad" дело (lvl18_r2fd плохо"):

case eqString ds_dyA lvl18_r2fd of _ {
  False -> $wa_s2da new_s_a14o;
  True ->
    case ds1_dyB of _ {
      [] ->
        case Handle.Text.hPutStr2
               Handle.FD.stdout lvl17_r2fc True new_s_a14o
        of _ { (# new_s1_X15h, _ #) ->
        Handle.Text.hPutStr2
          Handle.FD.stdout lvl16_r2fb True new_s1_X15h
        };
      : ipv_sIs ipv1_sIt -> $wa_s2da new_s_a14o
    }

Мы видим, что два значения на уровне модуля печатаются, lvl17_r2fc а также lvl16_r2fbвот их код:

lvl17_r2fc :: String
[GblId]
lvl17_r2fc =
  case foo_r2eT of _ { (xs_Xqp, s_Xq9) ->
  $w$cshowsPrec
    0
    (Data.List.sum_sum' xs_Xqp Data.List.genericDrop2)
    ([] @ Char)
  }

lvl16_r2fb :: String
[GblId]
lvl16_r2fb =
  case foo_r2eT of _ { (xs_apS, s_Xqp) ->
  $w$cshowsPrec 0 s_Xqp ([] @ Char)
  }

Почему они связаны на уровне модуля, а не внутри выражения? Это эффект ленивого подъема, еще одна оптимизация, которая увеличивает совместное использование и, следовательно, иногда оказывает негативное влияние на космические характеристики. См. Билет GHC 719 для другого случая этого эффекта.

Так что же происходит, что оценка lvl17_r2fc причины foo оценивать, а левая запись лениво печатается. К несчастью, lvl16_r2fb все еще жив и сохраняет полный кортеж. И поскольку сборщик мусора (кажется) не видит, что это селектор, оптимизация Wadler не срабатывает.

Напротив, вот код для "good1" ака lvl8_r2f1:

            case eqString ds_dyA lvl8_r2f1 of _ {
              False -> $wa2_s2dI w3_s2cF;
              True ->
                case ds1_dyB of _ {
                  [] ->
                    Handle.Text.hPutStr2
                      Handle.FD.stdout lvl7_r2f0 True w3_s2cF;
                  : ipv_sHg ipv1_sHh -> $wa2_s2dI w3_s2cF
                }
            } } in

где напечатанное значение - эта строка:

lvl7_r2f0 :: String
[GblId]
lvl7_r2f0 =
  case foo_r2eT of _ { (x_af6, y_af7) ->
  show_tuple
    (:
       @ ShowS
       (let {
          w2_a2bY [Dmd=Just L] :: Type.Integer

          w2_a2bY = lgo_r2eU mapAndSum1 x_af6 } in
        \ (w3_a2bZ :: String) ->
          $w$cshowsPrec 0 w2_a2bY w3_a2bZ)
       (:
          @ ShowS
          (\ (w2_a2bZ :: String) ->
             $w$cshowsPrec 0 y_af7 w2_a2bZ)
          ([] @ ShowS)))
    ([] @ Char)
  }

Как видите, кортеж разбирается только один раз, и используются оба значения. Так что ничто не относится к кортежу в целом, и это может быть сборкой мусора. Аналогично для "good2" а также "good3",

Сейчас "bad?"В неоптимизированном случае мы получаем этот код:

 case eqString ds_dyA (unpackCString# "bad?")
                 of _ {
                   False -> fail2_dyN realWorld#;
                   True ->
                     case ds1_dyB of _ {
                       [] ->
                         $
                           @ (Type.Integer, Type.Integer)
                           @ (IO ())
                           (System.IO.print
                              @ (Type.Integer, Type.Integer) $dShow_rzk)
                           ($
                              @ ([Type.Integer], Type.Integer)
                              @ (Type.Integer, Type.Integer)
                              (Control.Arrow.first
                                 @ (->)
                                 Control.Arrow.$fArrow(->)
                                 @ [Type.Integer]
                                 @ Type.Integer
                                 @ Type.Integer
                                 sum'_rzm)
                              foo_rzl);
                       : ipv_szd ipv1_sze -> fail2_dyN realWorld#
                     }
                 } } in

Реализация first с помощью *** использует шаблоны, которые можно опровергнуть, поэтому генерируется тот тип селектора, который хорошо обрабатывает сборщик мусора.

В оптимизированном случае все немного разбросано, но в любом случае вот соответствующий код (последнее значение - это тот, который печатается):

w_r2f2 :: Type.Integer

w_r2f2 =
  case foo_r2eT of _ { (x_aI1, y_aI2) ->
  lgo_r2eU mapAndSum1 x_aI1
  }

lvl9_r2f3 :: String -> String
[GblId, Arity=1]
lvl9_r2f3 =
  \ (w2_a2bZ :: String) ->
    $w$cshowsPrec 0 w_r2f2 w2_a2bZ

w1_r2f4 :: Type.Integer

w1_r2f4 = case foo_r2eT of _ { (x_aI6, y_aI7) -> y_aI7 }

lvl10_r2f5 :: String -> String
[GblId, Arity=1]
lvl10_r2f5 =
  \ (w2_a2bZ :: String) ->
    $w$cshowsPrec 0 w1_r2f4 w2_a2bZ

lvl11_r2f6 :: [ShowS]
[GblId]
lvl11_r2f6 =
  :
    @ ShowS lvl10_r2f5 ([] @ ShowS)

lvl12_r2f7 :: [ShowS]
[GblId]
lvl12_r2f7 = : @ ShowS lvl9_r2f3 lvl11_r2f6

lvl13_r2f8 :: ShowS
[GblId]
lvl13_r2f8 = show_tuple lvl12_r2f7

lvl14_r2f9 :: String
[GblId]
lvl14_r2f9 = lvl13_r2f8 ([] @ Char)

Использование first был встроен. Мы видим два звонка case foo_r2eT, так что это склонно к утечке пространства, несмотря на w1_rf24 выглядит как селектор (поэтому я ожидаю, что среда выполнения применит оптимизацию Wadler). Может быть, это не работает для статических громов? В самом деле, комментарий, если он актуален, говорит только о динамических выделенных блоках селектора. Так что если ваш foo не были значением уровня модуля (или, скорее, ленивым в одном), а скорее зависели от некоторого ввода, w1_rf24 может быть динамически распределен и, следовательно, имеет право на специальный режим. Но тогда код может выглядеть совсем иначе.