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

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

-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，类型默认为::Integer。 rem与mod正值相同，并且与%C中相同。mod另一方面，在负值上在数学上是正确的，但速度较慢。

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