为什么Haskell在执行类似C的代码时表现如此糟糕？(至少在这种情况下)

Question

我试图弄清楚我在Haskell中遇到的一些性能问题.作为其中的一部分,我编写了一个小比较程序来比较C和Haskell.具体来说,我尽可能少地将C程序翻译成Haskell.然后,Haskell程序的速度测量部分以非常强制的方式编写.

程序在一定范围内生成两个随机数列表,然后通过简单地连接这些点来计算形成的图的积分,其中一个列表是x值,一个列表是y值.从本质上讲,它是梯形规则.

以下是两个代码:

main.c中

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 5000000
#define maxY 1e5f/N
#define maxXgap 1

int main(){
    int i;
    float *y, *x;
    float xaccum, area;
    clock_t begin, end;
    double time_spent;

    y = (float*)malloc(sizeof(float)*N);
    x = (float*)malloc(sizeof(float)*N);

    srand(50546345); // change seed for different numbers

    //populate y and x fields with random points
    for(i = 0; i < N; i++){
        y[i] = ((float)rand())/((float)RAND_MAX)*maxY;
    }
    xaccum = 0;
    for(i = 0; i < N; i++){
        x[i] = xaccum;
        xaccum += ((float)rand())/((float)RAND_MAX)*maxXgap;
    }
    begin = clock();
    //perform a trapezoidal integration using the x y coordinates
    area = 0;
    for(i = 0; i < N-1; i++){
        area += (y[i+1]+y[i])/2*(x[i+1]-x[i]);
    }
    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC * 1000;
    printf("%i points\n%f area\n%f ms\n", N, area, time_spent);
}

Main.hs

{-# LANGUAGE BangPatterns #-}
module Main where

import Data.Array.Unboxed
import Data.Array.IO
import Data.List
import System.Random
import System.CPUTime
import Text.Printf
import Control.Exception

main :: IO ()
main = do
          (x,y) <- initArrays
          area <- time $ integrate x y
          print area

n :: Int
n = 5000000

maxY :: Float
maxY = 100000.0/(fromIntegral n)

maxXgap :: Float
maxXgap = 1

--initialize arrays with random floats
--this part is not measured in the running time (very slow)
initArrays :: IO (IOUArray Int Float, IOUArray Int Float)
initArrays = do
                y <- newListArray (0,n-1) (randomList maxY n (mkStdGen 23432))
                x <- newListArray (0,n-1) (scanl1 (+) $ randomList maxXgap n (mkStdGen 5462))
                return (x,y)

randomList :: Float -> Int -> StdGen -> [Float]
randomList max n gen = map (abs . ((*) max)) (take n . unfoldr (Just . random) $ gen)

integrate :: IOUArray Int Float -> IOUArray Int Float -> IO Float
integrate x y = iterative x y 0 0

iterative :: IOUArray Int Float -> IOUArray Int Float -> Int -> Float -> IO Float
iterative x y !i !accum = do if i == n-1
                              then return accum
                              else do x1 <- readArray x i
                                      x2 <- readArray x (i+1)
                                      y1 <- readArray y i
                                      y2 <- readArray y (i+1)
                                      iterative x y (i+1) (accum + (y2+y1)/2*(x2-x1))

time :: IO t -> IO t
time a = do
            start <- getCPUTime
            v <- a
            end <- getCPUTime
            let diff = (fromIntegral (end-start)) / (10^9)
            printf "Computation time %0.5f ms\n" (diff :: Double)
            return v

C集成在大约7毫秒内运行,Haskell集成在我的系统上大约60毫秒.当然Haskell版本会慢一些,但我想知道为什么它会慢得多.显然,Haskell代码中存在很多低效率.

为什么Haskell代码这么慢？怎么能解决它？

谢谢你的回答.

Answer 1

出于好奇,我用llvm运行了这个:

ghc Test.hs -O2 -XBangPatterns -fllvm -optlo-O3

它从60ms降到了24ms.仍然不理想.

所以,当我想知道为什么像这样的基准这么慢时,我要做的第一件事就是抛弃准备好的核心.也就是说,优化后的核心.

ghc Test.hs -O2 -ddump-prep -dsuppress-all -XBangPatterns> Test.hscore

在查看了核心之后,我最终找到了$ wa,其中定义了迭代循环.事实证明,这令人惊讶地进行了许多索引限制检查.请参阅,我通常使用具有"unsafeRead"和"unsafeIndex"函数的Data.Vector.Unboxed来删除边界检查.这些在这里很有用.就个人而言,我认为矢量包是优越的.

如果你看看$ wa,你会注意到它在开始时将参数拆箱:

case w_s3o9 of _ { STUArray l_s3of u_s3oi ds1_s3ol ds2_s3oH ->
case l_s3of of wild2_s3os { I# m_s3oo ->
case u_s3oi of wild3_s3ot { I# n1_s3ov ->
case ds1_s3ol of wild4_s3oC { I# y1_s3oE ->

这看起来很糟糕,但事实证明它在递归调用中使用的是专用版本,integration_ $ s $ wa,带有未装箱的整数等.这很好.

总之,我认为你应该通过使用带有不安全索引的向量来获得良好的改进.

编辑:这是一个带Data.Vector的修改版本.它运行大约7毫秒.对于良好的矢量代码,我认为与C相比唯一的缓慢应该是由于不完整的别名分析. https://gist.github.com/amosr/6026995

Answer 2

首先,我尝试使用您的代码重现您的发现(使用GHC 7.6.3 -O2 -fllvm和gcc 4.7.2和-O3)

$ ./theHaskellVersion-rev1
Computation time 24.00000 ms
25008.195
[tommd@Vodka Test]$ ./theCVersion
5000000 points
25013.105469 area
10.000000 ms

因此,如果目标是以平均值执行(运行时减少60%),我们的目标是10毫秒.看看你的代码,我看到:

• Arrays被使用,这是古老和cludgy.我切换到了Vector.
• 没有工人/包装器转换iterative.这种改变只是在一个不需要x和y作为参数的where子句中创建辅助函数.
• Float即使Double经常出色地表现得更好(这可能与此无关).

最终结果与您在C中发布的结果相符:

$ ghc -O2 so.hs -hide-package random && ./so
Computation time 11.00000 ms
24999.048783785303