优化哈斯克尔中的部分计算



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

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

假设ff0gg0h都是昂贵的,但l的创建和存储是极其昂贵的。

如前所述,l 被存储,直到返回的元组被完全评估或垃圾回收。 相反,length lf0 lg0 l 都应该在执行其中任何一个时执行,但fg应该延迟。

似乎可以通过编写以下内容来修复此行为:

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的方式将编译器融合sumf0g0成一个循环,逐项构造和使用l。 我可以通过手动内联来明确这一点,但这很糟糕。 有没有办法明确阻止创建列表l和/或强制内联? 如果内联或融合在编译过程中失败,可能会产生警告或错误,杂注?

顺便说一句,我很好奇为什么seqinlinelazy等都是由前奏曲中的let x = x in x定义的。 这仅仅是为了给编译器一个定义来覆盖吗?

如果你想确定,唯一的方法就是自己做。对于任何给定的编译器版本,您可以尝试多个源代码公式,并检查生成的核心/程序集/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版本,编译器可能能够合并abc的计算,以便在单次遍历l期间并行执行(不是并发意义上的),但就目前而言,我相当确信 GHC 没有,如果 JHC 或 UHC 这样做,我会感到惊讶。为此,计算bc的结构需要足够简单。

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

根据f0g0,它可能就像使用适当的累加器类型和组合功能进行严格的左折一样简单,就像著名的平均值一样

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确实倾向于共享该形式的列表,即使它很少进行CSE)。对于 GHC,标志fno-cse-fno-full-laziness可以帮助避免不必要的共享。

最新更新