函数调用在Haskell中有多少开销

Question

我是Haskell的新手，我对函数调用的成本感到困惑，这对我来说似乎完全不合理，让我认为我做错了什么。

考虑以下Haskell代码：

module Main where
logistic x = 4.0*x*(1.0-x)
lg :: Double -> Int -> Double
lg !x 0 = x
lg !x !n = lg (logistic x) (n-1)
main = putStrLn $ show $ lg 0.7861 100000000

使用命令编译

 ghc -O3 -XBangPatterns -o tsths tst.hs

运行它，我得到：

real    0m15.904s
user    0m15.853s
sys     0m0.016s

如果不是调用函数logistic，而是内联计算表达式：

module Main where
lg :: Double -> Int -> Double
lg !x 0 = x
lg !x !n = lg (4.0*x*(1.0-x)) (n-1)
main = putStrLn $ show $ lg 0.7861 100000000

执行时间变为：

real    0m0.838s
user    0m0.828s
sys     0m0.004s

这与等价的C程序完全相同，即

#include <stdio.h>
int main() {
   int i, num=100000000;
   double x=0.7861;
   for (i=0; i<num; ++i)
      x *= 4.0*(1.0-x);
   printf("%lgn", x);
}

我是不是做错了什么？

非常感谢。

Answer 1

这是GHC-7.4.1中的一个错误。查看生成的核心（只有函数lg的核心是重要的，从GHC-7.4.2中，我们得到

Main.lg3 :: GHC.Types.Double
[GblId,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 30 0}]
Main.lg3 = GHC.Float.$w$cfromRational Main.lg4 Main.lg2
Main.lg1 :: GHC.Types.Double
[GblId,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False,
         ConLike=False, Cheap=False, Expandable=False,
         Guidance=IF_ARGS [] 30 0}]
Main.lg1 = GHC.Float.$w$cfromRational Main.lg2 Main.lg2
Main.$wlg :: GHC.Prim.Double# -> GHC.Prim.Int# -> GHC.Prim.Double#
[GblId,
 Arity=2,
 Str=DmdType LL,
 Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=2, Value=True,
         ConLike=True, Cheap=True, Expandable=True,
         Guidance=IF_ARGS [0 30] 158 0}]
Main.$wlg =
   (ww_s1Oy :: GHC.Prim.Double#) (ww1_s1OC :: GHC.Prim.Int#) ->
    case ww1_s1OC of ds_Xvs {
      __DEFAULT ->
        case Main.lg3 of _ { GHC.Types.D# x_awJ ->
        case Main.lg1 of _ { GHC.Types.D# x1_awV ->
        letrec {
          $wlg1_X1PF [Occ=LoopBreaker]
            :: GHC.Prim.Double# -> GHC.Prim.Int# -> GHC.Prim.Double#
          [LclId, Arity=2, Str=DmdType LL]
          $wlg1_X1PF =
             (ww2_X1Pv :: GHC.Prim.Double#) (ww3_X1PA :: GHC.Prim.Int#) ->
              case ww3_X1PA of ds1_Xwr {
                __DEFAULT ->
                  $wlg1_X1PF
                    (GHC.Prim.*##
                       (GHC.Prim.*## x_awJ ww2_X1Pv) (GHC.Prim.-## x1_awV ww2_X1Pv))
                    (GHC.Prim.-# ds1_Xwr 1);
                0 -> ww2_X1Pv
              }; } in
        $wlg1_X1PF
          (GHC.Prim.*##
             (GHC.Prim.*## x_awJ ww_s1Oy) (GHC.Prim.-## x1_awV ww_s1Oy))
          (GHC.Prim.-# ds_Xvs 1)
        }
        };
      0 -> ww_s1Oy
    }

两个顶级CCD_ 3和一个像样的循环。

GHC-7.4.1有点过于内联了，产生了

Rec {
Main.$wlg [Occ=LoopBreaker]
  :: GHC.Prim.Double# -> GHC.Prim.Int# -> GHC.Prim.Double#
[GblId, Arity=2, Str=DmdType LL]
Main.$wlg =
   (ww_s1NS :: GHC.Prim.Double#) (ww1_s1NW :: GHC.Prim.Int#) ->
    case ww1_s1NW of ds_Xvb {
      __DEFAULT ->
        case GHC.Float.$wfromRat'' (-1021) 53 Main.logistic4 Main.logistic2
        of ww2_a1Mt { __DEFAULT ->
        case GHC.Float.$wfromRat'' (-1021) 53 Main.logistic2 Main.logistic2
        of ww3_X1Nq { __DEFAULT ->
        Main.$wlg
          (GHC.Prim.*##
             (GHC.Prim.*## ww2_a1Mt ww_s1NS) (GHC.Prim.-## ww3_X1Nq ww_s1NS))
          (GHC.Prim.-# ds_Xvb 1)
        }
        };
      0 -> ww_s1NS
    }
end Rec }

并在每次迭代中给您两个对fromRational工作者的调用。

现在，fromRational是一个相当复杂的函数。尽管在7.2系列中实现得更快，但它仍然相当缓慢，因此这些调用耗费了大量时间。

对于类型签名，不会生成Rational顶级常量，只有Double常量，然后使用这些常量，当然这不包括无端的减速。

Answer 2

正如Dan Burton所建议的，这实际上是多态函数的开销，因为GHC推断类型为logistic :: Fractional a => a -> a。如果显式指定类型，通常会启用更好的检查和更好的优化。我认为显式指定函数类型是一种很好的做法。

如果你想拥有多态类型的函数，但在特定用途下有全速的单态调用，你可以使用SPECIALIZE pragma，但我相信这是GHC特定的。

{-# LANGUAGE BangPatterns #-}
module Main where
logistic :: Fractional a => a -> a
{-# SPECIALISE logistic :: Double -> Double #-}
logistic x = 4.0*x*(1.0-x)
lg :: Double -> Int -> Double
lg !x 0 = x
lg !x !n = lg (logistic x) (n-1)
main = putStrLn $ show $ lg 0.7861 100000000

还要注意，您可以在文件的开头指定LANGUAGE杂注来启用bang模式，而不需要在命令行上启用它们。

在我的机器上，原始类型为21秒，显式类型为0.67秒，specialize为0.7秒（基本相同）。

我相信专用调用的开销非常小，因为它只是一堆指令，无论如何都会内联，但多态函数会导致调用。尽管有多态性，GHC却不能内联，这很奇怪。

Answer 3

将类型签名添加到logistic，您将看到加速。请允许我使用CPP来证明差异。

bash> cat tst.hs
module Main where
#if defined(SIG)
logistic :: Double -> Double
#endif
logistic x = 4.0*x*(1.0-x)
lg :: Double -> Int -> Double
lg !x 0 = x
lg !x !n = lg (logistic x) (n-1)
main = putStrLn $ show $ lg 0.7861 100000000

bash> ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.4.1

如果在未定义SIG的情况下编译（类型签名除外）：

bash> ghc -O3 -XBangPatterns -XCPP -o tsths tst.hs
[1 of 1] Compiling Main             ( tst.hs, tst.o )
Linking tsths ...

bash> time ./tsths
0.34209286442469333
real    0m13.187s
user    0m13.177s
sys 0m0.008s

现在，让我们使用定义的SIG进行编译，以便包含签名：

bash> rm tsths *.o *.hi

bash> ghc -O3 -XBangPatterns -XCPP -DSIG -o tsths tst.hs
[1 of 1] Compiling Main             ( tst.hs, tst.o )
Linking tsths ...
bash> time ./tsths
0.34209286442469333
real    0m0.464s
user    0m0.440s
sys 0m0.020s

不确定GHC为什么不在没有签名的情况下对其进行优化；无论如何，单态性限制应该将其限制为CCD_ 12。