展开效率与拉链相比

Question

在Code Review上,我回答了一个关于一个天真的Haskell fizzbuzz解决方案的问题,提出了一个向前迭代的实现,避免了越来越多的素数的二次成本和几乎完全丢弃模数除法.这是代码:

fizz :: Int -> String
fizz = const "fizz"

buzz :: Int -> String
buzz = const "buzz"

fizzbuzz :: Int -> String
fizzbuzz = const "fizzbuzz"

fizzbuzzFuncs =  cycle [show, show, fizz, show, buzz, fizz, show, show, fizz, buzz, show, fizz, show, show, fizzbuzz]

toFizzBuzz :: Int -> Int -> [String]
toFizzBuzz start count =
    let offsetFuncs = drop (mod (start - 1) 15) fizzbuzzFuncs
    in take count $ zipWith ($) offsetFuncs [start..]

作为进一步的提示,我建议使用重写它Data.List.unfoldr.该unfoldr版本是对此代码的一个明显,简单的修改,所以我不打算在这里输入它,除非那些寻求回答我的问题的人坚持认为这很重要(OP代码评论没有破坏者).但我确实对该unfoldr解决方案的相对效率提出了疑问zipWith.虽然我不再是Haskell的新手,但我并不是Haskell内部的专家.

一种unfoldr解决方案并不需要[start..]无限的名单,因为它可以简单地从展开start.我的想法是

1. 该zipWith解决方案不会[start..]按要求记忆每个连续的元素.使用和丢弃每个元素,因为不保留对[start ..]的头部的引用.因此,没有更多的内存消耗比unfoldr.
2. 关于unfoldr使其总是内联的性能和最近补丁的担忧是在我尚未达到的水平上进行的.

所以我认为这两者在内存消耗方面相当,但不了解相对性能.希望更有信息的Haskellers可以指导我理解这一点.

unfoldr用于生成序列似乎很自然,即使其他解决方案更具表现力.我只知道我需要更多地了解它的实际性能.(出于某种原因,我发现foldr在这个级别上更容易理解)

注意:在我开始调查问题(以及我完全理解的优化/内联讨论的唯一一点)之前,我unfoldr使用的Maybe是第一个潜在的性能问题.所以我能够立即停止担心Maybe(鉴于最新版本的Haskell).

Answer 1

作为一个负责近期的实施方案的变化zipWith和unfoldr,我想我也许应该采取这个刺.我不能那么容易地比较它们,因为它们是非常不同的功能,但我可以尝试解释它们的一些属性和变化的意义.

unfoldr

内联

旧版本unfoldr(之前base-4.8/ GHC 7.10)在顶级递归(它直接称自己).GHC从不内联递归函数,因此unfoldr从未内联.结果,GHC无法看到它如何与传递的功能相互作用.这个问题最令人不安的是传入的函数类型(b -> Maybe (a, b))实际上会产生Maybe (a, b)值,分配内存来保存Just和(,)构造函数.通过重构unfoldr为"工作者"和"包装器",新代码允许GHC内联它并且(在许多情况下)将其与传入的函数融合,因此额外的构造函数被编译器优化剥离.

例如,在GHC 7.10下,代码

module Blob where
import Data.List

bloob :: Int -> [Int]
bloob k = unfoldr go 0 where
  go n | n == k    = Nothing
       | otherwise = Just (n * 2, n+1)

汇编与ghc -O2 -ddump-simpl -dsuppress-all -dno-suppress-type-signatures核心

$wbloob :: Int# -> [Int]
$wbloob =
  \ (ww_sYv :: Int#) ->
    letrec {
      $wgo_sYr :: Int# -> [Int]
      $wgo_sYr =
        \ (ww1_sYp :: Int#) ->
          case tagToEnum# (==# ww1_sYp ww_sYv) of _ {
            False -> : (I# (*# ww1_sYp 2)) ($wgo_sYr (+# ww1_sYp 1));
            True -> []
          }; } in
    $wgo_sYr 0

bloob :: Int -> [Int]
bloob =
  \ (w_sYs :: Int) ->
    case w_sYs of _ { I# ww1_sYv -> $wbloob ww1_sYv }

聚变

另一个改变unfoldr是重写它以参与"折叠/构建"融合,这是GHC列表库中使用的优化框架."折叠/构建"融合和更新,不同平衡的"流融合"(在vector图书馆中使用)的想法是,如果列表是由"好的制作人"制作的,由"好的变形金刚"改造,并且被消费通过"良好的消费者",列表根本不需要实际分配.旧的unfoldr是不是一个好的制片人,所以如果你用制作的列表unfoldr,并与,比如说,它消耗foldr,列表的碎片将被分配(并立即成为垃圾)的计算进行.现在,unfoldr是一个很好的制作人,所以你可以用一个循环来编写,比方说,unfoldrfilterfoldr,而不是(必然)分配任何内存.

例如,给定上面的定义bloob,和一个严厉{-# INLINE bloob #-}(这个东西有点脆弱;好的生产者有时需要明确地内联为好),代码

hooby :: Int -> Int
hooby = sum . bloob

编译成GHC核心

$whooby :: Int# -> Int#
$whooby =
  \ (ww_s1oP :: Int#) ->
    letrec {
      $wgo_s1oL :: Int# -> Int# -> Int#
      $wgo_s1oL =
        \ (ww1_s1oC :: Int#) (ww2_s1oG :: Int#) ->
          case tagToEnum# (==# ww1_s1oC ww_s1oP) of _ {
            False -> $wgo_s1oL (+# ww1_s1oC 1) (+# ww2_s1oG (*# ww1_s1oC 2));
            True -> ww2_s1oG
          }; } in
    $wgo_s1oL 0 0

hooby :: Int -> Int
hooby =
  \ (w_s1oM :: Int) ->
    case w_s1oM of _ { I# ww1_s1oP ->
    case $whooby ww1_s1oP of ww2_s1oT { __DEFAULT -> I# ww2_s1oT }
    }

没有列表,没有Maybes,没有对; 它执行的唯一分配是Int用于存储最终结果(I#to 的应用ww2_s1oT).可以合理地期望整个计算在机器寄存器中执行.

zipWith

zipWith有一个奇怪的故事.它有点笨拙地适应折叠/构建框架(我相信它在流融合方面效果更好).有可能zipWith与它的第一个或第二个列表参数融合,并且多年来,列表库试图使它与两者融合,如果它们是一个好的生产者.不幸的是,使其与第二个列表参数融合可能会使某个程序在某些情况下更少定义.也就是说,使用的程序zipWith在没有优化的情况下编译时可以正常工作,但在使用优化编译时会产生错误.这不是一个很好的情况.因此,作为base-4.8,zipWith不再试图融合其第二个列表参数.如果你想让它与一个优秀的制作人融合,那么优秀的制作人最好是在第一个列表参数中.

具体来说,参考实现zipWith导致期望,例如,zipWith (+) [1,2,3] (1 : 2 : 3 : undefined)将给出[2,4,6],因为它一旦到达第一个列表的结尾就停止.在前面的zipWith实现中,如果第二个列表看起来像那样但是是由一个好的制作人制作的,并且如果zipWith碰巧与它融合而不是第一个列表,那么它将会蓬勃发展.