Эффективное преобразование 64-битного Double в ByteString - PullRequest
6 голосов
/ 02 декабря 2011

Я написал функцию для преобразования 64-битного Double в ByteString (безопасность архитектуры / типов на самом деле не проблема - давайте пока предположим, что Double - это 64-битное Word).Хотя функция ниже работает хорошо, мне интересно, есть ли более быстрый способ преобразования Double в ByteString.В приведенном ниже коде есть одна распаковка Word64 в список Word8, за которой следует обратный процесс (чтобы сделать его формат с прямым порядком байтов), а затем упаковка в ByteString.Код ниже:

{-# LANGUAGE MagicHash #-}
import GHC.Prim
import GHC.Types
import GHC.Word
import Data.Bits (shiftR)
import Data.ByteString (pack, unpack)
import Data.ByteString.Internal (ByteString)
import Text.Printf (printf)

encodeDouble :: Double -> ByteString
encodeDouble (D# x) = pack $ reverse $ unpack64 $ W64# (unsafeCoerce# x)

unpack64 :: Word64 -> [Word8]
unpack64 x = map (fromIntegral.(shiftR x)) [56,48..0]

-- function to convert list of bytestring into hex digits - for debugging
bprint :: ByteString -> String
bprint x = ("0x" ++ ) $ foldl (++) "" $ fmap (printf "%02x") $ unpack x

main = putStrLn $ bprint $ encodeDouble 7234.4

Пример вывода GHCi на Mac x86:

*Main> bprint $ encodeDouble 7234.4
"0x666666666642bc40"

Хотя код, кажется, работает хорошо, я планирую использовать его для кодирования множества значений Doubleв ByteString перед отправкой через IPC.Так что я буду признателен за подсказки, как сделать это быстрее, если таковые имеются.

Мне кажется, что double должен быть распакован в Word8, а затем упакован в ByteString.Так что, может быть, алгоритм в целом не может быть улучшен.Но использование более эффективной функции распаковки / упаковки, вероятно, будет иметь значение, если бы она была.

EDIT1: Я только что обнаружил еще одно осложнение на Mac (GHC 7.0.3) -Приведенный выше код не будет компилироваться в GHC из-за этой ошибки - я до сих пор тестировал в GHCi:

$ ghc -O --make t.hs
[1 of 1] Compiling Main             ( t.hs, t.o )

/var/folders/_q/33htc59519b3xq7y6xv100z40000gp/T/ghc6976_0/ghc6976_0.s:285:0:
    suffix or operands invalid for `movsd'

/var/folders/_q/33htc59519b3xq7y6xv100z40000gp/T/ghc6976_0/ghc6976_0.s:304:0:
    suffix or operands invalid for `movsd'

Итак, похоже, что я должен использовать FFI (cereal / data-binary-ieee754)пакет), пока эта ошибка не будет исправлена, или пока я не найду обходной путь.Похоже, что связано с GHC Ticket 4092 .Пожалуйста, исправьте меня, если это новая ошибка или другая ошибка.Пока я не могу его скомпилировать: (

EDIT2: Обновление кода для использования unsafeCoerce решает проблему компиляции. Код ниже с критерием Criterion:

{-# LANGUAGE MagicHash #-}
import GHC.Prim
import GHC.Types
import GHC.Word
import Data.Bits (shiftR)
import Data.ByteString (pack, unpack)
import Data.ByteString.Internal (ByteString)
import Text.Printf (printf)
import Unsafe.Coerce
import Criterion.Main

--encodeDouble :: Double -> ByteString
encodeDouble  x = pack $ reverse $ unpack64 $ unsafeCoerce x

unpack64 :: Word64 -> [Word8]
unpack64 x = map (fromIntegral.(shiftR x)) [56,48..0]

main = defaultMain [
        bgroup "encodeDouble" [
          bench "78901.234"  $ whnf encodeDouble 78901.234
          , bench "789.01" $ whnf encodeDouble 789.01
          ]
       ]

Выход критерия (усеченный):

estimating cost of a clock call...
mean is 46.09080 ns (36 iterations)

benchmarking encodeDouble/78901.234
mean: 218.8732 ns, lb 218.4946 ns, ub 219.3389 ns, ci 0.950
std dev: 2.134809 ns, lb 1.757455 ns, ub 2.568828 ns, ci 0.950

benchmarking encodeDouble/789.01
mean: 219.5382 ns, lb 219.0744 ns, ub 220.1296 ns, ci 0.950
std dev: 2.675674 ns, lb 2.197591 ns, ub 3.451464 ns, ci 0.950

При дальнейшем анализе большая часть узкого места, кажется, находится в unpack64. Принуждение занимает ~ 6ns. Unpack64 занимает ~ 195ns. Распаковка word64 как списка word8 вполнедорого здесь.

Ответы [ 3 ]

4 голосов
/ 02 декабря 2011

Я недавно добавил поддержку IEEE-754 с плавающей точкой к cereal, и вы можете найти похожие функции для binary в data-binary-ieee754.Вот пример использования версии cereal для округления pi до ByteString и обратно:

Prelude Data.Serialize> runGet getFloat64be $ runPut $ putFloat64be pi
Right 3.141592653589793

Для быстрого преобразования используется трюк с массивами ST;см. этот предыдущий вопрос для получения более подробной информации.

Обновление : О, я должен знать, как использовать вызовы, которые я внес в библиотеку ...

Обновление x2 : Что касается сбоя компиляции, я не думаю, что это квалифицируется как ошибка.

Я не слишком внимательно посмотрел на сгенерированную сборку для этого конкретного кода, но операнды инструкции movsd запутались.Из §11.4.1.1 руководства Intel x86 :

MOVSD (скалярное перемещение с плавающей запятой двойной точности) передает 64-битный операнд с плавающей запятой двойной точностииз памяти в нижнее четверное слово регистра XMM или наоборот, или между регистрами XMM.

В неоптимизированном коде у вас есть тонкие инструкции, такие как movsd LnTH(%rip),%xmm0, но в коде -O,вы видите такие вещи, как movsd Ln2cJ(%rip),%rax, где %rax - это регистр общего назначения, а не регистр XMM.

Оптимизатор, вероятно, делает предположения о представлениях данных, которые ему необходимо перемещать между регистрами, в зависимости от типа используемых данных.unsafeCoerce и друзья опровергают эти предположения, поэтому, когда селектор инструкций считает, что он выбирает правильную операцию для D#, он на самом деле испускает код, который пытается заполнить то, что D# там, где W64# будет подходящим образом.

Поскольку для обработки этого требования оптимизатору необходимо отказаться от многих предположений, которые позволяют ему генерировать лучший код при нормальных обстоятельствах, я склонен сказать, что это не ошибка, а скорее хорошая история, почему unsafeфункции несут предостережение emptor.

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

Следуя советам acfoltzer (исходный код злаков) и Daniel Fischer (unsafeCreate), я написал приведенный ниже код, который хорошо работает для моего варианта использования и тоже быстр:

{-#LANGUAGE MagicHash #-}
import Data.ByteString (pack, unpack)
import Data.ByteString.Internal (unsafeCreate,ByteString)
import Data.Bits (shiftR)
import GHC.Int (Int64)
import GHC.Prim
import GHC.Types
import GHC.Word
import Unsafe.Coerce
import Criterion.Main
import Foreign

-- | Write a Word64 in little endian format
putWord64le :: Word64 -> Ptr Word8 -> IO()
putWord64le w p = do
  poke p               (fromIntegral (w)           :: Word8)
  poke (p `plusPtr` 1) (fromIntegral (shiftR w  8) :: Word8)
  poke (p `plusPtr` 2) (fromIntegral (shiftR w 16) :: Word8)
  poke (p `plusPtr` 3) (fromIntegral (shiftR w 24) :: Word8)
  poke (p `plusPtr` 4) (fromIntegral (shiftR w 32) :: Word8)
  poke (p `plusPtr` 5) (fromIntegral (shiftR w 40) :: Word8)
  poke (p `plusPtr` 6) (fromIntegral (shiftR w 48) :: Word8)
  poke (p `plusPtr` 7) (fromIntegral (shiftR w 56) :: Word8)

{-# INLINE putWord64le #-}

encodeDouble :: Double -> ByteString
encodeDouble x = unsafeCreate 8 (putWord64le $ unsafeCoerce x)

main :: IO ()
main = defaultMain [
        bgroup "encodeDouble" [
          bench "78901.234"  $ whnf encodeDouble 78901.234
          , bench "789.01" $ whnf encodeDouble 789.01
          ]
       ]

Вывод критерия(усечено):

estimating cost of a clock call...
mean is 46.80361 ns (35 iterations)
found 5 outliers among 35 samples (14.3%)
  3 (8.6%) high mild
  2 (5.7%) high severe

benchmarking encodeDouble/78901.234
mean: 18.80689 ns, lb 18.73805 ns, ub 18.97247 ns, ci 0.950
std dev: 516.7499 ps, lb 244.8588 ps, ub 1.043685 ns, ci 0.950

benchmarking encodeDouble/789.01
mean: 18.96963 ns, lb 18.90986 ns, ub 19.06127 ns, ci 0.950
std dev: 374.2191 ps, lb 275.3313 ps, ub 614.4281 ps, ci 0.950

От ~ 220нс до ~ 19нс, хорошо!Я не делал ничего особенного в компиляции.Просто флаг -O будет использоваться в GHC7 (Mac, x86_64).

Теперь попробуем выяснить, как это сделать быстро с помощью списка парных чисел!

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

Обратите внимание, что использование unsafeCoerce# здесь опасно, в документах сказано:

Преобразование распакованного типа в другой распакованный тип того же размера (, но без приведения между плавающей точкойи целые типы )

Что касается скорости, может быть быстрее избежать промежуточного списка и напрямую записать в память через unsafeCreate из Data.ByteString.Internal.

...