为什么这个Haskell代码比C等效代码慢得多？未装箱的载体和刘海已经使用过

Question

我在Haskell和C中编写了一个简短的Mandelbrot Set生成器,发现C版本的运行速度比Haskell版本快20倍.虽然我预计Haskell会变慢,但考虑到我已经在使用未装箱的矢量和刘海来避免过度的篡改,我没想到会超过一个数量级.

分析显示大部分时间都花费在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(剖析报告)

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的博客文章

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

为了完整起见,unboxed,bytestring版本:

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