14

下面mapAndSum代码块中的函数结合了mapand sum(别介意sum在主函数中应用了另一个,它只是为了使输出紧凑)。是惰性计算的map,而sum是使用累加参数计算的。这个想法是,map可以在内存中没有完整列表的情况下使用结果,并且(仅)之后sum可以“免费”使用。main 函数表明我们在调用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调用都携带对整个对的引用,这导致整个列表被保存在内存中。

我们(我的同事 Toni Dietze 和我)使用明确的case声明(比较“bad”与“good2”)解决了这个问题。顺便说一句,发现这一点花了我们相当多的时间..!

现在,我们不明白的是两个方面:

  • 为什么mapAndSum首先工作?它还使用了一种无可辩驳的模式,因此它也应该将整个列表保存在内存中,但显然不是。并且将 the 转换let为 acase会使函数表现得完全不懒惰(以至于堆栈溢出;没有双关语的意思)。

    我们查看了 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."
4

1 回答 1

18

让我首先回答为什么mapAndSome可以很好地工作:你看到的(很可能)是 Philip Wadler 在“<a href="http://homepages.inf.ed.ac.uk/wadler /topics/garbage-collection.html" rel="noreferrer">使用垃圾收集器修复一些空间泄漏”。简短摘要:如果垃圾收集器看到表单的 thunkfst x并且x已经对元组构造函数进行了评估,例如(y,z),它将替换fst x为,如果没有在其他任何地方引用它y可能会释放。z

在您的代码中s',一旦将结果go评估为元组并经过一轮 GC,将不会保留对元组的引用,而是会被累积的参数替换。

现在让我们通过研究核心来看看其他模式。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"aka的代码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

via的实现使用可反驳的模式,因此会生成垃圾收集器可以很好地处理的那种选择器thunk。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 的优化)。也许它不适用于静态 thunk?事实上,如果评论是最新的,则只讨论动态分配的选择器 thunk。因此,如果您foo不是模块级值(或者更确切地说是惰性提升为一个),而是依赖于某些输入,w1_rf24则可能是动态分配的,因此有资格获得特殊处理。但是无论如何,代码可能看起来非常不同。

于 2012-07-24T08:10:41.600 回答