Trasformare efficientemente un ByteString in una rappresentazione esadecimale

Question

Avevo bisogno di essere in grado di fornire la rappresentazione esadecimale di un hash SHA512. Forse non sono stato abbastanza duro, ma ho trovato alcune funzioni su Hackage per farlo. Così ho scritto un'implementazione usando unfoldrN. È decisamente abbastanza veloce per i miei scopi, ma mi chiedo se qualcuno sa di un approccio più veloce.

Ho messo la mia implementazione su Github come un esempio: https://gist.github.com/2356925. Il file include anche un'implementazione semplice basata su Numeric.showHex, un test QuickCheck e un benchmark di criterio. I miei attuali risultati della versione semplice rispetto alla versione unfoldrN sono:

benchmarking simple 
mean: 4.677296 ms, lb 4.656011 ms, ub 4.696684 ms, ci 0.950 
std dev: 104.2791 us, lb 87.77023 us, ub 128.1627 us, ci 0.950 
found 5 outliers among 100 samples (5.0%) 
    4 (4.0%) low mild 
variance introduced by outliers: 15.195% 
variance is moderately inflated by outliers 

benchmarking unfoldrN_MS1 
mean: 370.0101 us, lb 365.9819 us, ub 373.8619 us, ci 0.950 
std dev: 20.17016 us, lb 16.92772 us, ub 24.08982 us, ci 0.950 
found 14 outliers among 100 samples (14.0%) 
    7 (7.0%) low mild 
    7 (7.0%) high mild 
variance introduced by outliers: 52.467% 
variance is severely inflated by outliers 

Chiunque vuole prendere una pugnalata a migliorarlo?

Answer 1

Andando di livello inferiore,

import Data.ByteString.Internal 
import Foreign.Ptr 
import Foreign.Storable 
import qualified Data.ByteString as B 
import Data.ByteString.Unsafe 
import Data.Bits 
import Data.Word 

maxLen :: Int 
maxLen = maxBound `quot` 2 

hexDig :: Word8 -> Word8 
hexDig d 
    | d < 10 = d + 48 
    | otherwise = d + 87 

toHex :: ByteString -> ByteString 
toHex bs 
    | len > maxLen = error "too long to convert" 
    | otherwise = unsafeCreate nl (go 0) 
     where 
     len = B.length bs 
     nl = 2*len 
     go i p 
      | i == len = return() 
      | otherwise = case unsafeIndex bs i of 
          w -> do poke p (hexDig $ w `shiftR` 4) 
            poke (p `plusPtr` 1) (hexDig $ w .&. 0xF) 
            go (i+1) (p `plusPtr` 2) 

ho potuto ridurre il tempo di conversione sulla mia macchina da un altro fattore di circa 3,5. Fare sample un po 'di più (25000), ho avuto

benchmarking simple 
mean: 13.76532 ms, lb 13.64184 ms, ub 13.88680 ms, ci 0.950 
std dev: 633.2413 us, lb 582.6342 us, ub 687.9701 us, ci 0.950 
variance introduced by outliers: 44.438% 
variance is moderately inflated by outliers 

benchmarking unfoldrN_MS1 
mean: 430.5705 us, lb 424.9206 us, ub 438.5689 us, ci 0.950 
std dev: 33.85429 us, lb 26.25623 us, ub 45.74915 us, ci 0.950 
found 4 outliers among 100 samples (4.0%) 
    3 (3.0%) high mild 
    1 (1.0%) high severe 
variance introduced by outliers: 69.726% 
variance is severely inflated by outliers 

benchmarking LowHex 
mean: 123.6000 us, lb 123.0551 us, ub 124.7084 us, ci 0.950 
std dev: 3.837497 us, lb 1.869370 us, ub 6.470112 us, ci 0.950 
found 6 outliers among 100 samples (6.0%) 
    4 (4.0%) high mild 
    2 (2.0%) high severe 
variance introduced by outliers: 25.818% 
variance is moderately inflated by outliers 

per l'originale 500 lungo sample, era

benchmarking simple 
mean: 2.603306 ms, lb 2.583054 ms, ub 2.629212 ms, ci 0.950 
std dev: 116.5341 us, lb 81.61409 us, ub 191.3293 us, ci 0.950 
found 7 outliers among 100 samples (7.0%) 
    2 (2.0%) low severe 
    3 (3.0%) low mild 
    1 (1.0%) high severe 
variance introduced by outliers: 42.490% 
variance is moderately inflated by outliers 

benchmarking unfoldrN_MS1 
mean: 83.19349 us, lb 82.88474 us, ub 83.58283 us, ci 0.950 
std dev: 1.771460 us, lb 1.486104 us, ub 2.174729 us, ci 0.950 
found 14 outliers among 100 samples (14.0%) 
    12 (12.0%) high mild 
    2 (2.0%) high severe 
variance introduced by outliers: 14.225% 
variance is moderately inflated by outliers 

benchmarking LowHex 
mean: 24.50564 us, lb 24.41683 us, ub 24.61241 us, ci 0.950 
std dev: 497.1908 ns, lb 415.6366 ns, ub 609.7594 ns, ci 0.950 
found 5 outliers among 100 samples (5.0%) 
    5 (5.0%) high mild 
variance introduced by outliers: 13.256% 
variance is moderately inflated by outliers 

Answer 2

sembra che ho appena usato

hex :: B.ByteString -> String 
hex = concatMap (printf "%02x") . B.unpack 

ultima volta che ho volevo farlo Questo era in combinazione con la libreria Crypto.Hash iirc. Dubito che le prestazioni siano grandiose, ma rispetto alla (lenta) funzione sha512 stessa, perché la conversione esadecimale sarebbe un problema?

Answer 3

La funzione che stai cercando è Data.ByteString.Builder.byteStringHex (o la sua funzione gemella per Lazy ByteStrings), fornita dal nuovo generatore bytestring. I extended your benchmarks e ottenere i seguenti risultati sulla mia macchina:

benchmarking size 5000/simple 
mean: 2.469847 ms, lb 2.440422 ms, ub 2.522850 ms, ci 0.950 
std dev: 196.5903 us, lb 116.8811 us, ub 318.4720 us, ci 0.950 
found 16 outliers among 100 samples (16.0%) 
    3 (3.0%) low severe 
    2 (2.0%) low mild 
    10 (10.0%) high severe 
variance introduced by outliers: 70.721% 
variance is severely inflated by outliers 

benchmarking size 5000/unfoldrN_MS1 
mean: 102.6075 us, lb 101.7695 us, ub 104.0159 us, ci 0.950 
std dev: 5.468574 us, lb 3.681120 us, ub 8.080665 us, ci 0.950 
found 16 outliers among 100 samples (16.0%) 
    6 (6.0%) high mild 
    10 (10.0%) high severe 
variance introduced by outliers: 51.455% 
variance is severely inflated by outliers 

benchmarking size 5000/byteStringHexFixed 
mean: 5.675204 us, lb 5.636296 us, ub 5.750211 us, ci 0.950 
std dev: 264.3726 ns, lb 140.9738 ns, ub 398.8494 ns, ci 0.950 
found 5 outliers among 100 samples (5.0%) 
    4 (4.0%) high severe 
variance introduced by outliers: 44.476% 
variance is moderately inflated by outliers 

mi piace questo numero. Peccato che le mie patch alla libreria bytestring siano ancora sotto esame da Duncan Coutts. Al più tardi il nuovo builder di bytestring sarà disponibile con la prossima versione di GHC.