Может ли Haskell оптимизировать вызовы функций так же, как Clang / GCC?
Я хочу спросить вас, могут ли компиляторы Haskell и C ++ оптимизировать вызовы функций одинаково.
Пожалуйста, посмотрите на следующие коды. В следующем примере Haskell значительно быстрее, чем C ++.
Я слышал, что Haskell может компилироваться в LLVM и может быть оптимизирован с помощью проходов LLVM. Кроме того, я слышал, что у Haskell есть некоторые серьезные оптимизации под капотом.
Но следующие примеры должны быть в состоянии работать с той же производительностью.
Я хочу спросить:
- Почему мой пример теста в C ++ работает медленнее, чем в Haskell?
- Можно ли дополнительно оптимизировать коды?
(Я использую LLVM-3.2 и GHC-7.6).
Код C ++:
#include <cstdio>
#include <cstdlib>
int b(const int x){
return x+5;
}
int c(const int x){
return b(x)+1;
}
int d(const int x){
return b(x)-1;
}
int a(const int x){
return c(x) + d(x);
}
int main(int argc, char* argv[]){
printf("Starting...\n");
long int iternum = atol(argv[1]);
long long int out = 0;
for(long int i=1; i<=iternum;i++){
out += a(iternum-i);
}
printf("%lld\n",out);
printf("Done.\n");
}
составлено с clang++ -O3 main.cpp
код haskell:
module Main where
import qualified Data.Vector as V
import System.Environment
b :: Int -> Int
b x = x + 5
c x = b x + 1
d x = b x - 1
a x = c x + d x
main = do
putStrLn "Starting..."args <- getArgs
let iternum = read (head args) :: Int in do
putStrLn $ show $ V.foldl' (+) 0 $ V.map (\i -> a (iternum-i))
$ V.enumFromTo 1 iternum
putStrLn "Done."составлено с ghc -O3 --make -fforce-recomp -fllvm ghc-test.hs
Скорость результатов:
Running testcase for program 'cpp/a.out'
-------------------
cpp/a.out 100000000 0.0% avg time: 105.05 ms
cpp/a.out 200000000 11.11% avg time: 207.49 ms
cpp/a.out 300000000 22.22% avg time: 309.22 ms
cpp/a.out 400000000 33.33% avg time: 411.7 ms
cpp/a.out 500000000 44.44% avg time: 514.07 ms
cpp/a.out 600000000 55.56% avg time: 616.7 ms
cpp/a.out 700000000 66.67% avg time: 718.69 ms
cpp/a.out 800000000 77.78% avg time: 821.32 ms
cpp/a.out 900000000 88.89% avg time: 923.18 ms
cpp/a.out 1000000000 100.0% avg time: 1025.43 msRunning testcase for program 'hs/main'
-------------------
hs/main 100000000 0.0% avg time: 70.97 ms (diff: 34.08)
hs/main 200000000 11.11% avg time: 138.95 ms (diff: 68.54)
hs/main 300000000 22.22% avg time: 206.3 ms (diff: 102.92)
hs/main 400000000 33.33% avg time: 274.31 ms (diff: 137.39)
hs/main 500000000 44.44% avg time: 342.34 ms (diff: 171.73)
hs/main 600000000 55.56% avg time: 410.65 ms (diff: 206.05)
hs/main 700000000 66.67% avg time: 478.25 ms (diff: 240.44)
hs/main 800000000 77.78% avg time: 546.39 ms (diff: 274.93)
hs/main 900000000 88.89% avg time: 614.12 ms (diff: 309.06)
hs/main 1000000000 100.0% avg time: 682.32 ms (diff: 343.11)
РЕДАКТИРОВАТЬ
Конечно, мы не можем сравнивать скорость языков, но скорость реализации.
Но мне любопытно, могут ли компиляторы Ghc и C ++ оптимизировать вызовы функций одинаково
Я отредактировал вопрос с новым тестом и кодами на основе вашей помощи 🙂
Решение
Если ваша цель — запустить это так же быстро, как ваш компилятор C ++, то вы
хотел бы использовать структуру данных, с которой компилятор может иметь свой путь.
module Main where
import qualified Data.Vector as V
b :: Int -> Int
b x = x + 5
c x = b x + 1
d x = b x - 1
a x = c x + d x
main = do
putStrLn "Starting..."putStrLn $ show $ V.foldl' (+) 0 $ V.map a $ V.enumFromTo 1 100000000
putStrLn "Done."GHC может полностью устранить цикл и просто вставить константу в
итоговая сборка. На моем компьютере это теперь имеет время выполнения < 0,002 с, когда
используя те же флаги оптимизации, которые вы указали изначально.
Как продолжение, основанное на комментариях @Yuras, ядро, созданное
векторное решение и решение для слияния потоков функционально
идентичны.
main_$s$wfoldlM'_loop [Occ=LoopBreaker]
:: Int# -> Int# -> Int#
main_$s$wfoldlM'_loop =
\ (sc_s2hW :: Int#) (sc1_s2hX :: Int#) ->
case <=# sc1_s2hX 100000000 of _ {
False -> sc_s2hW;
True ->
main_$s$wfoldlM'_loop
(+#
sc_s2hW
(+#
(+# (+# sc1_s2hX 5) 1)
(-# (+# sc1_s2hX 5) 1)))
(+# sc1_s2hX 1)
}
$wloop_foldl [Occ=LoopBreaker]
:: Int# -> Int# -> Int#
$wloop_foldl =
\ (ww_s1Rm :: Int#) (ww1_s1Rs :: Int#) ->
case ># ww1_s1Rs 100000000 of _ {
False ->
$wloop_foldl
(+#
ww_s1Rm
(+#
(+# (+# ww1_s1Rs 5) 1)
(-# (+# ww1_s1Rs 5) 1)))
(+# ww1_s1Rs 1);
True -> ww_s1Rm
}
Единственная реальная разница — выбор операции сравнения для
условие прекращения. Обе версии компилируются в узкие хвостовые рекурсивные циклы
это может быть легко оптимизировано LLVM.
Другие решения
GHC не объединяет списки (избегая успеха любой ценой?)
Вот версия, которая использует Поток-фьюжн пакет:
module Main where
import Prelude hiding (map, foldl)
import Data.List.Stream
import Data.Stream (enumFromToInt, unstream)
import Text.Printf
import Control.Exception
import System.CPUTime
b :: Int -> Int
b x = x + 5
c x = b x + 1
d x = b x - 1
a x = c x + d x
main = do
putStrLn "Starting..."putStrLn $ show $ foldl (+) 0 $ map (\z -> a z) $ unstream $ enumFromToInt 1 100000000
putStrLn "Done."У меня не установлено приложение llvm для сравнения с вашими результатами, но оно в 10 раз быстрее вашей версии (скомпилировано без llvm).
Я думаю, что векторный синтез должен работать еще быстрее.
Как уже отмечали другие, вы не сравниваете эквивалентные алгоритмы. Как Юрас указал GHC не объединяет списки. Ваша версия на Haskell фактически выделит весь этот список, это будет выполняться лениво по одной ячейке за раз, но это будет сделано. Ниже приведена версия, которая алгоритмически ближе к вашей C-версии. В моей системе он работает одновременно с версией C.
{-# LANGUAGE BangPatterns #-}
module Main where
import Text.Printf
import Control.Exception
import System.CPUTime
import Data.List
a,b,c :: Int -> Int
b x = x + 5
c x = b x + 1
d x = b x - 1
a !x = c x + d x
-- Don't allocate a list, iterate and increment as the C version does.
applyTo !acc !n
| n > 100000000 = acc
| otherwise = applyTo (acc + a n) (n + 1)
main = do
putStrLn "Starting..."print $ applyTo 0 1
putStrLn "Done."Сравнивая это с time:
ghc -O3 bench.hs -fllvm -fforce-recomp -o bench-hs && time ./bench-hs
[1 of 1] Compiling Main ( bench.hs, bench.o )
Linking bench-hs ...
Starting...
10000001100000000
Done.
./bench-hs 0.00s user 0.00s system 0% cpu 0.003 total
По сравнению с С:
clang++ -O3 bench.cpp -o bench && time ./bench
Starting...
10000001100000000
Done.
./bench 0.00s user 0.00s system 0% cpu 0.004 total