Низкая производительность разбора двоичного файла в haskell - PullRequest
Новая
       10

Низкая производительность разбора двоичного файла в haskell

15 голосов
/ 05 марта 2012

У меня есть набор двоичных записей, упакованных в файл, и я читаю их, используя Data.ByteString.Lazy и Data.Binary.Get. В моей текущей реализации 8-мегабайтный файл занимает 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

Что я могу сделать, чтобы сделать это быстрее?

Ответы [ 2 ]

20 голосов
/ 06 марта 2012

Небольшой рефакторинг (в основном, влево) дает гораздо лучшую производительность и значительно снижает накладные расходы 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

И соответствующая статистика времени выполнения. Несмотря на то, что номера распределения близки, GC и максимальный размер кучи в ревизиях немного отличаются.

Все приведенные здесь примеры были построены с использованием GHC 7.4.1 -O2.

Исходный источник, запускается с + RTS -K1G -RTS из-за чрезмерного использования стека: 

     426,003,680 bytes allocated in the heap
     443,141,672 bytes copied during GC
      99,305,920 bytes maximum residency (9 sample(s))
             203 MB total memory in use (0 MB lost due to fragmentation)

  Total   time    0.62s  (  0.81s elapsed)

  %GC     time      83.3%  (86.4% elapsed)

Редакция Даниила: 

     357,851,536 bytes allocated in the heap
     220,009,088 bytes copied during GC
      40,846,168 bytes maximum residency (8 sample(s))
              85 MB total memory in use (0 MB lost due to fragmentation)

  Total   time    0.24s  (  0.28s elapsed)

  %GC     time      69.1%  (71.4% elapsed)

И этот пост: 

     290,725,952 bytes allocated in the heap
         109,592 bytes copied during GC
          78,704 bytes maximum residency (10 sample(s))
               2 MB total memory in use (0 MB lost due to fragmentation)

  Total   time    0.06s  (  0.07s elapsed)

  %GC     time       5.0%  (6.0% elapsed)
17 голосов
/ 05 марта 2012

Ваш код декодирует файл размером 8 МБ менее чем за одну секунду (ghc-7.4.1) - конечно, я скомпилировал с -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, чтобы иметь ленивые поля, вы все равно можете декодировать через тип со строгими полями и map преобразование по списку результатов, чтобы извлечь выгоду из более строгого декодирования.

Однако код все еще тратит много времени на сборку мусора, поэтому дальнейшие улучшения все же могут быть необходимы.

...