优化Haskell中的部分计算

Question

我很好奇如何优化这段代码:

fun n = (sum l, f $ f0 l, g $ g0 l)
  where l = map h [1..n]

假设f,f0,g,g0,和h都是昂贵的,但创建和存储l是非常昂贵的.

如上所述,l存储直到返回的元组被完全评估或垃圾收集.取而代之的是,length l,f0 l,和g0 l都应该只要其中任何一个被执行,但执行f和g应被延迟.

看来这种行为可以通过写:

fun n = a `seq` b `seq` c `seq` (a, f b, g c)
  where
    l = map h [1..n]
    a = sum l
    b = inline f0 $ l
    c = inline g0 $ l

或者非常相似:

fun n = (a,b,c) `deepSeq` (a, f b, g c)
  where ...

我们也许可以指定一堆内部类型来实现相同的效果,这看起来很痛苦.还有其他选择吗？

另外,我明明跟我的希望inlines表示编译器的保险丝sum,f0和g0成一个单一循环,构建和消费l的长期项.我可以通过手动内联来明确这一点,但那很糟糕.有没有办法明确阻止列表l被创建和/或强制内联？编译过程中如果内联或融合失败会产生警告或错误的编剧可能呢？

顺便说一句,我很好奇,为什么seq,inline,lazy等等都定义为通过let x = x in x中拉开序幕.这只是给他们一个编译器的定义来覆盖？

Answer 1

如果你想确定的话，唯一的方法就是你自己去做。对于任何给定的编译器版本，您可以尝试几种源公式并检查生成的核心/程序集/llvm 字节码/无论它是否满足您的要求。但随着每个新的编译器版本的出现，这种情况可能会被打破。

如果你写

fun n = a `seq` b `seq` c `seq` (a, f b, g c)
  where
    l = map h [1..n]
    a = sum l
    b = inline f0 $ l
    c = inline g0 $ l

或其deepseq版本，编译器可能能够合并 的计算a，b并c在 的单次遍历期间并行执行（不是并发意义上的）l，但目前，我相当相信 GHC 不会' t，如果 JHC 或 UHC 这样做，我会感到惊讶。为此，计算结构b需要c足够简单。

跨编译器和编译器版本可移植地获得所需结果的唯一方法是您自己完成。至少在接下来的几年里。

根据f0和g0，它可能就像使用适当的累加器类型和组合函数进行严格的左折叠一样简单，就像著名的平均值一样

data P = P {-# UNPACK #-} !Int {-# UNPACK #-} !Double

average :: [Double] -> Double
average = ratio . foldl' count (P 0 0)
  where
    ratio (P n s) = s / fromIntegral n
    count (P n s) x = P (n+1) (s+x)

f0但如果and/or的结构g0不合适，比如一个是左折叠，另一个是右折叠，则可能无法在一次遍历中完成计算。l在这种情况下，需要在重新创建和存储之间进行选择l。l通过显式共享 ( ) 很容易实现存储where l = map h [1..n]，但如果编译器执行一些公共子表达式消除，则重新创建可能很难实现（不幸的是，GHC 确实倾向于共享该形式的列表，即使它几乎没有执行 CSE）。对于 GHC，标记fno-cse和-fno-full-laziness可以帮助避免不必要的共享。