Haskell中解析二进制文件性能差

Question

我有一组二进制记录打包到文件中，正在使用Data.ByteString.Lazy和Data.Binary.Get读取它们。根据我的当前实现，一个8Mb的文件需要6秒才能解析完成。

import qualified Data.ByteString.Lazy as BL
import Data.Binary.Get

data Trade = Trade { timestamp :: Int, price :: Int ,  qty :: Int } deriving (Show)

getTrades = do
  empty <- isEmpty
  if empty
    then return []
    else do
      timestamp <- getWord32le          
      price <- getWord32le
      qty <- getWord16le          
      rest <- getTrades
      let trade = Trade (fromIntegral timestamp) (fromIntegral price) (fromIntegral qty)
      return (trade : rest)

main :: IO()
main = do
  input <- BL.readFile "trades.bin" 
  let trades = runGet getTrades input
  print $ length trades

有什么方法可以让这个更快吗？

- Dave Anderson

---

《Real World Haskell》一书中有一章关于性能分析，同时在 Stack Overflow 上也有一些标记为 [Haskell]+[performance] 的问题，或许对您有所帮助。 - epsilonhalbe

@epsilonhalbe 谢谢，我已经进行了充分的搜索，这个模式是Data.Binary.Get文档中的模式。我猜测这是一个“几乎尾递归”问题，但是对于我来说有点难以理解。 - Dave Anderson

这很棘手，因为Data.Binary.Get看起来很严格 - 我之前发表过一条评论，试图获得更好的惰性，但我已将其删除，因为它不适用。丹尼尔·菲舍尔的答案向您展示了如何更好地执行严格操作。 - stephen tetley

Answer 1

稍微重构一下（基本上是一个左折叠），能够显著提高性能并大幅降低 GC 开销，解析一个 8388600 字节的文件。

{-# LANGUAGE BangPatterns #-}
module Main (main) where

import qualified Data.ByteString.Lazy as BL
import Data.Binary.Get

data Trade = Trade
  { timestamp :: {-# UNPACK #-} !Int
  , price     :: {-# UNPACK #-} !Int 
  , qty       :: {-# UNPACK #-} !Int
  } deriving (Show)

getTrade :: Get Trade
getTrade = do
  timestamp <- getWord32le
  price     <- getWord32le
  qty       <- getWord16le
  return $! Trade (fromIntegral timestamp) (fromIntegral price) (fromIntegral qty)

countTrades :: BL.ByteString -> Int
countTrades input = stepper (0, input) where
  stepper (!count, !buffer)
    | BL.null buffer = count
    | otherwise      =
        let (trade, rest, _) = runGetState getTrade buffer 0
        in stepper (count+1, rest)

main :: IO()
main = do
  input <- BL.readFile "trades.bin"
  let trades = countTrades input
  print trades

还有相关的运行时统计信息。尽管分配数量相近，但垃圾收集和最大堆大小在不同版本之间有显著差异。

这里的所有示例都是使用 GHC 7.4.1 -O2 构建的。

原始代码由于堆栈空间使用过多而通过 +RTS -K1G -RTS 运行：

     426,003,680 字节在堆上分配
     443,141,672 字节在 GC 期间复制
      99,305,920 字节最大驻留内存 (9 个样本)
             203 MB 总共使用的内存 (因碎片而丢失 0 MB)
总时间   0.62 秒  (  0.81 秒经过)
%GC     时间      83.3%  (86.4% 经过)

Daniel 的版本：

     357,851,536 字节在堆上分配
     220,009,088 字节在 GC 期间复制
      40,846,168 字节最大驻留内存 (8 个样本)
              85 MB 总共使用的内存 (因碎片而丢失 0 MB)
总时间   0.24 秒  (  0.28 秒经过)
%GC     时间      69.1%  (71.4% 经过)

以及这个帖子：

     290,725,952 字节在堆上分配
         109,592 字节在 GC 期间复制
          78,704 字节最大驻留内存 (10 个样本)
               2 MB 总共使用的内存 (因碎片而丢失 0 MB)
总时间   0.06 秒  (  0.07 秒经过)
%GC     时间       5.0%  (6.0% 经过)

- Nathan Howell

Answer 2

你的代码在这里（ghc-7.4.1）中解码了一个8MB的文件，少于一秒钟的时间 - 当然我使用了-O2进行编译。

但是，它需要大量的堆栈空间。您可以通过在适当的位置增加更多严格性，并使用累加器来收集已解析的交易，从而减少需要：

• 时间
• 堆栈空间
• 堆空间

{-# LANGUAGE BangPatterns #-}
module Main (main) where

import qualified Data.ByteString.Lazy as BL
import Data.Binary.Get

data Trade = Trade { timestamp :: {-# UNPACK #-} !Int
                   , price :: {-# UNPACK #-} !Int 
                   , qty :: {-# UNPACK #-} !Int
                   } deriving (Show)

getTrades :: Get [Trade]
getTrades = go []
  where
    go !acc = do
      empty <- isEmpty
      if empty
        then return $! reverse acc
        else do
          !timestamp <- getWord32le
          !price <- getWord32le
          !qty <- getWord16le
          let !trade = Trade (fromIntegral timestamp) (fromIntegral price) (fromIntegral qty)
          go (trade : acc)

main :: IO()
main = do
  input <- BL.readFile "trades.bin"
  let trades = runGet getTrades input
  print $ length trades

严格性和解包确保不会留下任何工作，以免在引用应该已经被遗忘的ByteString部分时产生后果。

如果您需要Trade具有惰性字段，仍然可以通过具有严格字段的类型进行解码，并将转换映射到结果列表上，以从更严格的解码中受益。

然而，代码仍然花费大量时间进行垃圾回收，因此可能仍需要进一步改进。

- Daniel Fischer

---

非常感谢你的出色回答！你帮助一个新手升级了一点。 - Dave Anderson