17

私は 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("%lg\n", x);
}

私は何かひどく間違ったことをしていますか？

どうもありがとう。

4

3 に答える 3

21

これは 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
    }

2 つのトップレベルDoubleと適切なループ。

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各反復でワーカーを 2 回呼び出しました。

さて、fromRationalかなり複雑な関数です。7.2 シリーズで実装が大幅に高速化されたにもかかわらず、依然としてかなり遅いため、これらの呼び出しは大きな打撃を与えます。

型シグネチャを使用すると、Rationalトップレベルの定数は生成されず、Double定数のみが生成され、これらが使用されます。もちろん、不当な速度低下は含まれません。

于 2012-09-07T16:21:02.493 に答える
11

Dan Burton が示唆しているように、GHC は type を推論するため、実際には多相関数のオーバーヘッドですlogistic :: Fractional a => a -> a。タイプを明示的に指定すると、通常、より優れたチェックとより優れた最適化の両方が有効になります。関数の型を明示的に指定することは良い習慣だと思います。

多相型の関数を持ちたいが、特定の用途の場合にモノモーフィック呼び出しのフルスピードが必要な場合は、SPECIALIZEプラグマを使用できますが、これは 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、ファイルの先頭にプラグマを指定して強打パターンを有効にすることができ、コマンド ラインで有効にする必要がないことにも注意してください。

私のマシンでの時間は、オリジナルで 21 秒、明示的なタイプで 0.67 秒、特化で 0.7 秒でした (これは基本的に同じです)。

とにかくインライン化されるのは単なる命令の束であり、ポリモーフィング関数は呼び出しになるため、特殊化された呼び出しのオーバーヘッドは非常に小さいと思います。ポリモーフィズムにもかかわらず、GHC がインライン化できないのは奇妙ですが。

于 2012-09-07T16:10:00.273 に答える
9

に型シグネチャを追加する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 が署名なしで最適化しない理由がわかりません。Double -> Doubleモノモーフィズムの制限により、とにかく制限する必要があります。

于 2012-09-07T15:58:35.430 に答える