Improving performance in unsigned integers
Any number Word32
can be expressed as a linear combination of numbers Word8
as follows:
x = a + b * 2^8 + c * 2^16 + d * 2^24
In other words, it is x
a database view 2^8
. To get these factors, I ran 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 correctly, but since my program uses this function multiple times, I thought you guys could give me an idea of how to improve (if possible) the performance of this operation. Any minor improvement is good for me, in time or space. It looks so easy to me that performance improvements cannot be achieved, but I still wanted to ask a question in case I was missing something.
By the way, I get annoyed with all the repetition fromIntegral
, but the conversion is necessary so the types can match.
Thanks in advance.
source to share
You can get significant performance gains by specifying a separate result type using the 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 the original function using the following enhancements:
- Instead of using a non-strict tuple type, I have defined a strong type
Split
. - I unpacked fields of this type to get rid of most memory allocations and garbage collections.
- I switched from
divMod
toshiftR
. You don't really need to work modulo, so I ditched it.
Another way to achieve speed improvements is with a not-so-specific data type. You probably want to do calculations with bytes, so we'll skip the step of storing and retrieving them. Instead, we pass the function to a splitWord
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 keep the bytes, you can simply pass the constructor Split
as a continuation:
splitWord Split 123456
But now you can just do the calculation you want to do:
splitWord (\a b c d -> a + b + c + d) 123456
source to share