为union结构编写可存储的向量定义时的优化建议

Question

我为下面的数据类型写了一个可存储的矢量实例(原始问题在这里):

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

用于为可存储矢量定义这些实例的代码如下.虽然我使用下面的代码获得了非常好的性能,但我对通用建议非常感兴趣,以提高该可存储实例的性能.通用建议,我的意思是:

• 它不是GHC编译器版本特有的.您可以假设GHC 6.12.3+排除性能错误(如果早期版本中存在任何错误,并且与此处的代码相关).
• 特定于平台的建议是可以的.您可以假设x86_64 Linux平台.
• 与利用特定于硬件的优化的建议相比,更多以算法改进(大O)形式的通用建议非常受重视.但是,考虑到像偷看/捅这样的基本操作,据我所知,算法改进的空间不大(因此它更有价值,因为它是一种稀缺的商品:)
• x86_64的编译器标志是可接受的(例如,告诉编译器有关删除浮点安全检查等).我使用"-O2 --make"选项来编译代码.

如果有任何已知的好的库源代码做类似的事情(即,为union/recursive数据类型定义可存储的实例),我将非常感兴趣检查它们.

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%(在我的基准测试中是一个简单的求和函数).下面的相关更改(警告 - 不可移植,但对我的用例来说不是问题):

数据构造函数更改:

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

可存储的尺寸和对齐变化:

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

Answer 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

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