有哪些可能的 Haskell 优化键？
What are possible Haskell optimizations keys?
我找到了用不同语言解决非常简单任务的基准测试 https://github.com/starius/lang-bench。这是 Haskell 的代码：
cmpsum i j k =
if i + j == k then 1 else 0
main = print (sum([cmpsum i j k |
i <- [1..1000], j <- [1..1000], k <- [1..1000]]))
正如您在基准测试中看到的那样，这段代码 运行 非常慢，我发现这很奇怪。
我尝试内联函数 cmpsum 并使用下一个标志进行编译：
ghc -c -O2 main.hs
但它真的没有帮助。我不是在问优化算法，因为它对所有语言都是一样的，而是在问可能的编译器或代码优化，可以使这段代码 运行 更快。
不完整的答案，抱歉。在我的机器上使用 GHC 7.10 进行编译，您的版本大约需要 12 秒。
我建议始终使用 -Wall 进行编译，这表明我们的数字默认为无限精度 Integer 类型。修复：
module Main where
cmpsum :: Int -> Int -> Int -> Int
cmpsum i j k =
if i + j == k then 1 else 0
main :: IO ()
main = print (sum([cmpsum i j k |
i <- [1..1000], j <- [1..1000], k <- [1..1000]]))
这对我来说大约需要 5 秒。 运行 +RTS -s 似乎表明我们在常量内存中有一个循环：
87,180 bytes allocated in the heap
1,704 bytes copied during GC
42,580 bytes maximum residency (1 sample(s))
18,860 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 0 colls, 0 par 0.000s 0.000s 0.0000s 0.0000s
Gen 1 1 colls, 0 par 0.000s 0.000s 0.0001s 0.0001s
INIT time 0.000s ( 0.001s elapsed)
MUT time 4.920s ( 4.919s elapsed)
GC time 0.000s ( 0.000s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 4.920s ( 4.921s elapsed)
%GC time 0.0% (0.0% elapsed)
Alloc rate 17,719 bytes per MUT second
Productivity 100.0% of total user, 100.0% of total elapsed
-fllvm 又缩短了一秒左右。也许其他人可以进一步研究它。
编辑：只是深入研究一下。看起来融合并没有发生。即使我将 sum 更改为 foldr (+) 0 这是一个明确的 "good producer/good consumer" 对。
Rec {
$wgo [InlPrag=[0], Occ=LoopBreaker] :: Int# -> Int#
[GblId, Arity=1, Str=DmdType <S,U>]
$wgo =
\ (w :: Int#) ->
let {
$j :: Int# -> Int#
[LclId, Arity=1, Str=DmdType]
$j =
\ (ww [OS=OneShot] :: Int#) ->
letrec {
$wgo1 [InlPrag=[0], Occ=LoopBreaker] :: [Int] -> Int#
[LclId, Arity=1, Str=DmdType <S,1*U>]
$wgo1 =
\ (w1 :: [Int]) ->
case w1 of _ [Occ=Dead] {
[] -> ww;
: y ys ->
case $wgo1 ys of ww1 { __DEFAULT ->
case lvl of _ [Occ=Dead] {
[] -> ww1;
: y1 ys1 ->
case y of _ [Occ=Dead] { I# y2 ->
case y1 of _ [Occ=Dead] { I# y3 ->
case tagToEnum# @ Bool (==# (+# w y2) y3) of _ [Occ=Dead] {
False ->
letrec {
$wgo2 [InlPrag=[0], Occ=LoopBreaker] :: [Int] -> Int#
[LclId, Arity=1, Str=DmdType <S,1*U>]
$wgo2 =
\ (w2 :: [Int]) ->
case w2 of _ [Occ=Dead] {
[] -> ww1;
: y4 ys2 ->
case y4 of _ [Occ=Dead] { I# y5 ->
case tagToEnum# @ Bool (==# (+# w y2) y5) of _ [Occ=Dead] {
False -> $wgo2 ys2;
True -> case $wgo2 ys2 of ww2 { __DEFAULT -> +# 1 ww2 }
}
}
}; } in
$wgo2 ys1;
True ->
letrec {
$wgo2 [InlPrag=[0], Occ=LoopBreaker] :: [Int] -> Int#
[LclId, Arity=1, Str=DmdType <S,1*U>]
$wgo2 =
\ (w2 :: [Int]) ->
case w2 of _ [Occ=Dead] {
[] -> ww1;
: y4 ys2 ->
case y4 of _ [Occ=Dead] { I# y5 ->
case tagToEnum# @ Bool (==# (+# w y2) y5) of _ [Occ=Dead] {
False -> $wgo2 ys2;
True -> case $wgo2 ys2 of ww2 { __DEFAULT -> +# 1 ww2 }
}
}
}; } in
case $wgo2 ys1 of ww2 { __DEFAULT -> +# 1 ww2 }
}
}
}
}
}
}; } in
$wgo1 lvl } in
case w of wild {
__DEFAULT -> case $wgo (+# wild 1) of ww { __DEFAULT -> $j ww };
1000 -> $j 0
}
end Rec }
事实上，查看 print $ foldr (+) (0:: Int) $ [ i+j | i <- [0..10000], j <- [0..10000]] 的核心似乎只融合了列表推导的第一层。这是一个错误吗？
您正在将对单个语句的循环与通过生成中间结构（列表）并折叠它进行计数进行比较。我不知道如果您创建一个包含十亿个元素的链表，Java 中的性能会有多好。
这是 Haskell 代码，它（大约）等同于您的 Java 代码。
{-# LANGUAGE BangPatterns #-}
main = print (loop3 1 1 1 0)
loop1 :: Int -> Int -> Int -> Int -> Int
loop1 !i !j !k !cc | k <= 1000 = loop1 i j (k+1) (cc + fromEnum (i + j == k))
| otherwise = cc
loop2 :: Int -> Int -> Int -> Int -> Int
loop2 !i !j !k !cc | j <= 1000 = loop2 i (j+1) k (loop1 i j k cc)
| otherwise = cc
loop3 :: Int -> Int -> Int -> Int -> Int
loop3 !i !j !k !cc | i <= 1000 = loop3 (i+1) j k (loop2 i j k cc)
| otherwise = cc
在我的机器上执行（test2 是你的 Haskell 代码）：
$ ghc --make -O2 test1.hs && ghc --make -O2 test2.hs && javac test3.java
$ time ./test1.exe && time ./test2.exe && time java test3
499500
real 0m1.614s
user 0m0.000s
sys 0m0.000s
499500
real 0m35.922s
user 0m0.000s
sys 0m0.000s
499500
real 0m1.589s
user 0m0.000s
sys 0m0.015s
此代码在 1 秒内完成工作，并且在 GHC 7.10 中没有额外分配 -O2（请参阅底部的分析输出）：
cmpsum :: Int -> Int -> Int -> Int
cmpsum i j k = fromEnum (i+j==k)
main = print $ sum [cmpsum i j k | i <- [1..1000],
j <- [1..const 1000 i],
k <- [1..const 1000 j]]
在 GHC 7.8 中，如果在开头添加以下内容，则在这种情况下（1.4 秒）可以获得几乎相同的结果：
import Prelude hiding (sum)
sum xs = foldr (\x r a -> a `seq` r (a+x)) id xs 0
这里存在三个问题：
将代码专门化为 Int 而不是让它默认为 Integer 是至关重要的。
GHC 7.10 为 sum 提供列表融合，而 GHC 7.8 没有。这是因为 sum 的新定义基于 foldl 的新定义，在某些情况下，如果没有 Joachim Breitner 为 GHC 7.10 创建的 "call arity" 分析，可能会非常糟糕。
GHC 在编译的早期执行有限的 "full laziness" 遍，在任何内联发生之前。结果，在循环中多次使用的 j 和 k 的常量 [1..1000] 项被提升到循环之外。如果这些实际上计算起来很昂贵，那会很好，但在这种情况下，一遍又一遍地进行加法而不是保存结果要便宜得多。上面的代码所做的是欺骗 GHC。由于 const 直到稍后才被内联，所以第一次完全惰性传递看不到列表是常量，所以它不会将它们提升出来。我这样写是因为它既漂亮又简短，但不可否认，它有点脆弱。为了使其更健壮，使用分阶段内联：
main = print $ sum [cmpsum i j k | i <- [1..1000],
j <- [1..konst 1000 i],
k <- [1..konst 1000 j]]
{-# INLINE [1] konst #-}
konst = const
这保证 konst 将在简化器阶段 1 中内联，但不会更早。第 1 阶段发生在 列表融合完成之后，因此让 GHC 看到所有内容是绝对安全的。
51,472 bytes allocated in the heap
3,408 bytes copied during GC
44,312 bytes maximum residency (1 sample(s))
17,128 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 0 colls, 0 par 0.000s 0.000s 0.0000s 0.0000s
Gen 1 1 colls, 0 par 0.000s 0.000s 0.0002s 0.0002s
INIT time 0.000s ( 0.000s elapsed)
MUT time 1.071s ( 1.076s elapsed)
GC time 0.000s ( 0.000s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 1.073s ( 1.077s elapsed)
%GC time 0.0% (0.0% elapsed)
Alloc rate 48,059 bytes per MUT second
Productivity 99.9% of total user, 99.6% of total elapsed
我找到了用不同语言解决非常简单任务的基准测试 https://github.com/starius/lang-bench。这是 Haskell 的代码：
cmpsum i j k =
if i + j == k then 1 else 0
main = print (sum([cmpsum i j k |
i <- [1..1000], j <- [1..1000], k <- [1..1000]]))
正如您在基准测试中看到的那样，这段代码 运行 非常慢，我发现这很奇怪。 我尝试内联函数 cmpsum 并使用下一个标志进行编译：
ghc -c -O2 main.hs
但它真的没有帮助。我不是在问优化算法，因为它对所有语言都是一样的，而是在问可能的编译器或代码优化，可以使这段代码 运行 更快。
不完整的答案，抱歉。在我的机器上使用 GHC 7.10 进行编译，您的版本大约需要 12 秒。
我建议始终使用 -Wall 进行编译，这表明我们的数字默认为无限精度 Integer 类型。修复：
module Main where
cmpsum :: Int -> Int -> Int -> Int
cmpsum i j k =
if i + j == k then 1 else 0
main :: IO ()
main = print (sum([cmpsum i j k |
i <- [1..1000], j <- [1..1000], k <- [1..1000]]))
这对我来说大约需要 5 秒。 运行 +RTS -s 似乎表明我们在常量内存中有一个循环：
87,180 bytes allocated in the heap
1,704 bytes copied during GC
42,580 bytes maximum residency (1 sample(s))
18,860 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 0 colls, 0 par 0.000s 0.000s 0.0000s 0.0000s
Gen 1 1 colls, 0 par 0.000s 0.000s 0.0001s 0.0001s
INIT time 0.000s ( 0.001s elapsed)
MUT time 4.920s ( 4.919s elapsed)
GC time 0.000s ( 0.000s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 4.920s ( 4.921s elapsed)
%GC time 0.0% (0.0% elapsed)
Alloc rate 17,719 bytes per MUT second
Productivity 100.0% of total user, 100.0% of total elapsed
-fllvm 又缩短了一秒左右。也许其他人可以进一步研究它。
编辑：只是深入研究一下。看起来融合并没有发生。即使我将 sum 更改为 foldr (+) 0 这是一个明确的 "good producer/good consumer" 对。
Rec {
$wgo [InlPrag=[0], Occ=LoopBreaker] :: Int# -> Int#
[GblId, Arity=1, Str=DmdType <S,U>]
$wgo =
\ (w :: Int#) ->
let {
$j :: Int# -> Int#
[LclId, Arity=1, Str=DmdType]
$j =
\ (ww [OS=OneShot] :: Int#) ->
letrec {
$wgo1 [InlPrag=[0], Occ=LoopBreaker] :: [Int] -> Int#
[LclId, Arity=1, Str=DmdType <S,1*U>]
$wgo1 =
\ (w1 :: [Int]) ->
case w1 of _ [Occ=Dead] {
[] -> ww;
: y ys ->
case $wgo1 ys of ww1 { __DEFAULT ->
case lvl of _ [Occ=Dead] {
[] -> ww1;
: y1 ys1 ->
case y of _ [Occ=Dead] { I# y2 ->
case y1 of _ [Occ=Dead] { I# y3 ->
case tagToEnum# @ Bool (==# (+# w y2) y3) of _ [Occ=Dead] {
False ->
letrec {
$wgo2 [InlPrag=[0], Occ=LoopBreaker] :: [Int] -> Int#
[LclId, Arity=1, Str=DmdType <S,1*U>]
$wgo2 =
\ (w2 :: [Int]) ->
case w2 of _ [Occ=Dead] {
[] -> ww1;
: y4 ys2 ->
case y4 of _ [Occ=Dead] { I# y5 ->
case tagToEnum# @ Bool (==# (+# w y2) y5) of _ [Occ=Dead] {
False -> $wgo2 ys2;
True -> case $wgo2 ys2 of ww2 { __DEFAULT -> +# 1 ww2 }
}
}
}; } in
$wgo2 ys1;
True ->
letrec {
$wgo2 [InlPrag=[0], Occ=LoopBreaker] :: [Int] -> Int#
[LclId, Arity=1, Str=DmdType <S,1*U>]
$wgo2 =
\ (w2 :: [Int]) ->
case w2 of _ [Occ=Dead] {
[] -> ww1;
: y4 ys2 ->
case y4 of _ [Occ=Dead] { I# y5 ->
case tagToEnum# @ Bool (==# (+# w y2) y5) of _ [Occ=Dead] {
False -> $wgo2 ys2;
True -> case $wgo2 ys2 of ww2 { __DEFAULT -> +# 1 ww2 }
}
}
}; } in
case $wgo2 ys1 of ww2 { __DEFAULT -> +# 1 ww2 }
}
}
}
}
}
}; } in
$wgo1 lvl } in
case w of wild {
__DEFAULT -> case $wgo (+# wild 1) of ww { __DEFAULT -> $j ww };
1000 -> $j 0
}
end Rec }
事实上，查看 print $ foldr (+) (0:: Int) $ [ i+j | i <- [0..10000], j <- [0..10000]] 的核心似乎只融合了列表推导的第一层。这是一个错误吗？
您正在将对单个语句的循环与通过生成中间结构（列表）并折叠它进行计数进行比较。我不知道如果您创建一个包含十亿个元素的链表，Java 中的性能会有多好。
这是 Haskell 代码，它（大约）等同于您的 Java 代码。
{-# LANGUAGE BangPatterns #-}
main = print (loop3 1 1 1 0)
loop1 :: Int -> Int -> Int -> Int -> Int
loop1 !i !j !k !cc | k <= 1000 = loop1 i j (k+1) (cc + fromEnum (i + j == k))
| otherwise = cc
loop2 :: Int -> Int -> Int -> Int -> Int
loop2 !i !j !k !cc | j <= 1000 = loop2 i (j+1) k (loop1 i j k cc)
| otherwise = cc
loop3 :: Int -> Int -> Int -> Int -> Int
loop3 !i !j !k !cc | i <= 1000 = loop3 (i+1) j k (loop2 i j k cc)
| otherwise = cc
在我的机器上执行（test2 是你的 Haskell 代码）：
$ ghc --make -O2 test1.hs && ghc --make -O2 test2.hs && javac test3.java
$ time ./test1.exe && time ./test2.exe && time java test3
499500
real 0m1.614s
user 0m0.000s
sys 0m0.000s
499500
real 0m35.922s
user 0m0.000s
sys 0m0.000s
499500
real 0m1.589s
user 0m0.000s
sys 0m0.015s
此代码在 1 秒内完成工作，并且在 GHC 7.10 中没有额外分配 -O2（请参阅底部的分析输出）：
cmpsum :: Int -> Int -> Int -> Int
cmpsum i j k = fromEnum (i+j==k)
main = print $ sum [cmpsum i j k | i <- [1..1000],
j <- [1..const 1000 i],
k <- [1..const 1000 j]]
在 GHC 7.8 中，如果在开头添加以下内容，则在这种情况下（1.4 秒）可以获得几乎相同的结果：
import Prelude hiding (sum)
sum xs = foldr (\x r a -> a `seq` r (a+x)) id xs 0
这里存在三个问题：
将代码专门化为
Int而不是让它默认为Integer是至关重要的。GHC 7.10 为
sum提供列表融合，而 GHC 7.8 没有。这是因为sum的新定义基于foldl的新定义，在某些情况下，如果没有 Joachim Breitner 为 GHC 7.10 创建的 "call arity" 分析，可能会非常糟糕。GHC 在编译的早期执行有限的 "full laziness" 遍，在任何内联发生之前。结果，在循环中多次使用的
j和k的常量[1..1000]项被提升到循环之外。如果这些实际上计算起来很昂贵，那会很好，但在这种情况下，一遍又一遍地进行加法而不是保存结果要便宜得多。上面的代码所做的是欺骗 GHC。由于const直到稍后才被内联，所以第一次完全惰性传递看不到列表是常量，所以它不会将它们提升出来。我这样写是因为它既漂亮又简短，但不可否认，它有点脆弱。为了使其更健壮，使用分阶段内联：main = print $ sum [cmpsum i j k | i <- [1..1000], j <- [1..konst 1000 i], k <- [1..konst 1000 j]] {-# INLINE [1] konst #-} konst = const这保证
konst将在简化器阶段 1 中内联，但不会更早。第 1 阶段发生在 列表融合完成之后，因此让 GHC 看到所有内容是绝对安全的。
51,472 bytes allocated in the heap
3,408 bytes copied during GC
44,312 bytes maximum residency (1 sample(s))
17,128 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 0 colls, 0 par 0.000s 0.000s 0.0000s 0.0000s
Gen 1 1 colls, 0 par 0.000s 0.000s 0.0002s 0.0002s
INIT time 0.000s ( 0.000s elapsed)
MUT time 1.071s ( 1.076s elapsed)
GC time 0.000s ( 0.000s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 1.073s ( 1.077s elapsed)
%GC time 0.0% (0.0% elapsed)
Alloc rate 48,059 bytes per MUT second
Productivity 99.9% of total user, 99.6% of total elapsed