__results.md

Type	Time (ns)
[Bool]	65060000
[Word8]	12520000
Vector Word8	186800
U.Vector Word8	183200
ByteString	176300
Vector Bool	92630
U.Vector Bool	86580

_results.txt

benchmarked bit list
time                 65.06 ms   (63.82 ms .. 66.62 ms)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 66.51 ms   (65.21 ms .. 70.87 ms)
std dev              3.971 ms   (663.7 μs .. 7.086 ms)
variance introduced by outliers: 16% (moderately inflated)

benchmarked byte list
time                 12.52 ms   (12.30 ms .. 12.72 ms)
                     0.998 R²   (0.996 R² .. 0.999 R²)
mean                 12.74 ms   (12.61 ms .. 12.89 ms)
std dev              360.7 μs   (276.2 μs .. 491.9 μs)

benchmarked byte vector
time                 186.8 μs   (184.7 μs .. 189.4 μs)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 184.1 μs   (182.7 μs .. 185.7 μs)
std dev              5.011 μs   (4.370 μs .. 5.846 μs)
variance introduced by outliers: 11% (moderately inflated)

benchmarked unboxed byte vector
time                 183.2 μs   (180.3 μs .. 186.8 μs)
                     0.998 R²   (0.997 R² .. 0.999 R²)
mean                 181.7 μs   (180.4 μs .. 183.4 μs)
std dev              5.285 μs   (4.285 μs .. 7.330 μs)
variance introduced by outliers: 13% (moderately inflated)

benchmarked byte string
time                 176.3 μs   (173.4 μs .. 180.0 μs)
                     0.997 R²   (0.995 R² .. 0.998 R²)
mean                 174.3 μs   (172.4 μs .. 176.3 μs)
std dev              6.527 μs   (5.658 μs .. 8.033 μs)
variance introduced by outliers: 20% (moderately inflated)

benchmarked bit vector
time                 92.63 μs   (90.48 μs .. 94.54 μs)
                     0.997 R²   (0.995 R² .. 0.998 R²)
mean                 93.13 μs   (92.16 μs .. 94.57 μs)
std dev              3.840 μs   (3.013 μs .. 5.277 μs)
variance introduced by outliers: 20% (moderately inflated)

benchmarked unboxed bit vector
time                 86.58 μs   (85.54 μs .. 87.51 μs)
                     0.999 R²   (0.997 R² .. 0.999 R²)
mean                 86.93 μs   (86.32 μs .. 87.88 μs)
std dev              2.626 μs   (2.070 μs .. 3.387 μs)
variance introduced by outliers: 13% (moderately inflated)

_results_mem.txt

these quick numbers were generated with:
  ./bits-bench +RTS -s -RTS -q -m prefix '...'
the program generated 1,000 random bytes in each case

bit list
1,463,528 bytes allocated in the heap
  984,032 bytes copied during GC
  280,296 bytes maximum residency (6 sample(s))
   43,664 bytes maximum slop
        2 MB total memory in use (0 MB lost due to fragmentation)

byte list
2,123,960 bytes allocated in the heap
1,937,560 bytes copied during GC
  312,216 bytes maximum residency (10 sample(s))
   44,232 bytes maximum slop
        2 MB total memory in use (0 MB lost due to fragmentation)

byte vector
360,449,504 bytes allocated in the heap
 29,456,304 bytes copied during GC
    316,296 bytes maximum residency (124 sample(s))
     50,624 bytes maximum slop
          2 MB total memory in use (0 MB lost due to fragmentation)

unboxed byte vector
379,928,128 bytes allocated in the heap
 30,094,928 bytes copied during GC
    309,552 bytes maximum residency (126 sample(s))
     48,816 bytes maximum slop
          2 MB total memory in use (0 MB lost due to fragmentation)

byte string
379,918,984 bytes allocated in the heap
 24,945,936 bytes copied during GC
    271,864 bytes maximum residency (126 sample(s))
     27,576 bytes maximum slop
          2 MB total memory in use (0 MB lost due to fragmentation)

bit vector
780,565,888 bytes allocated in the heap
  1,443,704 bytes copied during GC
    142,432 bytes maximum residency (154 sample(s))
     30,752 bytes maximum slop
          2 MB total memory in use (0 MB lost due to fragmentation)

unboxed bit vector
863,578,504 bytes allocated in the heap
  1,529,808 bytes copied during GC
     85,192 bytes maximum residency (158 sample(s))
     27,872 bytes maximum slop
          2 MB total memory in use (0 MB lost due to fragmentation)

bits-bench.hs

-- stack --resolver nightly-2018-01-09 script --compile
{-# OPTIONS_GHC -O2 -Weverything -Wno-implicit-prelude -Wno-unsafe #-}

module Main
  ( main
  ) where

import qualified Data.Bits as Bits
import qualified Data.ByteString as ByteString
import qualified Data.List as List
import qualified Data.Vector as Vector
import qualified Data.Vector.Unboxed as Vector.Unboxed
import qualified Data.Word as Word
import qualified Gauge
import qualified System.Random.MWC as Random

main :: IO ()
main = do
  generator <- Random.createSystemRandom
  byte_vector <- Random.uniformVector generator 1000
  let
    _ = byte_vector :: Vector.Vector Word.Word8
    unboxed_byte_vector = Vector.convert byte_vector :: Vector.Unboxed.Vector Word.Word8
    byte_list = Vector.toList byte_vector :: [Word.Word8]
    bit_list = concatMap (\ x -> map (Bits.testBit x) [0 .. 7]) byte_list :: [Bool]
    bit_vector = Vector.fromList bit_list :: Vector.Vector Bool
    unboxed_bit_vector = Vector.convert bit_vector :: Vector.Unboxed.Vector Bool
    byte_string = ByteString.pack byte_list :: ByteString.ByteString
    expected = List.foldl'
      (\ x index -> if bit_list !! index then x + 1 else x - 1)
      0
      [0 .. length bit_list - 1]
  Gauge.defaultMain
    -- 65.06 ms = 65060000 ns
    [ Gauge.bench "bit list" (Gauge.nf (test expected (\ x -> div (length x) 8) f5) bit_list)
    -- 12.52 ms = 12520000 ns
    , Gauge.bench "byte list" (Gauge.nf (test expected length f1) byte_list)
    -- 186.8 μs = 186800 ns
    , Gauge.bench "byte vector" (Gauge.nf (test expected Vector.length f2) byte_vector)
    -- 183.2 μs = 183200 ns
    , Gauge.bench "unboxed byte vector" (Gauge.nf (test expected Vector.Unboxed.length f3) unboxed_byte_vector)
    -- 176.3 μs = 176300 ns
    , Gauge.bench "byte string" (Gauge.nf (test expected ByteString.length f4) byte_string)
    -- 92.63 μs = 92630 ns
    , Gauge.bench "bit vector" (Gauge.nf (test expected (\ x -> div (Vector.length x) 8) f6) bit_vector)
    -- 86.58 μs = 86580 ns
    , Gauge.bench "unboxed bit vector" (Gauge.nf (test expected (\ x -> div (Vector.Unboxed.length x) 8) f7) unboxed_bit_vector)
    ]

test :: Int -> (a -> Int) -> (Int -> a -> Bool) -> a -> Int
test expected getLength getBit bytes =
  let
    actual = List.foldl'
      (\ x index -> if getBit index bytes then x + 1 else x - 1)
      0
      [0 .. 8 * getLength bytes - 1]
  in
    if expected == actual
      then actual
      else error (show (expected, actual))

f1 :: Int -> [Word.Word8] -> Bool
f1 i x = let (q, r) = quotRem i 8 in Bits.testBit (x !! q) r

f5 :: Int -> [Bool] -> Bool
f5 i x = x !! i

f2 :: Int -> Vector.Vector Word.Word8 -> Bool
f2 i x = let (q, r) = quotRem i 8 in Bits.testBit (x Vector.! q) r

f6 :: Int -> Vector.Vector Bool -> Bool
f6 i x = x Vector.! i

f3 :: Int -> Vector.Unboxed.Vector Word.Word8 -> Bool
f3 i x = let (q, r) = quotRem i 8 in Bits.testBit (x Vector.Unboxed.! q) r

f7 :: Int -> Vector.Unboxed.Vector Bool -> Bool
f7 i x = x Vector.Unboxed.! i

f4 :: Int -> ByteString.ByteString -> Bool
f4 i x = let (q, r) = quotRem i 8 in Bits.testBit (ByteString.index x q) r