8

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

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 ...

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

另外，我显然希望我inline的 s 编译器将sum, f0, 和融合g0到一个循环中，该循环逐项构造和l使用。我可以通过手动内联来明确这一点，但这很糟糕。有没有办法明确地阻止列表l被创建和/或强制内联？如果在编译期间内联或融合失败，可能会产生警告或错误的编译指示？

顺便说一句，我很好奇为什么seq, inline,lazy等都let x = x in x在 Prelude 中定义。这只是为了给他们一个定义让编译器覆盖吗​​？

4

1 回答 1

3

如果你想确定，唯一的办法就是自己做。对于任何给定的编译器版本，您可以尝试几种源代码公式并检查生成的核心/程序集/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需要足够简单。

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

取决于f0and 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和/或的结构g0不适合，比如一个是左折叠，另一个是右折叠，则可能无法在一次遍历中进行计算。在这种情况下，选择是在重新创建l和存储之间l。通过显式l共享（where l = map h [1..n]对于 GHC，标志fno-cse和-fno-full-laziness可以帮助避免不必要的共享。

于 2012-04-22T12:41:34.653 回答