如果在模块之间移动功能,性能会有很大差异

Question

如果我将一个函数从它的使用位置移动到一个单独的模块中,我注意到该程序的性能显着下降.

calc = sum . nub . map third . filter isProd . concat . map parts . permutations
    where third (_,_,b)          = fromDigits b
          isProd (a,b,p)         = fromDigits a * fromDigits b == fromDigits p
          -- All possibilities have digits: A x AAAA or AA x AAA
          parts (a:b:c:d:e:rest) = [([a], [b,c,d,e], rest)
                                   ,([a,b], [c,d,e], rest)]

在另一个模块中:

fromDigits :: Integral a => [a] -> a                                   
fromDigits = foldl1' (\a b -> 10 * a + b)

当fromDigits它在同一模块中时运行0.1秒,但当我将它移动到另一个模块时运行0.4秒.

我认为这是因为GHC不能内联函数,如果它在不同的模块中,但我觉得它应该能够,因为它们在同一个包中.

我不确定编译器的设置是什么,但是它是用Leksah/cabal默认构建的.我很确定这是-O2最低限度.

Answer 1

对于类型类多态fromDigits,您将获得一个函数,由于字典查找(+),(*)并且fromInteger太大而无法自动展开其展开.这意味着它不能专门用于调用站点,并且字典查找不能被消除以可能内联添加和乘法(这可能使得能够进一步优化).

当它与在其中使用的模块中定义时,通过优化,GHC为其使用的类型创建专用版本(如果已知).然后可以消除字典查找,(+)并且(*)可以内联和操作(如果它们使用的类型具有适合于内联的操作).

但这取决于所知的类型.因此,如果您具有多态calc并且fromDigits在一个模块中,但仅在其他模块中使用它,那么您再次处于只有通用版本可用的位置,但由于其展开未公开,因此不能专门化或以其他方式在呼叫站点优化.

一种解决方案是在接口文件中展开函数的展开,因此当必要的数据(特别是类型)可用时,可以在使用它的地方对其进行适当优化.您可以通过在函数中添加{-# INLINE #-}一个{-# INLINABLE #-}pragma ,或者从GHC 7开始,在接口文件中公开函数的展开.这使得在编译调用代码时几乎不变的源代码可用,因此可以使用更多可用信息正确地优化该函数.

这样做的缺点是代码膨胀,你得到每个调用站点的优化代码的副本(因为INLINABLE它不是那么极端,每个调用模块至少有一个副本,这通常不是太糟糕).

另一种解决方案是产生通过将定义模块中的专门版本,{-# SPECIALISE #-}编译指示(美国拼法也接受),让GHC创建优化版本的重要类型(Int,Integer,Word,？).这也会创建重写规则,因此在专门的类型中使用会被重写以使用专用版本(使用optimisations进行编译时).

这样做的缺点是,内联代码时可能出现的一些优化不是.

Answer 2

您可以使用以下inline函数告诉GHC在呼叫站点内联函数:http://www.haskell.org/ghc/docs/7.0.4/html/libraries/ghc-prim-0.2.0.0/GHC-Prim. html #v%3inline.您可能希望将它与INLINABLEpragma 结合使用:http://www.haskell.org/ghc/docs/7.0.4/html/users_guide/pragmas.html#inlinable-pragma