Performance improvement in unsigned integers function

Question

Any Word32 number can be expressed as a linear combination of Word8 numbers as follows:

x = a + b * 2^8 + c * 2^16 + d * 2^24

In other words, this is the representation of x in the base 2^8. In order to obtain these factors, I implemented the following function:

word32to8 :: Word32 -> (Word8,Word8,Word8,Word8)
word32to8 n = (fromIntegral a,fromIntegral b,fromIntegral c,fromIntegral d)
  where
   (d,r1) = divMod n  (2^24)
   (c,r2) = divMod r1 (2^16)
   (b,a)  = divMod r2 (2^8)

It works properly but, since my program is using this function bunch of times, I thought that you guys can give me an idea of how to improve (if possible) the performance of this operation. Any minor improvement is good to me, either in time or space. To me, it looks like it is so simple that a performance improvement can't be achieved, but I still wanted to ask the question, just in case there is something I am missing.

By the way, I feel annoyed with all the repetitions of fromIntegral, but the conversion is necessary so the types can match.

Thanks in advance.

Answer 1

You might get a major performance boost by defining a distinct type for the result, making use of a GHC extension and using bitwise operations instead:

data Split =
    Split {-# UNPACK #-} !Word8
          {-# UNPACK #-} !Word8
          {-# UNPACK #-} !Word8
          {-# UNPACK #-} !Word8

splitWord :: Word32 -> Split
splitWord x =
    Split (fromIntegral x)
          (fromIntegral (shiftR x 8))
          (fromIntegral (shiftR x 16))
          (fromIntegral (shiftR x 24))

This code is more than four times faster than your original function by using the following improvements:

• Instead of using the nonstrict tuple type I have defined a strict type Split.
• I have unpacked the fields of that type to get rid of most memory allocations and garbage collections.
• I have switched from divMod to shiftR. You don't actually need to modulo operation, so I dropped it.

Another way to get a speed improvement is by not going through a concrete data type at all. You probably want to perform calculations with the bytes, so we skip the step of storing and retrieving them. Instead we pass the splitWord function a continuation:

splitWord :: (Word8 -> Word8 -> Word8 -> Word8 -> r) -> Word32 -> r
splitWord k x =
    k (fromIntegral x)
      (fromIntegral (shiftR x 8))
      (fromIntegral (shiftR x 16))
      (fromIntegral (shiftR x 24))

If you still want to save the bytes, you can just pass the Split constructor as the continuation:

splitWord Split 123456

But now you can also just perform the calculation you wanted to perform:

splitWord (\a b c d -> a + b + c + d) 123456