Сколько накладных расходов вызывает функциональные вызовы в Haskell?
Я новичок в 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, я вычисляю выражение inline:
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);
}
Я делаю что-то ужасно неправильно?
Большое спасибо.
Ответы
Ответ 1
Добавьте подпись типа к 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.
Ответ 2
Это ошибка в 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
}
два верхних уровня 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 на каждой итерации.
Теперь fromRational является довольно сложной функцией. Он все еще довольно медленный, несмотря на то, что он получил гораздо более быструю реализацию в серии 7.2, поэтому эти вызовы сильно пострадали.
С сигнатурой типа не существует Rational констант верхнего уровня, только константы Double, и они затем используются, что, конечно же, не включает безвозмездное замедление.
Ответ 3
Как предложил Дэн Бертон, на самом деле это накладные расходы на полиморфную функцию, поскольку GHC вводит тип 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 pragma в начале файла, чтобы включить шаблоны bang и не нужно включать их в командной строке.
Время на моей машине составляло 21 секунду для оригинала, 0,67 с для явного типа, 0,7 сек для специализации (что в основном одинаково).
Я считаю, что накладные расходы на специализированный вызов очень малы, потому что это просто куча инструкций, которые все равно встраиваются, но полиморфная функция приводит к вызову. Хотя странно, что GHC не может быть встроен, несмотря на полиморфизм.
