How to efficiently byteswap binary data in Haskell

Question

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.

Noughtmare · Accepted Answer · 2022-03-03 21:17:53Z

2

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.

edited Mar 3, 2022 at 21:17

answered Mar 3, 2022 at 17:11

Noughtmare

11.3k1 gold badge18 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

leftaroundabout Over a year ago

Not sure I approve of writing this with do syntax instead of the obvious enough list comprehension...

Collectives™ on Stack Overflow

How to efficiently byteswap binary data in Haskell

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related