Conversión de Double de 64 bits a ByteString de manera eficiente

Question

Escribí una función para convertir Double de 64 bits a ByteString (arquitectura/seguridad tipo no es realmente un problema, supongamos por ahora que el doble es Word de 64 bits). Si bien la función siguiente funciona bien, me pregunto si existe una forma más rápida de convertir Double en ByteString. En el código siguiente, hay un desempaquetado de Word64 en la lista de Word8, seguido de reverso (para hacerlo en formato little endian), y luego empaquetado en ByteString. El código es el siguiente:

{-# 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 

Una salida GHCi muestra en Mac X 86:

*Main> bprint $ encodeDouble 7234.4 
"0x666666666642bc40" 

Mientras que el código parece funcionar bien, tengo la intención de usarlo para codificar gran cantidad de valores Double en ByteString antes de enviar sobre IPC. Por lo tanto, agradeceré sugerencias para hacerlo más rápido, si es que hay alguno.

Me parece que el doble se debe desempaquetar en Word8, y luego se empaqueta en ByteString. Entonces, puede ser el algoritmo general tal como es, no se puede mejorar mucho. Pero, usar una función desempaquetar/empacar más eficiente probablemente marcará la diferencia, si es que hay una.

EDIT1: acabo de descubrir otra complicación en Mac (GHC 7.0.3) - el código anterior no se compilará en GHC debido a este error - que estaba probando en GHCi hasta ahora:

$ 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' 

Por lo tanto, parece que tengo que recurrir a FFI (paquete cereal/data-binary-ieee754) hasta que se solucione este error, o hasta que encuentre una solución alternativa. Parece relacionado con GHC Ticket 4092. Corrígeme si se trata de un nuevo error o de un error diferente. Por ahora, no puedo compilarlo :(

Edit2: Actualización del código para utilizar unsafeCoerce corrige el problema de la compilación de código a continuación con el Criterio de referencia:.

{-# 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 
      ] 
     ] 

Criterio de salida (truncada):

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 

en un análisis más detallado, la mayor parte del cuello de botella parece estar en unpack64. la coacción toma ~ 6ns. unpack64 toma ~ 195ns. Desembalaje del word64 como una lista de word8 es bastante caro aquí.

Answer 1

Tenga en cuenta que el uso de unsafeCoerce# es peligroso aquí, los documentos dicen

casting un tipo sacó de la caja a otro tipo sacó de la caja del mismo tamaño (pero no coacciones entre en coma flotante e integrales tipos)

En cuanto a la velocidad, puede ser más rápido evitar la lista intermedia y escribir directamente en la memoria a través de unsafeCreate desde Data.ByteString.Internal.

Answer 2

Recientemente agregué soporte para flotadores IEEE-754 a cereal, y usted puede encontrar funciones similares para binary en data-binary-ieee754.Aquí hay un ejemplo usando la versión cereal de ida y vuelta a un piByteString y Fondo:

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

Se utiliza un truco con ST arrays para hacer la conversión rápida; ver this earlier question para más detalles.

actualización: D'oh, debe saber cómo utilizar las llamadas que contribuyó a la biblioteca ...

actualización x2: En cuanto a la falta de compilación, no creo que esto califica como una error.

No he examinado con demasiada atención el ensamblaje generado para este código en particular, pero los operandos a una instrucción movsd se están ensuciando. De §11.4.1.1 del Intel x86 manual:

El MOVSD (mover escalar doble precisión de punto flotante) transfiere una de 64 bits de doble precisión en coma flotante operando de la memoria a la baja palabra cuádruple de un registro XMM o viceversa, o entre registros XMM.

En el código no optimizado, usted tiene instrucciones finos como movsd LnTH(%rip),%xmm0, pero en el código -O, ves cosas como movsd Ln2cJ(%rip),%rax, donde %rax es un registro de propósito general, más que un registro XMM.

Es probable que el optimizador haga suposiciones sobre las representaciones de datos que necesita para moverse entre los registros en función del tipo de datos involucrados. unsafeCoerce y sus amigos invalidan esas suposiciones, por lo que cuando el selector de instrucciones crea que está eligiendo la operación correcta para un D#, en realidad está emitiendo un código que intenta rellenar ese D# donde encajaría felizmente un W64#.

Como manejar esto requeriría que el optimizador abandone muchas de las suposiciones que le permiten emitir mejor código en circunstancias normales, me inclino a decir que esto no es un error sino una buena historia de por qué las funciones unsafe tienen una advertencia advertencia del emptor

Answer 3

Siguiendo la sugerencia de acfoltzer (código fuente de cereales), y Daniel Fischer (unsafeCreate), que escribió el código de abajo que funciona bien para mi caso de uso, y es rápido también:

{-#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 
      ] 
     ] 

salida Criterio (truncado):

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 

De ~ 220ns a ~ 19ns, ¡agradable! No hice nada elegante en la compilación. Solo la opción -O lo hará en GHC7 (Mac, x86_64).

¡Ahora, tratando de descubrir cómo hacerlo rápido con la lista de dobles!