这两段代码做了非常不同的事情。
import Data.Bits
main = do
print $ length $ filter (\i -> i .&. (shift 1 (i `mod` 4)) /= 0) [0..123456789]
创建一个 123456790 的列表Integer
(懒惰地),取每个模 4 的余数(首先检查 是否Integer
小到足以包装原始机器整数,然后在除法之后进行符号检查,因为mod
只返回非负结果 -虽然在 ghc-7.6.1 中,有一个 primop,所以它不像以前mod
那样使用刹车),将Integer
1 向左移动适当的位数,这涉及到“大”Integer
的转换和对 GMP 的调用,按位和 with i
- 又一次调用 GMP - 并检查结果是否为 0,这会导致再次调用 GMP 或转换为小整数,不确定 GHC 在这里做了什么。然后,如果结果不为零,则创建一个新的列表单元格,其中Integer
被放入,并被 消耗掉length
。已经完成了很多工作,其中大部分工作由于未指定的数字类型默认为Integer
.
C 代码
#include <stdio.h>
int main(void) {
int count = 0;
const int max = 123456789;
int i;
for (i = 0; i < max; ++i)
if ((i & (1 << i % 4)) != 0)
++count;
printf("count: %d\n", count);
return 0;
}
(我冒昧地修复了 的返回类型main
),做得少得多。它需要 a int
,将其与另一个比较,如果更小,则将第一个int
与 3 (1)相比较,将int
1 向左移动适当的位数,将其与第一个相比较int
,如果非零增加另一个int
,然后增加第一个。这些都是机器操作,在原始机器类型上工作。
如果我们将该代码翻译成 Haskell,
module Main (main) where
import Data.Bits
maxNum :: Int
maxNum = 123456789
loop :: Int -> Int -> Int
loop acc i
| i < maxNum = loop (if i .&. (1 `shiftL` (i .&. 3)) /= 0 then acc + 1 else acc) (i+1)
| otherwise = acc
main :: IO ()
main = print $ loop 0 0
我们得到更接近的结果:
C, gcc -O3:
count: 30864196
real 0m0.180s
user 0m0.178s
sys 0m0.001s
Haskell, ghc -O2:
30864196
real 0m0.247s
user 0m0.243s
sys 0m0.003s
Haskell, ghc -O2 -fllvm:
30864196
real 0m0.144s
user 0m0.140s
sys 0m0.003s
GHC 的本机代码生成器并不是一个特别好的循环优化器,因此在这里使用 llvm 后端会产生很大的不同,但即使是本机代码生成器也不会做得太差。
好的,我已经完成了用按位和手动替换模数计算的二次幂模数的优化,GHC 的本机代码生成器(还没有)这样做,所以使用 ```rem 4`` instead of
.&。3`,本机代码生成器生成的代码需要(此处)运行 1.42 秒,但 llvm 后端会进行优化,并生成与手工优化相同的代码。
现在,让我们转向gspr 的问题
虽然 LLVM 对原始代码没有产生巨大影响,但它确实对修改后的代码产生了影响(我很想知道为什么......)。
好吧,使用的原始代码Integer
沙列表,llvm 不太清楚如何处理这些,它无法将该代码转换为循环。修改后的代码使用Int
s 并且vector
包将代码重写为循环,因此 llvm确实知道如何很好地优化它,这表明了。
(1)假设一台普通的二进制计算机。这种优化是由普通 C 编译器完成的,即使没有任何优化标志,除非在div
指令比移位快的非常罕见的平台上。