haskell - 我可以加速这个 Haskell 算法吗？

Question

我有这个 haskell 文件，用 ghc -O2 (ghc 7.4.1) 编译，在我的机器上需要 1.65 秒

import Data.Bits
main = do
    print $ length $ filter (\i -> i .&. (shift 1 (i `mod` 4)) /= 0) [0..123456789]

使用 gcc -O2 (gcc 4.6.3) 编译的 C 语言相同算法，运行时间为 0.18 秒。

#include <stdio.h>
void main() {
    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);
}

更新我认为这可能是 Data.Bits 的东西变慢了，但令人惊讶的是，如果我删除移位并直接执行 mod ，它实际上运行速度慢为 5.6 秒!？!

import Data.Bits
main = do
    print $ length $ filter (\i -> (i `mod` 4) /= 0) [0..123456789]

而等效的 C 运行速度稍快，为 0.16 秒:

#include <stdio.h>
void main() {
    int count = 0;
    const int max = 123456789;
    int i;
    for (i = 0; i < max; ++i)
        if ((i % 4) != 0)
            ++count;
    printf("count: %d\n", count);
}

Answer 1

这两段代码做了非常不同的事情。

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 向左移动适当的位数，这涉及到转换为“big”Integers 和对 GMP 的调用，采用按位与 i - 对 GMP 的另一次调用 - 并检查结果是否为 0，这会导致对 GMP 的另一次调用或转换为小整数，不确定 GHC 在这里做什么。然后，如果结果非零，则会创建一个新的列表单元格，将 Integer 放入其中，并按 length 消耗。已完成大量工作，其中大部分工作由于未指定的数字类型默认为整数而变得不必要的复杂。

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 的返回类型)，所做的事情要少得多。它需要一个 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 的 native 代码生成器并不是一个特别好的循环优化器，因此使用 llvm 后端会产生很大的差异，但即使是 native 代码生成器也不会做得太差。

好吧，我已经完成了用按位和手动方式将模数计算替换为二次幂模数的优化，GHC 的 native 代码生成器还没有这样做，所以使用 ```rem4`` 而不是 .&。 3`， native 代码生成器生成的代码需要(此处)运行 1.42 秒，但 llvm 后端会进行优化，并生成与手动优化相同的代码。

现在，让我们转向 gspr's question

While LLVM didn't have a massive effect on the original code, it really did on the modified (I'd love to learn why...).

好吧，原始代码使用了Integer和列表，llvm不太清楚如何处理这些，它无法将该代码转换为循环。修改后的代码使用 Int ，并且 vector 包将代码重写为循环，因此 llvm 确实知道如何很好地优化，这表明.

⁽¹⁾ 假设一台普通的二进制计算机。即使没有任何优化标志，普通 C 编译器也会完成该优化，除非在极少数平台上 div 指令比移位更快。