bitvec 1.1.3.0 → 1.1.4.0
raw patch · 23 files changed
+142/−199 lines, 23 filesdep ~basedep ~bytestringdep ~containersPVP ok
version bump matches the API change (PVP)
Dependency ranges changed: base, bytestring, containers, deepseq, integer-gmp, primitive, quickcheck-classes, quickcheck-classes-base, random, tasty, tasty-bench, tasty-quickcheck
API changes (from Hackage documentation)
Files
- README.md +2/−2
- bench/Bench.hs +16/−4
- bench/Bench/BitIndex.hs +3/−19
- bench/Bench/GCD.hs +2/−2
- bench/Bench/Intersection.hs +4/−12
- bench/Bench/Invert.hs +3/−11
- bench/Bench/Product.hs +19/−9
- bench/Bench/RandomFlip.hs +4/−24
- bench/Bench/RandomRead.hs +1/−1
- bench/Bench/RandomWrite.hs +1/−1
- bench/Bench/Remainder.hs +3/−3
- bench/Bench/Reverse.hs +3/−11
- bench/Bench/Sum.hs +12/−7
- bench/Bench/Union.hs +4/−12
- bitvec.cabal +20/−18
- changelog.md +5/−0
- src/Data/Bit.hs +8/−2
- src/Data/Bit/Immutable.hs +14/−13
- src/Data/Bit/Internal.hs +4/−2
- src/Data/Bit/Mutable.hs +8/−8
- src/Data/Bit/PdepPext.hs +0/−32
- src/Data/Bit/Utils.hs +3/−3
- test/Tests/Vector.hs +3/−3
README.md view
@@ -20,7 +20,7 @@ This is because naive updates are not atomic: they read the whole word from memory, then modify a bit, then write the whole word back.-* `Data.Bit.ThreadSafe` is slower (up to 20%),+* `Data.Bit.ThreadSafe` is slower (usually 10-20%), but writes and flips are thread-safe. ## Quick start@@ -105,7 +105,7 @@ does not matter and get tempted to run it in several parallel threads. In this case it is vital to switch from `Data.Bit` to `Data.Bit.ThreadSafe`, because the former is thread-unsafe with regards to writes.-There is a moderate performance penalty (up to 20%)+There is a moderate performance penalty (usually 10-20%) for using the thread-safe interface. ## Sets
bench/Bench.hs view
@@ -1,6 +1,7 @@ module Main where import Test.Tasty.Bench+import Test.Tasty.Patterns.Printer import Bench.BitIndex import Bench.GCD@@ -16,17 +17,28 @@ import Bench.Union main :: IO ()-main = defaultMain+main = defaultMain $ map (mapLeafBenchmarks addCompare) [ bgroup "bitIndex" $ map benchBitIndex [5..14] , bgroup "invert" $ map benchInvert [5..14] , bgroup "gcdExt" $ map benchGCD [5..14] , bgroup "intersection" $ map benchIntersection [5..14] , bgroup "product" $ map benchProduct [5..14]- , bgroup "randomWrite" $ map benchRandomWrite [5..14]- , bgroup "randomFlip" $ map benchRandomFlip [5..14]- , bgroup "randomRead" $ map benchRandomRead [5..14]+ , bgroup "productShort" $ map benchProductShort [5..14]+ , bgroup "square" $ map benchSquare [5..14]+ , bgroup "write" $ map benchRandomWrite [5..14]+ , bgroup "flip" $ map benchRandomFlip [5..14]+ , bgroup "read" $ map benchRandomRead [5..14] , bgroup "remainder" $ map benchRemainder [5..14] , bgroup "reverse" $ map benchReverse [5..14]+ , bgroup "add" $ map benchAdd [5..14] , bgroup "sum" $ map benchSum [5..14] , bgroup "union" $ map benchUnion [5..14] ]++bitBenchName :: String+bitBenchName = "Bit"++addCompare :: ([String] -> Benchmark -> Benchmark)+addCompare (name : path)+ | name /= bitBenchName = bcompare (printAwkExpr (locateBenchmark (bitBenchName : path)))+addCompare _ = id
bench/Bench/BitIndex.hs view
@@ -16,32 +16,16 @@ benchBitIndex :: Int -> Benchmark benchBitIndex k = bgroup (show (1 `shiftL` k :: Int))- [ bench "Bit/bitIndex" $ nf bitIndexBit (randomVec Bit k)- , bench "Bit/nthBitIndex" $ nf nthBitIndexBit (randomVec Bit k)- , bench "Bit/elemIndex" $ nf elemIndexBit (randomVec Bit k)- , bench "Bit.TS/bitIndex" $ nf bitIndexBitTS (randomVec TS.Bit k)- , bench "Bit.TS/nthBitIndex" $ nf nthBitIndexBitTS (randomVec TS.Bit k)- , bench "Bit.TS/elemIndex" $ nf elemIndexBitTS (randomVec TS.Bit k)- , bench "Vector" $ nf elemIndexVector (randomVec id k)+ [ bench "Bit" $ nf bitIndexBit (randomVec Bit k)+ , bench "BitTS" $ nf bitIndexBitTS (randomVec TS.Bit k)+ , bench "Vector" $ nf elemIndexVector (randomVec id k) ] bitIndexBit :: U.Vector Bit -> Maybe Int bitIndexBit = bitIndex (Bit True) -nthBitIndexBit :: U.Vector Bit -> Maybe Int-nthBitIndexBit = nthBitIndex (Bit True) 1--elemIndexBit :: U.Vector Bit -> Maybe Int-elemIndexBit = U.elemIndex (Bit True)- bitIndexBitTS :: U.Vector TS.Bit -> Maybe Int bitIndexBitTS = TS.bitIndex (TS.Bit True)--nthBitIndexBitTS :: U.Vector TS.Bit -> Maybe Int-nthBitIndexBitTS = TS.nthBitIndex (TS.Bit True) 1--elemIndexBitTS :: U.Vector TS.Bit -> Maybe Int-elemIndexBitTS = U.elemIndex (TS.Bit True) elemIndexVector :: U.Vector Bool -> Maybe Int elemIndexVector = U.elemIndex True
bench/Bench/GCD.hs view
@@ -25,6 +25,6 @@ benchGCD :: Int -> Benchmark benchGCD k = bgroup (show (1 `shiftL` k :: Int))- [ bench "Bit/gcdExt" $ nf (uncurry gcdExt) ( toF2Poly $ randomVec Bit k, toF2Poly $ randomVec' Bit k)- , bench "Bit.TS/gcdExt" $ nf (uncurry TS.gcdExt) (TS.toF2Poly $ randomVec TS.Bit k, TS.toF2Poly $ randomVec' TS.Bit k)+ [ bench "Bit" $ nf (uncurry gcdExt) ( toF2Poly $ randomVec Bit k, toF2Poly $ randomVec' Bit k)+ , bench "BitTS" $ nf (uncurry TS.gcdExt) (TS.toF2Poly $ randomVec TS.Bit k, TS.toF2Poly $ randomVec' TS.Bit k) ]
bench/Bench/Intersection.hs view
@@ -40,25 +40,17 @@ benchIntersection :: Int -> Benchmark benchIntersection k = bgroup (show (1 `shiftL` k :: Int))- [ bench "Bit/zipBits" $ nf (\x -> intersectionBit (randomVec Bit k) x) (randomVec2 Bit k)- , bench "Bit/zipWith" $ nf (\x -> intersectionBit' (randomVec Bit k) x) (randomVec2 Bit k)- , bench "Bit.TS/zipBits" $ nf (\x -> intersectionBitTS (randomVec TS.Bit k) x) (randomVec2 TS.Bit k)- , bench "Bit.TS/zipWith" $ nf (\x -> intersectionBitTS' (randomVec TS.Bit k) x) (randomVec2 TS.Bit k)- , bench "Vector" $ nf (\x -> intersectionVector (randomVec id k) x) (randomVec2 id k)- , bench "IntSet" $ nf (intersectionIntSet (randomSet k)) (randomSet2 k)+ [ bench "Bit" $ nf (\x -> intersectionBit (randomVec Bit k) x) (randomVec2 Bit k)+ , bench "BitTS" $ nf (\x -> intersectionBitTS (randomVec TS.Bit k) x) (randomVec2 TS.Bit k)+ , bench "Vector" $ nf (\x -> intersectionVector (randomVec id k) x) (randomVec2 id k)+ , bench "IntSet" $ nf (intersectionIntSet (randomSet k)) (randomSet2 k) ] intersectionBit :: U.Vector Bit -> U.Vector Bit -> U.Vector Bit intersectionBit = zipBits (.&.) -intersectionBit' :: U.Vector Bit -> U.Vector Bit -> U.Vector Bit-intersectionBit' = U.zipWith (\(Bit x) (Bit y) -> Bit (x && y))- intersectionBitTS :: U.Vector TS.Bit -> U.Vector TS.Bit -> U.Vector TS.Bit intersectionBitTS = TS.zipBits (.&.)--intersectionBitTS' :: U.Vector TS.Bit -> U.Vector TS.Bit -> U.Vector TS.Bit-intersectionBitTS' = U.zipWith (\(TS.Bit x) (TS.Bit y) -> TS.Bit (x && y)) intersectionVector :: U.Vector Bool -> U.Vector Bool -> U.Vector Bool intersectionVector = U.zipWith (&&)
bench/Bench/Invert.hs view
@@ -24,24 +24,16 @@ benchInvert :: Int -> Benchmark benchInvert k = bgroup (show (1 `shiftL` k :: Int))- [ bench "Bit/invertBits" $ nf invertBit (randomVec Bit k)- , bench "Bit/map-complement" $ nf invertBit' (randomVec Bit k)- , bench "Bit.TS/invertBits" $ nf invertBitTS (randomVec TS.Bit k)- , bench "Bit.TS/map-complement" $ nf invertBitTS' (randomVec TS.Bit k)- , bench "Vector" $ nf invertVector (randomVec id k)+ [ bench "Bit" $ nf invertBit (randomVec Bit k)+ , bench "BitTS" $ nf invertBitTS (randomVec TS.Bit k)+ , bench "Vector" $ nf invertVector (randomVec id k) ] invertBit :: U.Vector Bit -> U.Vector Bit invertBit = invertBits -invertBit' :: U.Vector Bit -> U.Vector Bit-invertBit' = U.map complement- invertBitTS :: U.Vector TS.Bit -> U.Vector TS.Bit invertBitTS = TS.invertBits--invertBitTS' :: U.Vector TS.Bit -> U.Vector TS.Bit-invertBitTS' = U.map complement invertVector :: U.Vector Bool -> U.Vector Bool invertVector = U.map not
bench/Bench/Product.hs view
@@ -1,5 +1,7 @@ module Bench.Product ( benchProduct+ , benchProductShort+ , benchSquare ) where import Data.Bit@@ -35,15 +37,23 @@ benchProduct :: Int -> Benchmark benchProduct k = bgroup (show (1 `shiftL` k :: Int))- [ bench "Bit/product" $ nf (\x -> (*) (toF2Poly $ randomVec Bit k) x) (toF2Poly $ randomVec2 Bit k)- , bench "Bit/productShort" $ nf (\x -> (*) (toF2Poly $ randomVec Bit k) x) (toF2Poly $ U.take 32 $ randomVec2 Bit k)- , bench "Bit/square" $ nf (\x -> (*) (toF2Poly $ randomVec Bit k) x) (toF2Poly $ randomVec Bit k)- , bench "Bit.TS/product" $ nf (\x -> (*) (TS.toF2Poly $ randomVec TS.Bit k) x) (TS.toF2Poly $ randomVec2 TS.Bit k)- , bench "Bit.TS/productShort" $ nf (\x -> (*) (TS.toF2Poly $ randomVec TS.Bit k) x) (TS.toF2Poly $ U.take 32 $ randomVec2 TS.Bit k)- , bench "Bit.TS/square" $ nf (\x -> (*) (TS.toF2Poly $ randomVec TS.Bit k) x) (TS.toF2Poly $ randomVec TS.Bit k)- , bench "Integer/product" $ nf (\x -> binMul (randomInteger k) x) (randomInteger2 k)- , bench "Integer/productShort" $ nf (\x -> binMul (randomInteger k) x) ((1 `shiftL` 32 - 1) .&. randomInteger2 k)- , bench "Integer/square" $ nf (\x -> binMul (randomInteger k) x) (randomInteger k)+ [ bench "Bit" $ nf (\x -> (*) (toF2Poly $ randomVec Bit k) x) (toF2Poly $ randomVec2 Bit k)+ , bench "BitTS" $ nf (\x -> (*) (TS.toF2Poly $ randomVec TS.Bit k) x) (TS.toF2Poly $ randomVec2 TS.Bit k)+ , bench "Integer" $ nf (\x -> binMul (randomInteger k) x) (randomInteger2 k)+ ]++benchProductShort :: Int -> Benchmark+benchProductShort k = bgroup (show (1 `shiftL` k :: Int))+ [ bench "Bit" $ nf (\x -> (*) (toF2Poly $ randomVec Bit k) x) (toF2Poly $ U.take 32 $ randomVec2 Bit k)+ , bench "BitTS" $ nf (\x -> (*) (TS.toF2Poly $ randomVec TS.Bit k) x) (TS.toF2Poly $ U.take 32 $ randomVec2 TS.Bit k)+ , bench "Integer" $ nf (\x -> binMul (randomInteger k) x) ((1 `shiftL` 32 - 1) .&. randomInteger2 k)+ ]++benchSquare :: Int -> Benchmark+benchSquare k = bgroup (show (1 `shiftL` k :: Int))+ [ bench "Bit" $ nf (\x -> (*) (toF2Poly $ randomVec Bit k) x) (toF2Poly $ randomVec Bit k)+ , bench "BitTS" $ nf (\x -> (*) (TS.toF2Poly $ randomVec TS.Bit k) x) (TS.toF2Poly $ randomVec TS.Bit k)+ , bench "Integer" $ nf (\x -> binMul (randomInteger k) x) (randomInteger k) ] binMul :: Integer -> Integer -> Integer
bench/Bench/RandomFlip.hs view
@@ -22,12 +22,10 @@ benchRandomFlip :: Int -> Benchmark benchRandomFlip k = bgroup (show (1 `shiftL` k :: Int))- [ bench "Bit/flip" $ nf randomFlipBit k- , bench "Bit/modify" $ nf randomFlipBit' k- , bench "Bit.TS/flip" $ nf randomFlipBitTS k- , bench "Bit.TS/modify" $ nf randomFlipBitTS' k- , bench "Vector" $ nf randomFlipVector k- , bench "IntSet" $ nf randomFlipIntSet k+ [ bench "Bit" $ nf randomFlipBit k+ , bench "BitTS" $ nf randomFlipBitTS k+ , bench "Vector" $ nf randomFlipVector k+ , bench "IntSet" $ nf randomFlipIntSet k ] randomFlipBit :: Int -> Int@@ -39,30 +37,12 @@ Bit i <- MU.unsafeRead vec 0 pure $ if i then 1 else 0 -randomFlipBit' :: Int -> Int-randomFlipBit' k = runST $ do- let n = 1 `shiftL` k- vec <- MU.new n- forM_ (take (mult * n) randomFlips) $- \i -> MU.unsafeModify vec complement (i .&. (1 `shiftL` k - 1))- Bit i <- MU.unsafeRead vec 0- pure $ if i then 1 else 0- randomFlipBitTS :: Int -> Int randomFlipBitTS k = runST $ do let n = 1 `shiftL` k vec <- MU.new n forM_ (take (mult * n) randomFlips) $ \i -> TS.unsafeFlipBit vec (i .&. (1 `shiftL` k - 1))- TS.Bit i <- MU.unsafeRead vec 0- pure $ if i then 1 else 0--randomFlipBitTS' :: Int -> Int-randomFlipBitTS' k = runST $ do- let n = 1 `shiftL` k- vec <- MU.new n- forM_ (take (mult * n) randomFlips) $- \i -> MU.unsafeModify vec complement (i .&. (1 `shiftL` k - 1)) TS.Bit i <- MU.unsafeRead vec 0 pure $ if i then 1 else 0
bench/Bench/RandomRead.hs view
@@ -30,7 +30,7 @@ benchRandomRead :: Int -> Benchmark benchRandomRead k = bgroup (show (1 `shiftL` k :: Int)) [ bench "Bit" $ nf randomReadBit k- , bench "Bit.TS" $ nf randomReadBitTS k+ , bench "BitTS" $ nf randomReadBitTS k , bench "Vector" $ nf randomReadVector k -- , bench "IntSet" $ nf randomReadIntSet k ]
bench/Bench/RandomWrite.hs view
@@ -23,7 +23,7 @@ benchRandomWrite :: Int -> Benchmark benchRandomWrite k = bgroup (show (1 `shiftL` k :: Int)) [ bench "Bit" $ nf randomWriteBit k- , bench "Bit.TS" $ nf randomWriteBitTS k+ , bench "BitTS" $ nf randomWriteBitTS k , bench "Vector" $ nf randomWriteVector k , bench "IntSet" $ nf randomWriteIntSet k ]
bench/Bench/Remainder.hs view
@@ -44,9 +44,9 @@ benchRemainder :: Int -> Benchmark benchRemainder k = bgroup (show (1 `shiftL` k :: Int))- [ bench "Bit/remainder" $ nf (\x -> rem (toF2Poly $ randomVec Bit k) x) (toF2Poly $ randomVec2 Bit k)- , bench "Bit.TS/remainder" $ nf (\x -> rem (TS.toF2Poly $ randomVec TS.Bit k) x) (TS.toF2Poly $ randomVec2 TS.Bit k)- , bench "Integer/remainder" $ nf (\x -> binRem (randomInteger k) x) (randomInteger2 k)+ [ bench "Bit" $ nf (\x -> rem (toF2Poly $ randomVec Bit k) x) (toF2Poly $ randomVec2 Bit k)+ , bench "BitTS" $ nf (\x -> rem (TS.toF2Poly $ randomVec TS.Bit k) x) (TS.toF2Poly $ randomVec2 TS.Bit k)+ , bench "Integer" $ nf (\x -> binRem (randomInteger k) x) (randomInteger2 k) ] binRem :: Integer -> Integer -> Integer
bench/Bench/Reverse.hs view
@@ -24,24 +24,16 @@ benchReverse :: Int -> Benchmark benchReverse k = bgroup (show (1 `shiftL` k :: Int))- [ bench "Bit/reverseBits" $ nf reverseBit (randomVec Bit k)- , bench "Bit/reverse" $ nf reverseBit' (randomVec Bit k)- , bench "Bit.TS/reverseBits" $ nf reverseBitTS (randomVec TS.Bit k)- , bench "Bit.TS/reverse" $ nf reverseBitTS' (randomVec TS.Bit k)- , bench "Vector" $ nf reverseVector (randomVec id k)+ [ bench "Bit" $ nf reverseBit (randomVec Bit k)+ , bench "BitTS" $ nf reverseBitTS (randomVec TS.Bit k)+ , bench "Vector" $ nf reverseVector (randomVec id k) ] reverseBit :: U.Vector Bit -> U.Vector Bit reverseBit = reverseBits -reverseBit' :: U.Vector Bit -> U.Vector Bit-reverseBit' = U.reverse- reverseBitTS :: U.Vector TS.Bit -> U.Vector TS.Bit reverseBitTS = TS.reverseBits--reverseBitTS' :: U.Vector TS.Bit -> U.Vector TS.Bit-reverseBitTS' = U.reverse reverseVector :: U.Vector Bool -> U.Vector Bool reverseVector = U.reverse
bench/Bench/Sum.hs view
@@ -1,5 +1,6 @@ module Bench.Sum- ( benchSum+ ( benchAdd+ , benchSum ) where import Data.Bit@@ -34,12 +35,16 @@ randomInteger2 :: Int -> Integer randomInteger2 k = toInteger $ toF2Poly $ randomVec2 Bit k +benchAdd :: Int -> Benchmark+benchAdd k = bgroup (show (1 `shiftL` k :: Int))+ [ bench "Bit" $ nf (\x -> (+) (toF2Poly $ randomVec Bit k) x) (toF2Poly $ randomVec2 Bit k)+ , bench "BitTS" $ nf (\x -> (+) (TS.toF2Poly $ randomVec TS.Bit k) x) (TS.toF2Poly $ randomVec2 TS.Bit k)+ , bench "Integer" $ nf (\x -> xor (randomInteger k) x) (randomInteger2 k)+ ]+ benchSum :: Int -> Benchmark benchSum k = bgroup (show (1 `shiftL` k :: Int))- [ bench "Bit/add" $ nf (\x -> (+) (toF2Poly $ randomVec Bit k) x) (toF2Poly $ randomVec2 Bit k)- , bench "Bit/sum" $ nf (foldl' (+) 0) [(1 :: F2Poly) .. fromInteger (1 `shiftL` k)]- , bench "Bit.TS/add" $ nf (\x -> (+) (TS.toF2Poly $ randomVec TS.Bit k) x) (TS.toF2Poly $ randomVec2 TS.Bit k)- , bench "Bit.TS/sum" $ nf (foldl' (+) 0) [(1 :: TS.F2Poly) .. fromInteger (1 `shiftL` k)]- , bench "Integer/add" $ nf (\x -> xor (randomInteger k) x) (randomInteger2 k)- , bench "Integer/sum" $ nf (foldl' xor 0) [(1 :: Integer) .. fromInteger (1 `shiftL` k)]+ [ bench "Bit" $ nf (foldl' (+) 0) [(1 :: F2Poly) .. fromInteger (1 `shiftL` k)]+ , bench "BitTS" $ nf (foldl' (+) 0) [(1 :: TS.F2Poly) .. fromInteger (1 `shiftL` k)]+ , bench "Integer" $ nf (foldl' xor 0) [(1 :: Integer) .. fromInteger (1 `shiftL` k)] ]
bench/Bench/Union.hs view
@@ -40,25 +40,17 @@ benchUnion :: Int -> Benchmark benchUnion k = bgroup (show (1 `shiftL` k :: Int))- [ bench "Bit/zipBits" $ nf (\x -> unionBit (randomVec Bit k) x) (randomVec2 Bit k)- , bench "Bit/zipWith" $ nf (\x -> unionBit' (randomVec Bit k) x) (randomVec2 Bit k)- , bench "Bit.TS/zipBits" $ nf (\x -> unionBitTS (randomVec TS.Bit k) x) (randomVec2 TS.Bit k)- , bench "Bit.TS/zipWith" $ nf (\x -> unionBitTS' (randomVec TS.Bit k) x) (randomVec2 TS.Bit k)- , bench "Vector" $ nf (\x -> unionVector (randomVec id k) x) (randomVec2 id k)- , bench "IntSet" $ nf (unionIntSet (randomSet k)) (randomSet2 k)+ [ bench "Bit" $ nf (\x -> unionBit (randomVec Bit k) x) (randomVec2 Bit k)+ , bench "BitTS" $ nf (\x -> unionBitTS (randomVec TS.Bit k) x) (randomVec2 TS.Bit k)+ , bench "Vector" $ nf (\x -> unionVector (randomVec id k) x) (randomVec2 id k)+ , bench "IntSet" $ nf (unionIntSet (randomSet k)) (randomSet2 k) ] unionBit :: U.Vector Bit -> U.Vector Bit -> U.Vector Bit unionBit = zipBits (.|.) -unionBit' :: U.Vector Bit -> U.Vector Bit -> U.Vector Bit-unionBit' = U.zipWith (\(Bit x) (Bit y) -> Bit (x || y))- unionBitTS :: U.Vector TS.Bit -> U.Vector TS.Bit -> U.Vector TS.Bit unionBitTS = TS.zipBits (.|.)--unionBitTS' :: U.Vector TS.Bit -> U.Vector TS.Bit -> U.Vector TS.Bit-unionBitTS' = U.zipWith (\(TS.Bit x) (TS.Bit y) -> TS.Bit (x || y)) unionVector :: U.Vector Bool -> U.Vector Bool -> U.Vector Bool unionVector = U.zipWith (||)
bitvec.cabal view
@@ -1,6 +1,6 @@ name: bitvec-version: 1.1.3.0-cabal-version: >=1.10+version: 1.1.4.0+cabal-version: 2.0 build-type: Simple license: BSD3 license-file: LICENSE@@ -29,7 +29,7 @@ This is because naive updates are not atomic: they read the whole word from memory, then modify a bit, then write the whole word back.- * "Data.Bit.ThreadSafe" is slower (up to 20%),+ * "Data.Bit.ThreadSafe" is slower (usually 10-20%), but writes and flips are thread-safe. . === Similar packages@@ -46,8 +46,8 @@ author: Andrew Lelechenko <andrew.lelechenko@gmail.com>, James Cook <mokus@deepbondi.net> -tested-with: GHC ==8.0.2 GHC ==8.2.2 GHC ==8.4.4 GHC ==8.6.5 GHC ==8.8.1 GHC ==8.8.2 GHC ==8.8.4 GHC ==8.10.7 GHC ==9.0.1 GHC ==9.2.1-extra-source-files:+tested-with: GHC ==8.4.4 GHC ==8.6.5 GHC ==8.8.1 GHC ==8.8.2 GHC ==8.8.4 GHC ==8.10.7 GHC ==9.0.2 GHC ==9.2.7 GHC ==9.4.4 GHC ==9.6.1+extra-doc-files: changelog.md README.md @@ -68,9 +68,9 @@ Data.Bit Data.Bit.ThreadSafe build-depends:- base >=4.9 && <5,- bytestring >=0.10,- deepseq,+ base >=4.11 && <5,+ bytestring >=0.10 && <0.12,+ deepseq <1.5, primitive >=0.5, vector >=0.11 && <0.14 default-language: Haskell2010@@ -78,7 +78,6 @@ other-modules: Data.Bit.F2Poly Data.Bit.F2PolyTS- Data.Bit.Gmp Data.Bit.Immutable Data.Bit.ImmutableTS Data.Bit.Internal@@ -98,6 +97,8 @@ if flag(libgmp) extra-libraries: gmp cpp-options: -DUseLibGmp+ other-modules:+ Data.Bit.Gmp test-suite bitvec-tests type: exitcode-stdio-1.0@@ -105,12 +106,12 @@ build-depends: base, bitvec,- primitive >=0.5,- quickcheck-classes-base,- quickcheck-classes >=0.6.1,+ primitive >=0.5 && <0.9,+ quickcheck-classes-base <0.7,+ quickcheck-classes >=0.6.1 && <0.7, vector >=0.11,- tasty,- tasty-quickcheck+ tasty <1.5,+ tasty-quickcheck <0.11 default-language: Haskell2010 hs-source-dirs: test other-modules:@@ -126,7 +127,7 @@ include-dirs: test if impl(ghc <9.0)- build-depends: integer-gmp+ build-depends: integer-gmp <1.2 else build-depends: ghc-bignum @@ -134,9 +135,10 @@ build-depends: base, bitvec,- containers,- random,- tasty-bench,+ containers <0.7,+ random <1.3,+ tasty,+ tasty-bench >=0.3.2 && <0.4, vector type: exitcode-stdio-1.0 main-is: Bench.hs
changelog.md view
@@ -1,3 +1,8 @@+# 1.1.4.0++* Include `Data.Bit.Gmp` only if `libgmp` flag is set.+* Tweak inlining pragmas to inline less aggressively.+ # 1.1.3.0 * Fix malformed `signum` for `F2Poly`.
src/Data/Bit.hs view
@@ -9,7 +9,10 @@ -- Maintainer: Andrew Lelechenko <andrew.lelechenko@gmail.com> -- -- This module exposes an interface with thread-unsafe writes and flips.--- Consider using "Data.Bit.ThreadSafe", which is thread-safe, but slower (up to 20%).+-- Consider using "Data.Bit.ThreadSafe", which is thread-safe, but slower+-- (usually 10-20%, up to 50% for short vectors).+--+-- @since 0.1 module Data.Bit #else -- |@@ -19,7 +22,10 @@ -- Maintainer: Andrew Lelechenko <andrew.lelechenko@gmail.com> -- -- This module exposes an interface with thread-safe writes and flips.--- Consider using "Data.Bit", which is faster (up to 20%), but thread-unsafe.+-- Consider using "Data.Bit", which is faster+-- (usually 10-20%, up to 50% for short vectors), but thread-unsafe.+--+-- @since 1.0 module Data.Bit.ThreadSafe #endif ( Bit(..)
src/Data/Bit/Immutable.hs view
@@ -61,9 +61,9 @@ import qualified Data.Vector.Primitive as P import qualified Data.Vector.Storable as S import qualified Data.Vector.Unboxed as U+import qualified Data.Vector.Unboxed.Base as UB import qualified Data.Vector.Unboxed.Mutable as MU import Data.Word-import Unsafe.Coerce #ifdef WORDS_BIGENDIAN import GHC.Exts@@ -193,7 +193,7 @@ v' <- U.unsafeThaw v w <- cloneToWordsM v' U.unsafeFreeze w-{-# INLINE cloneToWords #-}+{-# INLINABLE cloneToWords #-} -- | Cast an unboxed vector of 'Word8' -- to an unboxed vector of bits.@@ -210,7 +210,7 @@ castFromWords8 ws = BitVec (off `shiftL` 3) (len `shiftL` 3) arr where #ifdef WORDS_BIGENDIAN- P.Vector off' len arr' = unsafeCoerce ws+ UB.V_Word8 (P.Vector off' len arr') = ws off = 0 arr = runST $ do let lenWords = nWords $ len `shiftL` 3@@ -223,7 +223,7 @@ writeByteArray marr i (W# (byteSwap# w)) unsafeFreezeByteArray marr #else- P.Vector off len arr = unsafeCoerce ws+ UB.V_Word8 (P.Vector off len arr) = ws #endif -- | Try to cast an unboxed vector of bits@@ -240,7 +240,7 @@ #else castToWords8 (BitVec s n ws) | s .&. 7 == 0, n .&. 7 == 0- = Just $ unsafeCoerce $ P.Vector (s `shiftR` 3) (n `shiftR` 3) ws+ = Just $ UB.V_Word8 $ P.Vector (s `shiftR` 3) (n `shiftR` 3) ws | otherwise = Nothing #endif @@ -259,7 +259,7 @@ v' <- U.unsafeThaw v w <- cloneToWords8M v' U.unsafeFreeze w-{-# INLINE cloneToWords8 #-}+{-# INLINABLE cloneToWords8 #-} -- | Clone a 'BS.ByteString' to a new unboxed vector of bits. --@@ -359,7 +359,7 @@ forM_ [0, wordSize .. n - 1] $ \i -> writeWord zs i (f (indexWord xs i) (indexWord ys i)) U.unsafeFreeze zs-{-# INLINE zipBits #-}+{-# INLINABLE zipBits #-} -- | Map a vectors with the given function. -- Similar to 'Data.Vector.Unboxed.map',@@ -375,11 +375,11 @@ :: (forall a . Bits a => a -> a) -> U.Vector Bit -> U.Vector Bit-mapBits f xs = case (unBit (f (Bit False)), unBit (f (Bit True))) of- (False, False) -> U.replicate (U.length xs) (Bit False)- (False, True) -> xs- (True, False) -> invertBits xs- (True, True) -> U.replicate (U.length xs) (Bit True)+mapBits f = case (unBit (f (Bit False)), unBit (f (Bit True))) of+ (False, False) -> (`U.replicate` Bit False) . U.length+ (False, True) -> id+ (True, False) -> invertBits+ (True, True) -> (`U.replicate` Bit True) . U.length {-# INLINE mapBits #-} -- | Invert (flip) all bits.@@ -412,7 +412,8 @@ -- | For each set bit of the first argument, deposit -- the corresponding bit of the second argument--- to the result. Similar to the parallel deposit instruction (PDEP).+-- to the result. Similar to the+-- [parallel bit deposit instruction (PDEP)](https://en.wikipedia.org/wiki/X86_Bit_manipulation_instruction_set#Parallel_bit_deposit_and_extract). -- -- >>> :set -XOverloadedLists -- >>> selectBits [0,1,0,1,1] [1,1,0,0,1]
src/Data/Bit/Internal.hs view
@@ -57,7 +57,7 @@ -- as efficient as possible (8 values per byte). -- Unboxed vectors of `Bit` use 8x less memory -- than unboxed vectors of 'Bool' (which store one value per byte),--- but random writes are up to 10% slower.+-- but random writes are slightly slower. -- -- @since 0.1 newtype Bit = Bit {@@ -75,7 +75,9 @@ -- as efficient as possible (8 values per byte). -- Unboxed vectors of `Bit` use 8x less memory -- than unboxed vectors of 'Bool' (which store one value per byte),--- but random writes are up to 20% slower.+-- but random writes are slightly slower.+--+-- @since 1.0.0.0 newtype Bit = Bit { unBit :: Bool -- ^ @since 0.2.0.0 } deriving
src/Data/Bit/Mutable.hs view
@@ -85,7 +85,7 @@ MU.unsafeCopy (MU.slice 0 lenBits w) v MU.set (MU.slice lenBits (mulWordSize lenWords - lenBits) w) (Bit False) pure $ MU.MV_Word $ P.MVector 0 lenWords arr-{-# INLINE cloneToWordsM #-}+{-# INLINABLE cloneToWordsM #-} -- | Clone a vector of bits to a new unboxed vector of 'Word8'. -- If the bits don't completely fill the words, the last 'Word8' will be zero-padded.@@ -110,7 +110,7 @@ #endif pure $ MU.MV_Word8 $ P.MVector 0 actualLenBytes arr-{-# INLINE cloneToWords8M #-}+{-# INLINABLE cloneToWords8M #-} -- | Zip two vectors with the given function, -- rewriting the contents of the second argument.@@ -200,7 +200,7 @@ loop (i + 1) accNew {-# SPECIALIZE zipInPlace :: (forall a. Bits a => a -> a -> a) -> Vector Bit -> MVector s Bit -> ST s () #-}-{-# INLINE zipInPlace #-}+{-# INLINABLE zipInPlace #-} -- | Apply a function to a mutable vector bitwise, -- rewriting its contents.@@ -217,11 +217,11 @@ => (forall a . Bits a => a -> a) -> U.MVector (PrimState m) Bit -> m ()-mapInPlace f xs = case (unBit (f (Bit False)), unBit (f (Bit True))) of- (False, False) -> MU.set xs (Bit False)- (False, True) -> pure ()- (True, False) -> invertInPlace xs- (True, True) -> MU.set xs (Bit True)+mapInPlace f = case (unBit (f (Bit False)), unBit (f (Bit True))) of+ (False, False) -> (`MU.set` Bit False)+ (False, True) -> const $ pure ()+ (True, False) -> invertInPlace+ (True, True) -> (`MU.set` Bit True) {-# SPECIALIZE mapInPlace :: (forall a. Bits a => a -> a) -> MVector s Bit -> ST s () #-} {-# INLINE mapInPlace #-}
src/Data/Bit/PdepPext.hs view
@@ -6,7 +6,6 @@ -- | Parallel bit deposit and extract instructions. -- https://en.wikipedia.org/wiki/Bit_Manipulation_Instruction_Sets#Parallel_bit_deposit_and_extract -{-# LANGUAGE CPP #-} {-# LANGUAGE MagicHash #-} module Data.Bit.PdepPext@@ -14,8 +13,6 @@ , pext ) where -#if MIN_VERSION_base(4,11,0)- import GHC.Exts pdep :: Word -> Word -> Word@@ -23,32 +20,3 @@ pext :: Word -> Word -> Word pext (W# src#) (W# mask#) = W# (pext# src# mask#)--#else--import Data.Bits--pdep :: Word -> Word -> Word-pdep = go 0- where- go :: Word -> Word -> Word -> Word- go result _ 0 = result- go result src mask = go newResult newSrc newMask- where- lowest = 1 `shiftL` countTrailingZeros mask- newResult = if src .&. 1 == 0 then result else result .|. lowest- newSrc = src `shiftR` 1- newMask = mask .&. complement lowest--pext :: Word -> Word -> Word-pext src mask = loop 0 0 0- where- loop i count acc- | i >= finiteBitSize (0 :: Word)- = acc- | testBit mask i- = loop (i + 1) (count + 1) (if testBit src i then setBit acc count else acc)- | otherwise- = loop (i + 1) count acc--#endif
src/Data/Bit/Utils.hs view
@@ -28,10 +28,10 @@ import Data.Bits import qualified Data.Vector.Primitive as P import qualified Data.Vector.Unboxed as U+import qualified Data.Vector.Unboxed.Base as UB #if __GLASGOW_HASKELL__ >= 810 import GHC.Exts #endif-import Unsafe.Coerce import Data.Bit.PdepPext @@ -206,9 +206,9 @@ {-# INLINE hiMask #-} fromPrimVector :: P.Vector Word -> U.Vector Word-fromPrimVector = unsafeCoerce+fromPrimVector = UB.V_Word {-# INLINE fromPrimVector #-} toPrimVector :: U.Vector Word -> P.Vector Word-toPrimVector = unsafeCoerce+toPrimVector (UB.V_Word ws) = ws {-# INLINE toPrimVector #-}
test/Tests/Vector.hs view
@@ -13,10 +13,10 @@ import Data.List (findIndex) import qualified Data.Vector.Primitive as P import qualified Data.Vector.Unboxed as U+import qualified Data.Vector.Unboxed.Base as UB import Data.Word import Test.Tasty import Test.Tasty.QuickCheck (Property, NonNegative(..), Positive(..), testProperty, Large(..), (===), property, once, (==>), ioProperty, (.&&.), counterexample)-import Unsafe.Coerce #include "MachDeps.h" @@ -146,7 +146,7 @@ = counterexample ("offset = " ++ show off ++ " len = " ++ show len) $ U.toList (castFromWords8 ws) === concatMap wordToBitList (U.toList ws) where- P.Vector off len _ = unsafeCoerce ws+ UB.V_Word8 (P.Vector off len _) = ws prop_cloneToWords8_def :: U.Vector Bit -> Property prop_cloneToWords8_def xs@(BitVec off len _)@@ -165,7 +165,7 @@ = counterexample ("offset = " ++ show off ++ " len = " ++ show len) $ Just ws === castToWords8 (castFromWords8 ws) where- P.Vector off len _ = unsafeCoerce ws+ UB.V_Word8 (P.Vector off len _) = ws #endif prop_castToWords8_2 :: U.Vector Bit -> Property