Bật hiệu quả ByteString thành một biểu diễn hex

Question

Tôi cần có khả năng trình bày hex của hàm băm SHA512. Có lẽ tôi đã không nhìn đủ cứng, nhưng tôi có thể tìm thấy bất kỳ chức năng nào trên Hackage để làm điều đó. Vì vậy, tôi đã viết một triển khai sử dụng unfoldrN. Nó chắc chắn đủ nhanh cho mục đích của tôi, nhưng tôi tự hỏi liệu có ai biết cách tiếp cận nhanh hơn không.

Tôi đã thực hiện triển khai trên Github dưới dạng gist: https://gist.github.com/2356925. Tệp cũng bao gồm triển khai đơn giản dựa trên Numeric.showHex, kiểm tra QuickCheck và điểm chuẩn tiêu chí. Các kết quả hiện tại của tôi về phiên bản đơn giản so với phiên bản unfoldrN là:

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 

Bất kỳ ai muốn tiến hành cải thiện nó?

Answer 1

Đi thấp cấp,

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) 

tôi có thể giảm thời gian chuyển đổi trên hộp của tôi bằng một yếu tố của khoảng 3,5. Làm sample lâu hơn một chút (25000), tôi đã

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 

Đối với bản gốc 500 dài sample, đó là

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

Dường như tôi chỉ sử dụng

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

lần cuối cùng tôi muốn làm điều đó. Điều này được kết hợp với thư viện Crypto.Hash iirc. Tôi nghi ngờ hiệu suất là tuyệt vời, nhưng so với (chậm) sha512 chức năng chính nó, tại sao chuyển đổi hex sẽ là một vấn đề?

Answer 3

Chức năng bạn đang tìm kiếm là Data.ByteString.Builder.byteStringHex (hoặc chức năng song sinh của nó cho Lazy ByteStrings), được cung cấp bởi trình tạo kết xuất mới. I extended your benchmarks và nhận các kết quả sau trên máy của tôi:

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 

Tôi thích số này. Quá xấu mà các bản vá của tôi cho thư viện lồng ghép vẫn đang được xem xét bởi Duncan Coutts. Tại phiên bản mới nhất, người xây dựng mới sẽ có sẵn với bản phát hành GHC tiếp theo.