performance - 展开器与 zipWith 的效率

Question

在代码审查中，我回答了一个关于 naive Haskell fizzbuzz solution 的问题。通过建议 iterates forward 的实现，避免了增加素数的二次成本和(几乎)完全丢弃模除法。这是代码:

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 version 是对这段代码的明显、简单的修改，所以我不会在这里输入它，除非寻求回答我的问题的人坚持认为这很重要(代码审查中的 OP 没有剧透)。但我确实对 unfoldr 的相对效率有疑问。与 zipWith 相比的解决方案一。虽然我不再是 Haskell 新手，但我也不是 Haskell 内部结构方面的专家。

一个 unfoldr解决方案不需要 [start..]无限列表，因为它可以简单地从 start 展开.我的想法是

zipWith解决方案不会记住 [start..] 的每个连续元素正如它所要求的那样。每个元素都被使用和丢弃，因为没有保留对 [start..] 头部的引用。所以没有比 unfoldr 更多的内存消耗。 .

对 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作为“worker”和“wrapper”，新代码允许 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 库中使用)的想法是，如果列表由“好的生产者”生成，则由“好的转换器”转换，并被“好消费者”消费，那么列表 conses 根本不需要分配。老 unfoldr不是一个好的制作人，所以如果你制作了一个带有 unfoldr 的列表并将其与 foldr 一起使用，随着计算的进行，列表的各个部分将被分配(并立即变成垃圾)。现在， unfoldr是一个很好的生产者，所以你可以写一个循环，比如说， unfoldr , filter , 和 foldr ，而不是(必然)分配任何内存。

例如，给定上述 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 }
    }

没有列表，没有 Maybe s，没有对；它执行的唯一分配是 Int用于存储最终结果( I# 到 ww2_s1oT 的应用)。可以合理地预期整个计算将在机器寄存器中执行。
zipWith zipWith有一个奇怪的故事。它有点笨拙地适合折叠/构建框架(我相信它在流融合方面工作得更好)。可以制作 zipWith fuse 与它的第一个或第二个列表参数，并且多年来，列表库试图使其与其中任何一个融合，如果其中一个是一个好的生产者。不幸的是，使其与第二个列表参数融合可能会使程序在某些情况下的定义更少。即，使用 zipWith 的程序在没有优化的情况下编译时可以正常工作，但在使用优化编译时会产生错误。这不是一个很好的情况。因此，截至 base-4.8 , zipWith不再尝试与它的第二个列表参数融合。如果你想让它与一个好的生产者融合，那个好的生产者最好在第一个列表参数中。

具体来说， zipWith 的引用实现导致期望，例如， zipWith (+) [1,2,3] (1 : 2 : 3 : undefined)会给 [2,4,6] ，因为它一到达第一个列表的末尾就停止了。与之前的 zipWith实现，如果第二个列表看起来像这样，但由一个好的生产者制作，并且如果 zipWith碰巧与它融合而不是第一个列表，然后它就会繁荣起来。