performance - 为什么这个 Haskell 代码比等效的 C 代码慢得多？已使用的未装箱矢量和刘海

Question

我用 Haskell 和 C 编写了一个简短的 Mandelbrot 集生成器，发现 C 版本运行 20 倍 比 Haskell 版本更快。虽然我预计 Haskell 会更慢，但考虑到我已经在使用未装箱的向量和 bang 来避免过多的重击，我没想到会超过一个数量级。

分析显示大部分时间都花在 go以下代码的函数，实际上只是一个带有一些比较、乘法和加法的循环。

orbits limit radius a b = go 0 0 0
  where
    r2 = radius * radius
    go !n !x !y
      | n == limit    = n
      | x2 + y2 >= r2 = n
      | otherwise     = go (n + 1) (x2 - y2 + a) (2 * x * y + b)
      where
        x2 = x * x
        y2 = y * y

在执行中，运行 C 代码需要 0.9 秒，而等效的 Haskell 代码需要 18 秒。它们都实现相同的算法，并且都生成相同的输出(PGM 图形文件)。

Haskell 源代码在这里:

Main.hs

MandelV.hs

mandel3.prof (profiling report)

C代码在这里:

mandel.c

导致这种巨大性能差异的问题可能是什么？

Answer 1

tl;dr - 添加类型签名，使用 ByteString并打开-O3

但首先——正如其他人之前所说——你不是在比较相同的东西，而你的 c 代码使用了很多可变性和 c 的弱类型系统。而且我相信写入文件也比haskell等价物更不安全。您可以从 haskell 的类型检查/类型推断中受益。

另请注意，如果没有任何类型签名，您的代码是多态的 - 即您可以使用与 Float 相同的代码或 Double , Word8或 Int如果你想这样做。这是第一个陷阱 - 对于整数 GHC 默认为 Integer ，一个任意精度的整数，相当于“bigint”，通常慢几个数量级。

因此添加类型签名，极大地提高了速度。

(用于练习和学习)我使用未装箱类型 (ub-mandel)、类型化版本 (mandel) 和 op 的非类型化版本 (ut-mandel) 以及 c 版本 (c-mandel) 进行了一些比较和实现。

测量这些程序，您会得到以下结果(在使用 linux 的现代笔记本电脑上)

★ time ./c-mandel
./c-mandel  0,46s user 0,00s system 99% cpu 0,467 total

★ time stack exec -- ut-mandel
stack exec -- ut-mandel  9,33s user 0,09s system 99% cpu 9,432 total

★ time stack exec -- mandel
stack exec -- mandel  1,70s user 0,04s system 99% cpu 1,749 total

★ time stack exec -- ub-mandel
stack exec -- ub-mandel  1,25s user 0,08s system 98% cpu 1,343 total

显然，c 代码优于所有实现——但仅添加类型签名就可以将速度提高 5.49 倍。尽管迁移到未装箱类型(我不得不承认这是第一次)带来了另外 36% 的加速(注意:这种加速是以代码的可读性为代价的)。

但是，从 String 切换仍然可以改进这一点。版本为 ByteString让我们更进一步。

★ time stack exec -- ub-mandel-bytestring
stack exec -- ub-mandel-bytestring 0,84s user 0,04s system 98% cpu 0,890 total

得到教训

打开类型签名

打开-O3

使用 Bytestring

如果您的代码仍然不够快 - 请花一个小时并转到未装箱类型

如果您仍有精力，请继续阅读 llvm 输出以及编译器的作用，起点将是 neil mitchell's blog article

注:所有这些计算都是在没​​有使用并行计算的情况下完成的，我认为在 haskell 中比在 C 中更容易完成。但这是我留给其他人的任务，或者看看 gh: simonmar/parconc-examples对于在 gpu 上并行运行的版本。

为了完整起见，未装箱的字节串版本:
Main.hs

{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE MagicHash #-}

module Main where

import Control.Monad
import Data.ByteString.Char8 as C
import System.IO (withFile, IOMode(WriteMode), Handle)

import           GHC.Prim
import           GHC.Exts (Int(..), Double(..))
import qualified Data.Vector.Unboxed as U
import qualified MandelV as MV

savePgm :: Int -> Int -> Int -> U.Vector Int -> String -> IO ()
savePgm w h orbits v filename =
  withFile filename WriteMode $ \f -> do
    hPutStrLn f "P2"
    hPutStrLn f $ C.pack $ show w ++ " " ++ show h
    hPutStrLn f (C.pack $ show orbits)
    U.imapM_ (elm f) v
  where
      elm :: Handle -> Int -> Int -> IO ()
      elm f ix e =
          if rem ix w == 0
             then hPutStrLn f $ C.pack $ show e
             else hPutStr f $ C.pack $ show e ++ " "

main :: IO ()
main = do
  let w        = 2560#  :: Int#
      h        = 1600#  :: Int#
      x1       = -2.0## :: Double#
      y1       = -1.5## :: Double#
      x2       = 1.0##  :: Double#
      y2       = 1.5##  :: Double#
      filename = "test_hs.pgm"
      orbits   = 63#    :: Int#
      radius   = 2.0##  :: Double#

      v = MV.mandelbrot orbits radius x1 y1 x2 y2 w h :: U.Vector Int
  savePgm (I# w) (I# h) (I# orbits) v filename

MandelV.hs

{-# LANGUAGE MagicHash #-}
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE UnboxedTuples #-}

module MandelV where

import GHC.Prim
import GHC.Exts
import qualified Data.Vector.Unboxed as U

orbits :: Int# -> Double# -> Double# -> Double# -> Int#
orbits limit radius a b =
    go 0# 0.0## 0.0##
  where
    r2 = radius *## radius
    go  ::  Int# -> Double# -> Double# -> Int#
    go !n !x !y
      | unsafeCoerce# (n ==# limit)       = n
      | unsafeCoerce# (x2 +## y2 >=## r2) = n
      | otherwise                         = go (n +# 1#) (x2 -## y2 +## a) (2.0## *## x *## y +## b)
      where
        x2 = x *## x
        y2 = y *## y

mandelbrot :: Int# -> Double# -> Double# -> Double# -> Double# -> Double# -> Int# -> Int# -> U.Vector Int
mandelbrot limit radius x1 y1 x2 y2 w h = U.generate (I# (w *# h)) f
  where
    mx = (x2 -## x1) /## int2Double# (w -# 1#)
    my = (y2 -## y1) /## int2Double# (h -# 1#)
    f :: Int -> Int
    f (I# ix) = I# (orbits limit radius x y)
      where (# j,i #) = quotRemInt# ix w
            x          = mx *## (x1 +## int2Double# i)
            y          = my *## (y1 +## int2Double# j)

相关部分
mandel.cabal

executable ub-mandel
  main-is:             Main.hs
  other-modules:       MandelV
  -- other-extensions:    
  build-depends:       base >=4.8 && <4.9
               ,       vector >=0.11 && <0.12
               ,       ghc-prim
               ,       bytestring
  hs-source-dirs:      unboxed
  default-language:    Haskell2010
  ghc-options:         -O3