无符号整数函数的性能改进

Question

任何Word32数字都可以表示为Word8数字的线性组合,如下所示:

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

换句话说,这是x在基础中的表示2^8.为了获得这些因素,我实现了以下功能:

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)

它工作正常,但是,由于我的程序多次使用这个函数,我认为你们可以让我知道如何改进(如果可能的话)这个操作的性能.无论是时间还是空间,任何微小的改进对我都有好处.对我来说,它看起来很简单,无法实现性能提升,但我仍然想问这个问题,以防万一我遗漏了什么.

顺便说一句,我对所有的重复感到恼火fromIntegral,但转换是必要的,所以类型可以匹配.

提前致谢.

Answer 1

您可以通过为结果定义不同的类型来获得主要的性能提升,使用GHC扩展并使用按位运算:

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))

通过使用以下改进,此代码比原始函数快四倍:

• 我没有使用非严格元组类型,而是定义了严格类型Split.
• 我已解压缩该类型的字段以摆脱大多数内存分配和垃圾收集.
• 我已经改用divMod了shiftR.你实际上并不需要模运算,所以我放弃了它.

提高速度的另一种方法是根本不通过具体的数据类型.您可能希望使用字节执行计算,因此我们跳过存储和检索它们的步骤.相反,我们将splitWord函数传递给延续:

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))

如果您仍想保存字节,可以将Split构造函数作为延续传递:

splitWord Split 123456

但现在您也可以执行您想要执行的计算:

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