Benchmark of various containers doing bit-level manipulation.

_README.markdown

I'm back with more bit-level benchmarks in Haskell. The goal here is to do some work on each bit in a large string of bytes. The time to beat is about 5 ms, which is how long Rust takes to do this. Unfortunately it looks like Haskell isn't quite up to the task:

Type	Time
ByteString	483.8 ms
Vector Bool (boxed)	315.9 ms
Vector Word8 (boxed)	500.3 ms
Vector Word16 (boxed)	511.6 ms
Vector Word32 (boxed)	520.6 ms
Vector Word64 (boxed)	490.3 ms
Vector Bool (unboxed)	297.0 ms
Vector Word8 (unboxed)	469.7 ms
Vector Word16 (unboxed)	487.8 ms
Vector Word32 (unboxed)	484.7 ms
Vector Word64 (unboxed)	502.2 ms

All the times are very close, so maybe I'm actually measuring the performance of something else. foldr? Adding Ints together? Something else? I'd love to know how to make this faster.

bits.hs

import qualified Data.Bits as Bit
import qualified Data.ByteString as B
import qualified Data.ByteString.Unsafe as B
import qualified Data.Vector as VB
import qualified Data.Vector.Generic as V
import qualified Data.Vector.Unboxed as VU
import qualified Data.Word as W
import qualified Gauge.Main as G
import qualified System.Random.MWC as R

main :: IO ()
main = do
  let size = 2097152 :: Int
  vb8 <- R.withSystemRandom (R.asGenST (\ generator ->
    R.uniformVector generator size))
  let
    vbb = mk_vbb vb8
    vb16 = mk_vb16 vb8
    vb32 = mk_vb32 vb8
    vb64 = mk_vb64 vb8
    vub = mk_vub vb8
    vu8 = mk_vu8 vb8
    vu16 = mk_vu16 vb8
    vu32 = mk_vu32 vb8
    vu64 = mk_vu64 vb8
    b = mk_b vb8

  print size
  G.defaultMain
    [ G.bench "ByteString" (G.nf f_b b)
    , G.bench "Vector Bool (boxed)" (G.nf f_vbb vbb)
    , G.bench "Vector Word8 (boxed)" (G.nf f_vb8 vb8)
    , G.bench "Vector Word16 (boxed)" (G.nf f_vb16 vb16)
    , G.bench "Vector Word32 (boxed)" (G.nf f_vb32 vb32)
    , G.bench "Vector Word64 (boxed)" (G.nf f_vb64 vb64)
    , G.bench "Vector Bool (unboxed)" (G.nf f_vub vub)
    , G.bench "Vector Word8 (unboxed)" (G.nf f_vu8 vu8)
    , G.bench "Vector Word16 (unboxed)" (G.nf f_vu16 vu16)
    , G.bench "Vector Word32 (unboxed)" (G.nf f_vu32 vu32)
    , G.bench "Vector Word64 (unboxed)" (G.nf f_vu64 vu64)
    ]

-- ByteString

mk_b :: VB.Vector W.Word8 -> B.ByteString
mk_b v = B.pack (V.toList v)

f_b :: B.ByteString -> Int
f_b b = foldr
  (\ i x -> if bit_b b i then x + 1 else x - 1)
  0
  [0 .. 8 * B.length b - 1]

bit_b :: B.ByteString -> Int -> Bool
bit_b b i = let
  (q, r) = quotRem i 8
  x = B.unsafeIndex b q
  in Bit.testBit x r

-- Vector Bool (boxed)

mk_vbb :: VB.Vector W.Word8 -> VB.Vector Bool
mk_vbb v = V.fromList (map (bit_vb8 v) [0 .. 8 * V.length v - 1])

f_vbb :: VB.Vector Bool -> Int
f_vbb v = foldr
  (\ i x -> if bit_vbb v i then x + 1 else x - 1)
  0
  [0 .. V.length v - 1]

bit_vbb :: VB.Vector Bool -> Int -> Bool
bit_vbb = V.unsafeIndex

-- Vector Bool (unboxed)

mk_vub :: VB.Vector W.Word8 -> VU.Vector Bool
mk_vub v = V.fromList (map (bit_vb8 v) [0 .. 8 * V.length v - 1])

f_vub :: VU.Vector Bool -> Int
f_vub v = foldr
  (\ i x -> if bit_vub v i then x + 1 else x - 1)
  0
  [0 .. V.length v - 1]

bit_vub :: VU.Vector Bool -> Int -> Bool
bit_vub = V.unsafeIndex

-- Vector Word8 (boxed)

f_vb8 :: VB.Vector W.Word8 -> Int
f_vb8 v = foldr
  (\ i x -> if bit_vb8 v i then x + 1 else x - 1)
  0
  [0 .. 8 * V.length v - 1]

bit_vb8 :: VB.Vector W.Word8 -> Int -> Bool
bit_vb8 v i = let
  (q, r) = quotRem i 8
  x = V.unsafeIndex v q
  in Bit.testBit x r

-- Vector Word8 (unboxed)

mk_vu8 :: VB.Vector W.Word8 -> VU.Vector W.Word8
mk_vu8 = V.convert

f_vu8 :: VU.Vector W.Word8 -> Int
f_vu8 v = foldr
  (\ i x -> if bit_vu8 v i then x + 1 else x - 1)
  0
  [0 .. 8 * V.length v - 1]

bit_vu8 :: VU.Vector W.Word8 -> Int -> Bool
bit_vu8 v i = let
  (q, r) = quotRem i 8
  x = V.unsafeIndex v q
  in Bit.testBit x r

-- Vector Word16 (boxed)

mk_vb16 :: VB.Vector W.Word8 -> VB.Vector W.Word16
mk_vb16 v = V.fromList (map
  (\ i -> let
    x = V.unsafeIndex v i
    y = V.unsafeIndex v (i + 1)
    in w8_16 y Bit..|. (Bit.unsafeShiftL (w8_16 x) 8))
  [0, 2 .. V.length v - 1])

f_vb16 :: VB.Vector W.Word16 -> Int
f_vb16 v = foldr
  (\ i x -> if bit_vb16 v i then x + 1 else x - 1)
  0
  [0 .. 16 * V.length v - 1]

bit_vb16 :: VB.Vector W.Word16 -> Int -> Bool
bit_vb16 v i = let
  (q, r) = quotRem i 16
  x = V.unsafeIndex v q
  in Bit.testBit x r

-- Vector Word16 (unboxed)

mk_vu16 :: VB.Vector W.Word8 -> VU.Vector W.Word16
mk_vu16 v = V.fromList (map
  (\ i -> let
    x = V.unsafeIndex v i
    y = V.unsafeIndex v (i + 1)
    in w8_16 y Bit..|. (Bit.unsafeShiftL (w8_16 x) 8))
  [0, 2 .. V.length v - 1])

f_vu16 :: VU.Vector W.Word16 -> Int
f_vu16 v = foldr
  (\ i x -> if bit_vu16 v i then x + 1 else x - 1)
  0
  [0 .. 16 * V.length v - 1]

bit_vu16 :: VU.Vector W.Word16 -> Int -> Bool
bit_vu16 v i = let
  (q, r) = quotRem i 16
  x = V.unsafeIndex v q
  in Bit.testBit x r

-- Vector Word32 (boxed)

mk_vb32 :: VB.Vector W.Word8 -> VB.Vector W.Word32
mk_vb32 v = V.fromList (map
  (\ i -> let
    a = V.unsafeIndex v i
    b = V.unsafeIndex v (i + 1)
    c = V.unsafeIndex v (i + 2)
    d = V.unsafeIndex v (i + 3)
    in w8_32 d
      Bit..|. (Bit.unsafeShiftL (w8_32 c) 8)
      Bit..|. (Bit.unsafeShiftL (w8_32 b) 16)
      Bit..|. (Bit.unsafeShiftL (w8_32 a) 24))
  [0, 4 .. V.length v - 1])

f_vb32 :: VB.Vector W.Word32 -> Int
f_vb32 v = foldr
  (\ i x -> if bit_vb32 v i then x + 1 else x - 1)
  0
  [0 .. 32 * V.length v - 1]

bit_vb32 :: VB.Vector W.Word32 -> Int -> Bool
bit_vb32 v i = let
  (q, r) = quotRem i 32
  x = V.unsafeIndex v q
  in Bit.testBit x r

-- Vector Word32 (unboxed)

mk_vu32 :: VB.Vector W.Word8 -> VU.Vector W.Word32
mk_vu32 v = V.fromList (map
  (\ i -> let
    a = V.unsafeIndex v i
    b = V.unsafeIndex v (i + 1)
    c = V.unsafeIndex v (i + 2)
    d = V.unsafeIndex v (i + 3)
    in w8_32 d
      Bit..|. (Bit.unsafeShiftL (w8_32 c) 8)
      Bit..|. (Bit.unsafeShiftL (w8_32 b) 16)
      Bit..|. (Bit.unsafeShiftL (w8_32 a) 24))
  [0, 4 .. V.length v - 1])

f_vu32 :: VU.Vector W.Word32 -> Int
f_vu32 v = foldr
  (\ i x -> if bit_vu32 v i then x + 1 else x - 1)
  0
  [0 .. 32 * V.length v - 1]

bit_vu32 :: VU.Vector W.Word32 -> Int -> Bool
bit_vu32 v i = let
  (q, r) = quotRem i 32
  x = V.unsafeIndex v q
  in Bit.testBit x r

-- Vector Word64 (boxed)

mk_vb64 :: VB.Vector W.Word8 -> VB.Vector W.Word64
mk_vb64 v = V.fromList (map
  (\ i -> let
    a = V.unsafeIndex v i
    b = V.unsafeIndex v (i + 1)
    c = V.unsafeIndex v (i + 2)
    d = V.unsafeIndex v (i + 3)
    e = V.unsafeIndex v (i + 4)
    f = V.unsafeIndex v (i + 5)
    g = V.unsafeIndex v (i + 6)
    h = V.unsafeIndex v (i + 7)
    in w8_64 h
      Bit..|. (Bit.unsafeShiftL (w8_64 g) 8)
      Bit..|. (Bit.unsafeShiftL (w8_64 f) 16)
      Bit..|. (Bit.unsafeShiftL (w8_64 e) 24)
      Bit..|. (Bit.unsafeShiftL (w8_64 d) 32)
      Bit..|. (Bit.unsafeShiftL (w8_64 c) 40)
      Bit..|. (Bit.unsafeShiftL (w8_64 b) 48)
      Bit..|. (Bit.unsafeShiftL (w8_64 a) 56))
  [0, 8 .. V.length v - 1])

f_vb64 :: VB.Vector W.Word64 -> Int
f_vb64 v = foldr
  (\ i x -> if bit_vb64 v i then x + 1 else x - 1)
  0
  [0 .. 64 * V.length v - 1]

bit_vb64 :: VB.Vector W.Word64 -> Int -> Bool
bit_vb64 v i = let
  (q, r) = quotRem i 64
  x = V.unsafeIndex v q
  in Bit.testBit x r

-- Vector Word64 (unboxed)

mk_vu64 :: VB.Vector W.Word8 -> VU.Vector W.Word64
mk_vu64 v = V.fromList (map
  (\ i -> let
    a = V.unsafeIndex v i
    b = V.unsafeIndex v (i + 1)
    c = V.unsafeIndex v (i + 2)
    d = V.unsafeIndex v (i + 3)
    e = V.unsafeIndex v (i + 4)
    f = V.unsafeIndex v (i + 5)
    g = V.unsafeIndex v (i + 6)
    h = V.unsafeIndex v (i + 7)
    in w8_64 h
      Bit..|. (Bit.unsafeShiftL (w8_64 g) 8)
      Bit..|. (Bit.unsafeShiftL (w8_64 f) 16)
      Bit..|. (Bit.unsafeShiftL (w8_64 e) 24)
      Bit..|. (Bit.unsafeShiftL (w8_64 d) 32)
      Bit..|. (Bit.unsafeShiftL (w8_64 c) 40)
      Bit..|. (Bit.unsafeShiftL (w8_64 b) 48)
      Bit..|. (Bit.unsafeShiftL (w8_64 a) 56))
  [0, 8 .. V.length v - 1])

f_vu64 :: VU.Vector W.Word64 -> Int
f_vu64 v = foldr
  (\ i x -> if bit_vu64 v i then x + 1 else x - 1)
  0
  [0 .. 64 * V.length v - 1]

bit_vu64 :: VU.Vector W.Word64 -> Int -> Bool
bit_vu64 v i = let
  (q, r) = quotRem i 64
  x = V.unsafeIndex v q
  in Bit.testBit x r

-- misc

w8_16 :: W.Word8 -> W.Word16
w8_16 = fromIntegral

w8_32 :: W.Word8 -> W.Word32
w8_32 = fromIntegral

w8_64 :: W.Word8 -> W.Word64
w8_64 = fromIntegral

package.yaml

name: bits
version: 0.0.0

executable:
  dependencies:
    - base
    - bytestring
    - gauge
    - mwc-random
    - vector
  ghc-options:
    - -O2
    - -rtsopts
    - -threaded
    - -Weverything
    - -Wno-implicit-prelude
    - -Wno-unsafe
  main: bits.hs

results.txt

8
ByteString                               mean 593.7 ns  ( +- 18.80 ns  )
Vector Bool (boxed)                      mean 173.3 ns  ( +- 6.742 ns  )
Vector Word8 (boxed)                     mean 703.7 ns  ( +- 29.02 ns  )
Vector Word16 (boxed)                    mean 720.0 ns  ( +- 29.71 ns  )
Vector Word32 (boxed)                    mean 696.9 ns  ( +- 23.08 ns  )
Vector Word64 (boxed)                    mean 672.9 ns  ( +- 9.588 ns  )
Vector Bool (unboxed)                    mean 101.5 ns  ( +- 2.361 ns  )
Vector Word8 (unboxed)                   mean 597.5 ns  ( +- 41.54 ns  )
Vector Word16 (unboxed)                  mean 611.0 ns  ( +- 20.95 ns  )
Vector Word32 (unboxed)                  mean 618.4 ns  ( +- 25.05 ns  )
Vector Word64 (unboxed)                  mean 607.2 ns  ( +- 17.06 ns  )

64
ByteString                               mean 5.395 μs  ( +- 260.3 ns  )
Vector Bool (boxed)                      mean 1.472 μs  ( +- 118.9 ns  )
Vector Word8 (boxed)                     mean 5.669 μs  ( +- 174.9 ns  )
Vector Word16 (boxed)                    mean 5.646 μs  ( +- 194.2 ns  )
Vector Word32 (boxed)                    mean 5.567 μs  ( +- 134.5 ns  )
Vector Word64 (boxed)                    mean 5.509 μs  ( +- 190.3 ns  )
Vector Bool (unboxed)                    mean 975.2 ns  ( +- 33.55 ns  )
Vector Word8 (unboxed)                   mean 4.926 μs  ( +- 319.9 ns  )
Vector Word16 (unboxed)                  mean 5.055 μs  ( +- 110.1 ns  )
Vector Word32 (unboxed)                  mean 5.073 μs  ( +- 249.0 ns  )
Vector Word64 (unboxed)                  mean 5.295 μs  ( +- 514.2 ns  )

512
ByteString                               mean 79.80 μs  ( +- 2.367 μs  )
Vector Bool (boxed)                      mean 47.56 μs  ( +- 1.680 μs  )
Vector Word8 (boxed)                     mean 87.20 μs  ( +- 3.260 μs  )
Vector Word16 (boxed)                    mean 86.89 μs  ( +- 2.512 μs  )
Vector Word32 (boxed)                    mean 87.39 μs  ( +- 6.157 μs  )
Vector Word64 (boxed)                    mean 85.27 μs  ( +- 2.953 μs  )
Vector Bool (unboxed)                    mean 44.06 μs  ( +- 1.840 μs  )
Vector Word8 (unboxed)                   mean 77.85 μs  ( +- 2.047 μs  )
Vector Word16 (unboxed)                  mean 83.16 μs  ( +- 1.270 μs  )
Vector Word32 (unboxed)                  mean 82.79 μs  ( +- 2.175 μs  )
Vector Word64 (unboxed)                  mean 82.62 μs  ( +- 4.109 μs  )

4096
ByteString                               mean 739.3 μs  ( +- 18.79 μs  )
Vector Bool (boxed)                      mean 434.7 μs  ( +- 19.44 μs  )
Vector Word8 (boxed)                     mean 779.8 μs  ( +- 12.91 μs  )
Vector Word16 (boxed)                    mean 808.6 μs  ( +- 55.99 μs  )
Vector Word32 (boxed)                    mean 786.7 μs  ( +- 34.97 μs  )
Vector Word64 (boxed)                    mean 774.5 μs  ( +- 16.00 μs  )
Vector Bool (unboxed)                    mean 400.4 μs  ( +- 6.289 μs  )
Vector Word8 (unboxed)                   mean 729.8 μs  ( +- 14.55 μs  )
Vector Word16 (unboxed)                  mean 779.2 μs  ( +- 37.24 μs  )
Vector Word32 (unboxed)                  mean 757.7 μs  ( +- 12.68 μs  )
Vector Word64 (unboxed)                  mean 768.2 μs  ( +- 30.28 μs  )

32768
ByteString                               mean 6.657 ms  ( +- 269.0 μs  )
Vector Bool (boxed)                      mean 4.091 ms  ( +- 90.98 μs  )
Vector Word8 (boxed)                     mean 6.972 ms  ( +- 182.6 μs  )
Vector Word16 (boxed)                    mean 6.983 ms  ( +- 161.4 μs  )
Vector Word32 (boxed)                    mean 6.884 ms  ( +- 170.6 μs  )
Vector Word64 (boxed)                    mean 6.866 ms  ( +- 134.5 μs  )
Vector Bool (unboxed)                    mean 3.818 ms  ( +- 76.13 μs  )
Vector Word8 (unboxed)                   mean 6.545 ms  ( +- 177.4 μs  )
Vector Word16 (unboxed)                  mean 6.796 ms  ( +- 240.8 μs  )
Vector Word32 (unboxed)                  mean 6.736 ms  ( +- 168.4 μs  )
Vector Word64 (unboxed)                  mean 7.119 ms  ( +- 926.2 μs  )

262144
ByteString                               mean 58.28 ms  ( +- 1.492 ms  )
Vector Bool (boxed)                      mean 39.50 ms  ( +- 1.316 ms  )
Vector Word8 (boxed)                     mean 62.59 ms  ( +- 3.733 ms  )
Vector Word16 (boxed)                    mean 63.12 ms  ( +- 6.919 ms  )
Vector Word32 (boxed)                    mean 60.47 ms  ( +- 987.1 μs  )
Vector Word64 (boxed)                    mean 61.92 ms  ( +- 3.117 ms  )
Vector Bool (unboxed)                    mean 35.50 ms  ( +- 417.9 μs  )
Vector Word8 (unboxed)                   mean 57.29 ms  ( +- 704.9 μs  )
Vector Word16 (unboxed)                  mean 59.56 ms  ( +- 1.419 ms  )
Vector Word32 (unboxed)                  mean 61.06 ms  ( +- 3.791 ms  )
Vector Word64 (unboxed)                  mean 59.85 ms  ( +- 942.6 μs  )

2097152
ByteString                               mean 483.8 ms  ( +- 7.787 ms  )
Vector Bool (boxed)                      mean 315.9 ms  ( +- 10.22 ms  )
Vector Word8 (boxed)                     mean 500.3 ms  ( +- 3.416 ms  )
Vector Word16 (boxed)                    mean 511.6 ms  ( +- 23.61 ms  )
Vector Word32 (boxed)                    mean 520.6 ms  ( +- 25.86 ms  )
Vector Word64 (boxed)                    mean 490.3 ms  ( +- 10.89 ms  )
Vector Bool (unboxed)                    mean 297.0 ms  ( +- 3.970 ms  )
Vector Word8 (unboxed)                   mean 469.7 ms  ( +- 4.784 ms  )
Vector Word16 (unboxed)                  mean 487.8 ms  ( +- 7.937 ms  )
Vector Word32 (unboxed)                  mean 484.7 ms  ( +- 3.877 ms  )
Vector Word64 (unboxed)                  mean 502.2 ms  ( +- 24.46 ms  )

stack.yaml

resolver: lts-10.0