23

我有这个 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 4.6.3) 编译的 C 语言中的相同算法gcc -O2在 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);
}
4

4 回答 4

24

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

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那样使用刹车),将Integer1 向左移动适当的位数,这涉及到“大”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)相比较,将int1 向左移动适当的位数,将其与第一个相比较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 不太清楚如何处理这些,它无法将该代码转换为循环。修改后的代码使用Ints 并且vector包将代码重写为循环,因此 llvm确实知道如何很好地优化它,这表明了。

(1)假设一台普通的二进制计算机。这种优化是由普通 C 编译器完成的,即使没有任何优化标志,除非在div指令比移位快的非常罕见的平台上。

于 2012-10-04T18:17:04.547 回答
15

很少有东西能比带有严格累加器的手写循环更胜一筹:

{-# LANGUAGE BangPatterns #-}

import Data.Bits

f :: Int -> Int
f n = g 0 0
  where g !i !s | i <= n    = g (i+1) (if i .&. (unsafeShiftL 1 (i `rem` 4)) /= 0 then s+1 else s)
                | otherwise = s

main = print $ f 123456789

除了到目前为止提到的技巧之外,这还替换shiftunsafeShiftL,它不检查其参数。

-O2用and编译-fllvm,这比我机器上的原始速度快 13 倍。

注意:测试是否设置了位i可以x更清楚地写为x `testBit` i。这将产生与上述相同的组件。

于 2012-10-04T17:50:11.680 回答
12

Vector instead of list, fold instead of filter-and-length

Substituting the list for an unboxed vector and the filter-and-length for a fold (i.e. incrementing a counter) improves the time significantly for me. Here's what I used:

import qualified Data.Vector.Unboxed as UV
import Data.Bits

foo :: Int
foo = UV.foldl (\s i -> if i .&. (shift 1 (i `rem` 4)) /= 0 then s+1 else s) 0 (UV.enumFromN 0 123456789)

main = print foo

The original code (with two changes though: rem instead of mod as suggested in the comments, and adding an Int to the signature to avoid Integer) gave:

$ time ./orig 
30864196

real    0m2.159s
user    0m2.144s
sys     0m0.008s

The modified code above gave:

$ time ./new 
30864196

real    0m1.450s
user    0m1.440s
sys     0m0.004s

LLVM

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

Original (LLVM):

$ time ./orig-llvm 
30864196

real    0m2.047s
user    0m2.036s
sys     0m0.008s

Modified (LLVM):

$ time ./new-llvm 
30864196

real    0m0.233s
user    0m0.228s
sys     0m0.004s

For comparison, OP's original C code comes in at 0m0.152s user on my system.

This is all GHC 7.4.1, GCC 4.6.3, and vector 0.9.1. LLVM is either 2.9 or 3.0; I have both but can't seem to figure out which one GHC is actually using.

于 2012-10-04T16:29:58.660 回答
0

尝试这个:

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

没有::Int,类型默认为::Integerremmod正值相同,并且与%C中相同。mod另一方面,在负值上在数学上是正确的,但速度较慢。

  • int在 C 中是 32 位
  • Int在 Haskell 中是 32 位或 64 位宽,就像long在 C中一样
  • Integer是一个任意位整数,它没有最小值/最大值,它的内存大小取决于它的值(类似于字符串)。
于 2012-10-16T16:54:49.917 回答