我正在学习 Haskell。我的兴趣是将它用于个人计算机实验。现在，我正在尝试看看 Haskell 的速度有多快。许多人声称与 C(++) 相当，如果这是真的，我会非常高兴(我应该注意，无论它是否快速，我都会使用 Haskell，但快速仍然是一件好事)。

我的测试程序用一个非常简单的算法实现了 π(x):素数将结果加 1。素数在 1 和 √x 之间没有整数除数。这不是一场算法大战，这纯粹是为了编译器性能。

Haskell 在我的计算机上似乎慢了大约 6 倍，这很好(仍然比纯 Python 快 100 倍)，但这可能只是因为我是 Haskell 新手。

现在，我的问题是:如何在不改变算法的情况下优化 Haskell 实现？ Haskell 的性能真的与 C 相当吗？

这是我的 Haskell 代码:

import System.Environment

-- a simple integer square root
isqrt :: Int -> Int
isqrt = floor . sqrt . fromIntegral

-- primality test        
prime :: Int -> Bool
prime x = null [x | q <- [3, 5..isqrt x], rem x q == 0]

main = do
  n <- fmap (read . head) getArgs
  print $ length $ filter prime (2:[3, 5..n])

这是我的 C++ 代码:

#include <iostream>
#include <cmath>
#include <cstdlib>
using namespace std;

bool isPrime(int);

int main(int argc, char* argv[]) {
    int primes = 10000, count = 0;
    if (argc > 1) {
        primes = atoi(argv[1]);
    }
    if (isPrime(2)) {
        count++;
    }
    for (int i = 3; i <= primes; i+=2) {
        if (isPrime(i)){
            count++;
        }
    }
    cout << count << endl;
    return 0;
}

bool isPrime(int x){
    for (int i = 2; i <= floor(sqrt(x)); i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

最佳答案

您的 Haskell 版本在 prime 中构造一个惰性列表，只是为了测试它是否为空。这似乎确实是一个瓶颈。以下版本在我的机器上运行速度与 C++ 版本一样快:

prime :: Int -> Bool
prime x = go 3
  where
    go q | q <= isqrt x = if rem x q == 0 then False else go (q+2)
    go _  = True

使用 -O2 编译时为 3.31 秒，而使用 gcc 4.8 和 -O3 编译时使用 gcc 4.8 时为 3.18 秒。

当然，“猜测”程序优化慢的地方并不是一个很好的方法。幸运的是，Haskell 有很好的分析工具。

编译运行

$ ghc --make primes.hs -O2 -prof -auto-all -fforce-recomp && ./primes 5000000 +RTS -p

给予

# primes.prof
  Thu Feb 20 00:49 2014 Time and Allocation Profiling Report  (Final)

     primes +RTS -p -RTS 5000000

  total time  =        5.71 secs   (5710 ticks @ 1000 us, 1 processor)
  total alloc = 259,580,976 bytes  (excludes profiling overheads)

COST CENTRE MODULE  %time %alloc

prime.go    Main     96.4    0.0
main        Main      2.0   84.6
isqrt       Main      0.9   15.4

                                                      individual     inherited
COST CENTRE MODULE                  no.     entries  %time %alloc   %time %alloc

MAIN        MAIN                     45           0    0.0    0.0   100.0  100.0
 main       Main                     91           0    2.0   84.6   100.0  100.0
  prime     Main                     92     2500000    0.7    0.0    98.0   15.4
   prime.go Main                     93   326103491   96.4    0.0    97.3   15.4
    isqrt   Main                     95           0    0.9   15.4     0.9   15.4

--- >8 ---

这清楚地表明 prime 是事情变热的地方。有关分析的更多信息，我将向您推荐 Real World Haskell, Chap 25 .

要真正了解发生了什么，您可以查看(一种)GHC 的中间语言Core，它将向您展示优化后的代码外观。一些好的信息是at the Haskell wiki .除非必要，否则我不建议这样做，但很高兴知道存在这种可能性。

关于您的其他问题:

1) 如何在不改变算法的情况下优化 Haskell 实现？

配置文件，并尝试编写内部循环，以便它们不会进行任何内存分配，并且可以由编译器进行严格限制。这样做需要一些练习和经验。

2) Haskell 的性能真的与 C 相当吗？

这取决于。 GHC 很神奇，通常可以很好地优化你的程序。如果您知道自己在做什么，通常可以接近优化 C 的性能(C 速度的 100% - 200%)。也就是说，这些优化并不总是容易或看起来很漂亮，高级 Haskell 可能会更慢。但是不要忘记，在使用 Haskell 时，您会获得惊人的表现力和高级抽象。除了对性能最关键的应用程序之外，它通常对所有应用程序都足够快，即使这样，您也可以通过一些分析和性能优化来非常接近 C。

关于c++ - Haskell 与 C++ 中的简单 π(x)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21894270/