2

I'm now developing binary parsing program using Haskell. I currently found out that strict/lazy both BitGet seems to be very slow and surprisingly allocate a lot of memory.

I tested below code (built with -O2), such as parsing entire bits in the input file, and figure out the profiling result. For this example, I used the 1,819,173 bytes binary file.

Strict version:

import Prelude                   as P
import System.Environment        (getArgs)
import Data.ByteString           as B
import Data.Binary.Strict.BitGet

coreFunc :: Int -> BitGet Int
coreFunc len = f len 0
    where
    f 0 r = return r
    f l _ = do
        b <- getBit
        f (l - 1) $ if b then 1 else 0

mainFunc :: B.ByteString -> IO ()
mainFunc bs =
    case runBitGet bs (coreFunc ((B.length bs) * 8)) of
        Left emsg -> error emsg
        Right r  -> print $ show r

main :: IO ()
main = do
    args <- getArgs
    case args of
        []    -> return ()
        (x:_) -> (do
            bs <- B.readFile x
            mainFunc bs
            return ()
            )

-- profiling result --
total time  =        1.74 secs   (1741 ticks @ 1000 us, 1 processor)
total alloc = 7,948,043,192 bytes  (excludes profiling overheads)

Lazy version:

import Prelude                   as P
import System.Environment        (getArgs)
import Data.ByteString.Lazy      as B
import Data.Binary.Bits.Get
import Data.Binary.Get
import Data.Int                  (Int64)

coreFunc :: Int64 -> BitGet Int
coreFunc len = f len 0
    where
    f 0 r = return r
    f l _ = do
        b <- getBool
        f (l - 1) $ if b then 1 else 0

mainFunc :: B.ByteString -> IO ()
mainFunc bs = do
    let r = runGet (runBitGet (coreFunc ((B.length bs) * 8))) bs
    print $ show r

main :: IO ()
main = do
    args <- getArgs
    case args of
        []    -> return ()
        (x:_) -> (do
            bs <- B.readFile x
            mainFunc bs
            return ()
            )

-- profiling result --
total time  =        2.21 secs   (2207 ticks @ 1000 us, 1 processor)
total alloc = 6,405,531,680 bytes  (excludes profiling overheads)

I want to ask that:

  • How can I improve this performance?
  • Can I profile inside of the BitGet library behavior?
  • Are there the other way to parse binary bits?
4
  • Are you sure you need to be doing bit level parsing for the whole of your binary parser? Generally for binary parsing I would use the regular Data.Binary library and mask/bit twiddle with functions from Data.Word. I've noticed there are a couple of BitGet packages on Hackage, so they may have different performance characteristics if you really need to work at the bit level. Mar 23, 2014 at 8:12
  • Yes. I'm developing H.26X decoder for my study. It needs bit level parsing. Mar 23, 2014 at 12:34
  • You can certainly profile the library if you build it with profiling turned on. Mar 24, 2014 at 15:03
  • I think that I can profile libraries by enabling enable-library-profiling in the .cabal/config, and re-install all the libraries, but had no luck. Am I missing something? Mar 25, 2014 at 16:17

1 Answer 1

2

It seems like your coreFunc is supposed to skip forward some (len - 1) number of bits, then read a single bit as an 0 or 1 and return it in the BitGet monad. If that's the intent, something like this will be much more efficient.

I'm using the binary-bits package:

import Control.Applicative
import Data.Binary.Get

coreFunc :: Int -> Get Int
coreFunc len =
    fromEnum <$> runBitGet (block (skip (len - 1) *> bool)

skip :: Int -> BitGet ()
skip n = byteString bytes *> word64be bits *> pure ()
    where (bytes, bits) = quotRem n 8 -- sizeOf Word8             

Unfortunately the package does not have a skip function to let us skip n bits, which the binary package it's based off includes, so I've had to write my own. It's possible a more efficient version could be written with access to the Block internals, but the library might already be optimizing it well enough that theres no benefit.

I'd like to benchmark this version against yours to get an accurate comparison, can you provide the binary file you use for testing?

3
  • Thanks for your answer. But if you try to skipping almost every bits, it is not the thing that I want to know. I want to know 'why so many bytes are allocated for parsing (8 * 1,819,173 =) 14,553,384 bits' and how to reduce it. Mar 24, 2014 at 5:47
  • Again, if you'd provide a test input file I could do better than speculate. But my guess is that to parse a single bit, you probably need to allocate a larger Word, mask it to get the single bit, then allocate a Bool which is then GC'd in the next iteration. If the intent is to skip over some number of bits, it's best to let the compiler know it shouldn't allocate anything (which my version of coreFunc does)
    – cdk
    Mar 24, 2014 at 13:45
  • Sorry for my misunderstanding. I used 'HPCV_BRCM_A.264' which included in Rec._ITU-T_H.264.1(2012-01)_FRExt_Bitstreams. Mar 25, 2014 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.