Предложения по оптимизации при написании хранимого векторного определения для структуры объединения - PullRequest
Новая
       23

Предложения по оптимизации при написании хранимого векторного определения для структуры объединения

5 голосов
/ 09 декабря 2011

Я написал сохраняемый экземпляр вектора для типа данных ниже ( оригинальный вопрос здесь ): 

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

Код для определения этих экземпляров для Сохраняемого вектора приведен ниже.Хотя я получаю очень хорошую производительность с помощью приведенного ниже кода, я очень заинтересован в общих предложениях по улучшению производительности этого хранимого экземпляра.Под общим предложением я имею в виду следующее:

  • Это не относится к версии компилятора GHC.Вы можете предположить, что GHC 6.12.3+ исключает ошибки производительности, если они присутствуют в более ранних версиях и имеют отношение к коду здесь.
  • Предложения для конкретной платформы в порядке.Вы можете предположить, что платформа Linux x86_64.
  • Общее предложение в форме улучшения алгоритма (большой 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

Обновление:

Основываясь на отзывах Дэниела и dflemstr, я переписал выравнивание, а также, обновил конструктор, чтобы иметь тип Word32 вместо Word8.Но, похоже, чтобы это было эффективным, конструктор данных тоже должен быть обновлен, чтобы иметь распакованные значения - это было упущением с моей стороны.Я должен был написать конструктор данных, чтобы сначала иметь распакованные значения (см. слайды производительности Джона Тиббелла - слайд № 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

Ответы [ 2 ]

3 голосов
/ 09 декабря 2011

Доступ к памяти с выравниванием в четыре или восемь байтов обычно намного быстрее, чем доступ со странным выравниванием.Может случиться так, что выравнивание для вашего экземпляра автоматически округляется до восьми байтов, но я бы посоветовал по крайней мере измерить с явным выравниванием восьми байтов, используя 32 бит (Int32 или Word32) для тега конструктора и чтенияи запись обоих типов полезных нагрузок как Int32.Это будет потрачено впустую, но есть большая вероятность, что это будет быстрее.Поскольку вы работаете на 64-битной платформе, может быть даже быстрее использовать 16-байтовое выравнивание и чтение / запись Int64.Ориентир, эталон, эталон, чтобы узнать, что вам больше всего подходит.

1 голос
/ 10 декабря 2011

Если скорость - то, что вам нужно, то этот вид битовой упаковки не является правильным направлением.

Процессор всегда имеет дело с операциями размером с слово, что означает, что если у вас есть, например, 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

Это цена, которую вы должны заплатить за более быстрые структуры данных в современных процессорных архитектурах.

...