How to efficiently byteswap binary data in Haskell

user_2965738 0
Viewed 79

byteswap below does what I want, but I fear it is inefficient for larger chunks of binary data. Is there an efficient library function or something I can use?

{-# LANGUAGE OverloadedStrings #-}

import qualified Data.ByteString as B (ByteString, length, append, cons, foldl)

byteswap :: B.ByteString -> B.ByteString
byteswap = let
  swapper (collector, result) byte = let
    updated = B.cons byte collector
    in if 3 < B.length updated then ("", B.append result updated) else (updated, result)
  in snd . B.foldl swapper ("", "")

main = print $ byteswap "1234abcdXYZ"

Prints 4321dcba.

endianness binaryfiles haskell performance
1 Answers

The slow part of your code is append which is linear in the size of the bytestring that you are generating, hence your program will take at least quadratic time.

Instead you can use a list as intermediate structure (which ideally would get fused away) and pack the whole result in one go:

byteswap :: B.ByteString -> B.ByteString
byteswap xs = B.pack
  [ B.index xs $ i * 4 + j
  | i <- [0 .. B.length xs `quot` 4 - 1]
  , j <- [3,2,1,0]
  ]

This can do 10 million bytes in 3 seconds on my machine.

You can speed it up by using unsafe internal bytestring functions:

byteswap :: B.ByteString -> B.ByteString
byteswap xs = unsafePackLenBytes (B.length xs `quot` 4 * 4)
  [ unsafeIndex xs $ i * 4 + j
  | i <- [0 .. B.length xs `quot` 4 - 1]
  , j <- [3,2,1,0]
  ]

And with my patch for fusion of unsafePackLenBytes I get 10 million bytes swapped in 6 ms.

user_152075680
Related