5

我为下面的数据类型写了一个可存储的向量实例（这里的原始问题）：

data Atoms = I GHC.Int.Int32 | S GHC.Int.Int16

为可存储向量定义这些实例的代码如下。虽然我使用下面的代码获得了非常好的性能，但我对提高该可存储实例的性能的通用建议非常感兴趣。通过一般性建议，我的意思是：

  • 它不特定于 GHC 编译器版本。您可以假设 GHC 6.12.3+ 排除了早期版本中存在的性能错误，并且与此处的代码相关。
  • 特定于平台的建议是可以的。您可以假设 x86_64 Linux 平台。
  • 比利用硬件特定优化的建议更有价值的是算法改进（大 O）形式的通用建议。但是，鉴于这里的 peek/poke 等基本操作，据我所知，算法改进的余地不大（因此更有价值，因为它是一种稀缺商品：）
  • x86_64 的编译器标志是可接受的（例如，告诉编译器删除浮点安全检查等）。我正在使用“-O2 --make”选项来编译代码。

如果有任何已知的优秀库源代码可以做类似的事情（即，为联合/递归数据类型定义可存储实例），我将对检查它们非常感兴趣。

import Data.Vector.Storable
import qualified Data.Vector.Storable as V
import Foreign
import Foreign.C.Types
import GHC.Int

data Atoms = I GHC.Int.Int32 | S GHC.Int.Int16
                deriving (Show)

instance Storable Atoms where
  sizeOf _ = 1 + sizeOf (undefined :: Int32)
  alignment _ = 1 + alignment (undefined :: Int32)

  {-# INLINE peek #-}
  peek p = do
            let p1 = (castPtr p::Ptr Word8) `plusPtr` 1 -- get pointer to start of the    element. First byte is type of element
            t <- peek (castPtr p::Ptr Word8)
            case t of
              0 -> do
                    x <- peekElemOff (castPtr p1 :: Ptr GHC.Int.Int32) 0
                    return (I x)
              1 -> do
                    x <- peekElemOff (castPtr p1 :: Ptr GHC.Int.Int16) 0
                    return (S x)

  {-# INLINE poke #-}
  poke p x = case x of
      I a -> do
              poke (castPtr p :: Ptr Word8) 0
              pokeElemOff (castPtr p1) 0 a
      S a -> do
              poke (castPtr p :: Ptr Word8) 1
              pokeElemOff (castPtr p1) 0 a
      where  p1 = (castPtr p :: Ptr Word8) `plusPtr` 1 -- get pointer to start of the     element. First byte is type of element

更新：

根据 Daniel 和 dflemstr 的反馈，我重写了对齐方式，并将构造函数更新为 Word32 类型而不是 Word8。但是，似乎要使其有效，数据构造函数也应该更新为具有未打包的值——这是我的疏忽。我应该首先编写数据构造函数来获得解压缩的值（参见John Tibbell 的性能幻灯片- 幻灯片 #49）。因此，重写数据构造函数，再加上对齐和构造函数的更改，对性能产生了很大影响，将函数比向量提高了大约 33%（我的基准测试中的一个简单的 sum 函数）。以下相关更改（警告 - 不可移植，但对我的用例来说不是问题）：

数据构造函数更改：

data Atoms = I {-# UNPACK #-} !GHC.Int.Int32 | S {-# UNPACK #-} !GHC.Int.Int16

可存储的 sizeof 和对齐更改：

instance Storable Atoms where
  sizeOf _ = 2*sizeOf (undefined :: Int32)
  alignment _ = 4

  {-# INLINE peek #-}
  peek p = do
            let p1 = (castPtr p::Ptr Word32) `plusPtr` 1
            t <- peek (castPtr p::Ptr Word32)
            case t of
              0 -> do
                    x <- peekElemOff (castPtr p1 :: Ptr GHC.Int.Int32) 0
                    return (I x)
              _ -> do
                    x <- peekElemOff (castPtr p1 :: Ptr GHC.Int.Int16) 0
                    return (S x)

  {-# INLINE poke #-}
  poke p x = case x of
      I a -> do
              poke (castPtr p :: Ptr Word32) 0
              pokeElemOff (castPtr p1) 0 a
      S a -> do
              poke (castPtr p :: Ptr Word32) 1
              pokeElemOff (castPtr p1) 0 a
      where  p1 = (castPtr p :: Ptr Word32) `plusPtr` 1
4

2 回答 2

3

四字节或八字节对齐的内存访问通常比奇数对齐的访问快得多。您的实例的对齐可能会自动四舍五入到八个字节，但我建议至少使用显式八字节对齐进行测量，使用 32 位（Int32或Word32）作为构造函数标记并读取和写入两种类型的有效负载作为Int32. 这会浪费比特，但很有可能它会更快。由于您使用的是 64 位平台，因此使用 16 字节对齐和读/写可能会更快Int64。基准测试、基准测试、基准测试，找出最适合您的方法。

于 2011-12-09T19:59:38.247 回答
1

如果速度是您所追求的，那么这种位包装不是正确的方向。

处理器总是处理字大小的操作，这意味着如果你有一个 32 位处理器，处理器可以（物理）处理的最小内存量是 32 位或 4 字节（对于 64 位处理器，它64 位或 8 个字节）。更远; 处理器只能在字边界加载内存，这意味着字节地址是字大小的倍数。

因此，如果您使用 5 的对齐方式（在这种情况下），则意味着您的数据存储方式如下：

|  32 bits  |  32 bits  |  32 bits  |  32 bits  |
 [    data    ] [    data    ] [    data    ]
 00 00 00 00 01 01 00 01 00 00 00 12 34 56 78 00
 IX Value       IX Value XX XX IX Value

IX = Constructor index
Value = The stored value
XX = Unused byte

如您所见，数据与字边界越来越不同步，使得处理器/程序必须做更多的工作来访问每个元素。

如果您将对齐增加到 8（64 位），您的数据将像这样存储：

|  32 bits  |  32 bits  |  32 bits  |  32 bits  |  32 bits  |  32 bits  |
 [    data    ]          [    data    ]          [    data    ]
 00 00 00 00 01 00 00 00 01 00 01 00 00 00 00 00 00 12 34 56 78 00 00 00
 IX Value       XX XX XX IX Value XX XX XX XX XX IX Value       XX XX XX

这会使您“浪费”每个元素 3 个字节，但您的数据结构会快得多，因为可以使用更少的指令和对齐的内存负载来加载和解释每个数据。

如果您仍然要使用 8 个字节，则不妨将构造函数索引为 Int32，因为无论如何您都没有将这些字节用于其他任何内容，并且使所有基准元素字对齐进一步提高了速度：

|  32 bits  |  32 bits  |  32 bits  |  32 bits  |  32 bits  |  32 bits  |
 [        data         ] [        data         ] [        data         ]
 00 00 00 00 00 00 00 01 00 00 00 01 00 01 00 00 00 00 00 00 12 34 56 78
 Index       Value       Index       Value XX XX Index       Value

这是在当前处理器架构上为更快的数据结构付出的代价。

于 2011-12-09T20:37:06.333 回答