hw-rankselect-base 0.3.2.1 → 0.3.2.2

raw patch · 9 files changed

+157/−202 lines, 9 filesdep −safedep ~criteriondep ~hedgehogPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependencies removed: safe

Dependency ranges changed: criterion, hedgehog

API changes (from Hackage documentation)

Files

• README.md +51/−7
• hw-rankselect-base.cabal +87/−95
• src/HaskellWorks/Data/RankSelect/Base/Internal.hs +3/−3
• src/HaskellWorks/Data/RankSelect/Base/Rank.hs +0/−18
• src/HaskellWorks/Data/RankSelect/Base/Rank1.hs +0/−10
• src/HaskellWorks/Data/RankSelect/Base/Select.hs +0/−18
• src/HaskellWorks/Data/RankSelect/Base/Select1.hs +16/−28
• test/HaskellWorks/Data/RankSelect/Base/Rank1Spec.hs +0/−8
• test/HaskellWorks/Data/RankSelect/Base/Select1Spec.hs +0/−15

@@ -1,5 +1,6 @@ # hw-rankselect-base [![CircleCI](https://circleci.com/gh/haskell-works/hw-rankselect-base.svg?style=svg)](https://circleci.com/gh/haskell-works/hw-rankselect-base)+[![Travis](https://travis-ci.org/haskell-works/hw-rankselect-base.svg?branch=master)](https://travis-ci.org/haskell-works/hw-rankselect-base)  Rank and select operations. @@ -27,16 +28,35 @@ from both `Data.Vector`, and `Data.Vector.Storable` of these primitive types. -The collection-based type classes instances are not intended to be used-in high-performance code because they have poor performance for most-purposes and are provided purely as reference implementations.+## Examples -Bit-vectors larger than 64-bits need indexing to achieve higher performance.-A indexed bit-vector implementation can found in the-[hw-rankselect](https://hackage.haskell.org/package/hw-rankselect) package.+Check the convenience imports in the project's `.ghci` file. -## Notes+Run the repl in convenience script (uses stack). +```+$ ./run-stack.sh repl+```++Then create a rank-select bit-string of the desired type:+++```+λ> let bs = fromJust $ bitRead "0001001001100001000001000110101000101000" :: Word64+"00010010 01100001 00000100 01101010 00101000 00000000 00000000 00000000"+```++Call the rank-select operations on the bit-string++```+λ> rank1 bs 20+1+λ> select1 bs 4+11+```++## Vector indexing conventions+ This library follows standard 1-based counting conventions typically found in Computer Science literature where `select1 10 2 = 4` as illustrated here: @@ -55,6 +75,30 @@   7 6 5 4  [3]2 1 0   0 0 0 0   1 0 1 0 ```++## Performance notes++The word-vector-based type classes instances are not intended to be used+in high-performance code because where random-access on large bit-vectors+are needed because they have poor performance due to having to do a linear+scan.++For smaller bit-vectors that fit on one page of memory, they do quite well.+In fact, the [hw-dsv](https://github.com/haskell-works/hw-dsv) library+uses them for small vectors.++Bit-vectors larger than say 4096-bits need indexing to achieve reasonable+random-access performance.++An indexed bit-vector implementation can found in the+[hw-rankselect](https://hackage.haskell.org/package/hw-rankselect) package.++## Architecture notes++This library has only been tested on little-endian CPU architectures.++Anyone wishing to use this on big-endian CPU architectures will need to+confirm that this works properly.  ## Compilation 

@@ -1,27 +1,20 @@--- This file has been generated from package.yaml by hpack version 0.20.0.------ see: https://github.com/sol/hpack------ hash: 15ac58f5a21cf2d2874629af4d19d7916c03ddbb8e42234fb1440b5b8e92ce76--name:           hw-rankselect-base-version:        0.3.2.1-synopsis:       Rank-select base-description:    Please see README.md-category:       Data-homepage:       http://github.com/haskell-works/hw-rankselect-base#readme-bug-reports:    https://github.com/haskell-works/hw-rankselect-base/issues-author:         John Ky-maintainer:     newhoggy@gmail.com-copyright:      2016 John Ky-license:        BSD3-license-file:   LICENSE-tested-with:    GHC == 8.4.2, GHC == 8.2.2, GHC == 8.0.2, GHC == 7.10.3-build-type:     Simple-cabal-version:  >= 1.10+cabal-version: 2.2 -extra-source-files:-    README.md+name:                   hw-rankselect-base+version:                0.3.2.2+synopsis:               Rank-select base+description:            Please see README.md+category:               Data, Bit, Succinct Data Structures, Data Structures+homepage:               http://github.com/haskell-works/hw-rankselect-base#readme+bug-reports:            https://github.com/haskell-works/hw-rankselect-base/issues+author:                 John Ky+maintainer:             newhoggy@gmail.com+copyright:              2016-2019 John Ky+license:                BSD-3-Clause+license-file:           LICENSE+tested-with:            GHC == 8.8.1, GHC == 8.6.5, GHC == 8.4.4, GHC == 8.2.2+build-type:             Simple+extra-source-files:     README.md  source-repository head   type: git@@ -32,82 +25,81 @@   manual: False   default: False -library-  hs-source-dirs:-      src-  ghc-options: -Wall -O2 -msse4.2-  build-depends:-      base >=4.8 && <5-    , bits-extra >=0.0.0.4 && <0.1-    , hw-bits >=0.7.0.2 && <0.8-    , hw-int >=0.0.0.1 && <0.1-    , hw-prim >=0.5.0.5 && <0.7-    , hw-string-parse >=0.0.0.2 && <0.1-    , safe-    , vector >=0.12 && <0.13+common base                           { build-depends: base                           >= 4.8        && < 5      }++common QuickCheck                     { build-depends: QuickCheck                     >= 2.10       && < 2.14   }+common bits-extra                     { build-depends: bits-extra                     >= 0.0.0.4    && < 0.1    }+common criterion                      { build-depends: criterion                      >= 1.2        && < 1.6    }+common hedgehog                       { build-depends: hedgehog                       >= 0.6        && < 1.1    }+common hspec                          { build-depends: hspec                          >= 2.2        && < 3      }+common hw-bits                        { build-depends: hw-bits                        >= 0.7.0.2    && < 0.8    }+common hw-hedgehog                    { build-depends: hw-hedgehog                    >= 0.1        && < 0.2    }+common hw-hspec-hedgehog              { build-depends: hw-hspec-hedgehog              >= 0.1        && < 0.2    }+common hw-int                         { build-depends: hw-int                         >= 0.0.0.1    && < 0.1    }+common hw-prim                        { build-depends: hw-prim                        >= 0.5.0.5    && < 0.7    }+common hw-string-parse                { build-depends: hw-string-parse                >= 0.0.0.2    && < 0.1    }+common vector                         { build-depends: vector                         >= 0.12       && < 0.13   }++common config+  default-language:     Haskell2010+  ghc-options:          -Wall -fwarn-tabs -fwarn-incomplete-uni-patterns -fwarn-incomplete-record-updates -O2 -msse4.2   if (flag(bmi2)) && (impl(ghc >=8.4.1))     ghc-options: -mbmi2 -msse4.2     cpp-options: -DBMI2_ENABLED-  exposed-modules:-      HaskellWorks.Data.RankSelect.Base-      HaskellWorks.Data.RankSelect.Base.Internal-      HaskellWorks.Data.RankSelect.Base.Rank-      HaskellWorks.Data.RankSelect.Base.Rank0-      HaskellWorks.Data.RankSelect.Base.Rank1-      HaskellWorks.Data.RankSelect.Base.Select-      HaskellWorks.Data.RankSelect.Base.Select0-      HaskellWorks.Data.RankSelect.Base.Select1-  other-modules:-      Paths_hw_rankselect_base-  default-language: Haskell2010 +library+  import:               base, config+                      , bits-extra+                      , hw-bits+                      , hw-int+                      , hw-prim+                      , hw-string-parse+                      , vector+  exposed-modules:      HaskellWorks.Data.RankSelect.Base+                        HaskellWorks.Data.RankSelect.Base.Internal+                        HaskellWorks.Data.RankSelect.Base.Rank0+                        HaskellWorks.Data.RankSelect.Base.Rank1+                        HaskellWorks.Data.RankSelect.Base.Select0+                        HaskellWorks.Data.RankSelect.Base.Select1+  other-modules:        Paths_hw_rankselect_base+  autogen-modules:      Paths_hw_rankselect_base+  hs-source-dirs:       src+ test-suite hw-rankselect-base-test-  type: exitcode-stdio-1.0-  main-is: Spec.hs-  hs-source-dirs:-      test-  ghc-options: -Wall -threaded -rtsopts -with-rtsopts=-N-  build-depends:-      QuickCheck >=2.10 && <2.12-    , base >=4.8 && <5-    , bits-extra >=0.0.0.4 && <0.1-    , hedgehog >=0.5 && <0.7-    , hspec >=2.2 && <2.6-    , hw-bits >=0.7.0.2 && <0.8-    , hw-hedgehog >=0.1 && <0.2-    , hw-hspec-hedgehog >=0.1 && <0.2-    , hw-prim >=0.5.0.5 && <0.7-    , hw-rankselect-base-    , vector >=0.12 && <0.13-  if (flag(bmi2)) && (impl(ghc >=8.4.1))-    ghc-options: -mbmi2 -msse4.2-    cpp-options: -DBMI2_ENABLED-  other-modules:-      HaskellWorks.Data.RankSelect.Base.InternalSpec-      HaskellWorks.Data.RankSelect.Base.Rank0Spec-      HaskellWorks.Data.RankSelect.Base.Rank1Spec-      HaskellWorks.Data.RankSelect.Base.Select0Spec-      HaskellWorks.Data.RankSelect.Base.Select1Spec-      Paths_hw_rankselect_base-  default-language: Haskell2010+  import:               base, config+                      , QuickCheck+                      , bits-extra+                      , hedgehog+                      , hspec+                      , hw-bits+                      , hw-hedgehog+                      , hw-hspec-hedgehog+                      , hw-prim+                      , vector+  type:                 exitcode-stdio-1.0+  main-is:              Spec.hs+  other-modules:        HaskellWorks.Data.RankSelect.Base.InternalSpec+                        HaskellWorks.Data.RankSelect.Base.Rank0Spec+                        HaskellWorks.Data.RankSelect.Base.Rank1Spec+                        HaskellWorks.Data.RankSelect.Base.Select0Spec+                        HaskellWorks.Data.RankSelect.Base.Select1Spec+                        Paths_hw_rankselect_base+  autogen-modules:      Paths_hw_rankselect_base+  hs-source-dirs:       test+  ghc-options:          -threaded -rtsopts -with-rtsopts=-N+  build-depends:        hw-rankselect-base+  build-tool-depends:   hspec-discover:hspec-discover  benchmark bench-  type: exitcode-stdio-1.0-  main-is: Main.hs-  hs-source-dirs:-      bench-  ghc-options: -Wall -O2 -msse4.2-  build-depends:-      base >=4.8 && <5-    , bits-extra >=0.0.0.4 && <0.1-    , criterion >=1.2 && <1.5-    , hw-bits >=0.7.0.2 && <0.8-    , hw-prim >=0.5.0.5 && <0.7-    , hw-rankselect-base-    , vector >=0.12 && <0.13-  if (flag(bmi2)) && (impl(ghc >=8.4.1))-    ghc-options: -mbmi2 -msse4.2-    cpp-options: -DBMI2_ENABLED-  other-modules:-      Paths_hw_rankselect_base-  default-language: Haskell2010+  import:               base, config+                      , bits-extra+                      , criterion+                      , hw-bits+                      , hw-prim+                      , vector+  type:                 exitcode-stdio-1.0+  main-is:              Main.hs+  other-modules:        Paths_hw_rankselect_base+  autogen-modules:      Paths_hw_rankselect_base+  hs-source-dirs:       bench+  build-depends:        hw-rankselect-base

@@ -23,16 +23,16 @@  select1Word64Bmi2 :: Word64 -> Word64 -> Word64 select1Word64Bmi2 w r =-  let zeros = countTrailingZeros (pdep (1 .<. (r - 1)) w) :: Int+  let zeros = countTrailingZeros (pdep (1 .<. ((r - 1) .&. 0x7f)) w) :: Int       mask  = fromIntegral ((fromIntegral (zeros .<. 57) :: Int64) `shiftR` 63) :: Word64   in (fromIntegral zeros .|. mask) + 1 {-# INLINE select1Word64Bmi2 #-}  select1Word32Bmi2 :: Word32 -> Word64 -> Word64 select1Word32Bmi2 w r =-  let zeros = countTrailingZeros (pdep (1 .<. (r - 1)) w) :: Int+  let zeros = countTrailingZeros (pdep (1 .<. ((r - 1) .&. 0x7f)) w) :: Int       mask  = fromIntegral ((fromIntegral (zeros .<. 58) :: Int64) `shiftR` 63) :: Word64-  in (fromIntegral zeros .|. mask) + 1+          in (fromIntegral zeros .|. mask) + 1 {-# INLINE select1Word32Bmi2 #-}  select1Word64Broadword :: Word64 -> Word64 -> Word64

@@ -1,18 +0,0 @@-{-# LANGUAGE FlexibleInstances     #-}-{-# LANGUAGE MultiParamTypeClasses #-}--module HaskellWorks.Data.RankSelect.Base.Rank-  ( -- * Rank & Select-    Rank(..)-  ) where--import HaskellWorks.Data.Positioning-import HaskellWorks.Data.RankSelect.Base.Rank0-import HaskellWorks.Data.RankSelect.Base.Rank1--class Eq a => Rank v a where-  rank :: a -> v -> Count -> Count--instance Rank [Bool] Bool where-  rank a = if a then rank1 else rank0-  {-# INLINABLE rank #-}

@@ -6,7 +6,6 @@     ( Rank1(..)     ) where -import Data.Bits.BitSize import Data.Word import HaskellWorks.Data.AtIndex import HaskellWorks.Data.Bits.BitShown@@ -51,15 +50,6 @@   rank1 False 0 = 0   rank1 False 1 = 0   rank1 _     _ = error "Invalid position for rank1"--instance (PopCount1 w, Rank1 w, BitSize w) => Rank1 [w] where-  rank1 = go 0-    where go c (w:ws) p = if p <= bitCount w-            then c + rank1 w p-            else go (c + popCount1 w) ws (p - bitCount w)-          go c [] _ = c--  {-# INLINABLE rank1 #-}  instance Rank1 (DV.Vector Word8) where   rank1 v p = popCount1 prefix + if r == 0 then 0 else (`rank1` r) maybeElem

@@ -1,18 +0,0 @@-{-# LANGUAGE FlexibleInstances     #-}-{-# LANGUAGE MultiParamTypeClasses #-}--module HaskellWorks.Data.RankSelect.Base.Select-    ( -- * Rank & Select-      Select(..)-    ) where--import HaskellWorks.Data.Positioning-import HaskellWorks.Data.RankSelect.Base.Select0-import HaskellWorks.Data.RankSelect.Base.Select1--class Eq a => Select v a where-  select :: a -> v -> Count -> Count--instance Select [Bool] Bool where-  select a = if a then select1 else select0-  {-# INLINABLE select #-}

@@ -7,7 +7,6 @@     ( Select1(..)     ) where -import Data.Bits.BitSize import Data.Word import HaskellWorks.Data.AtIndex import HaskellWorks.Data.Bits.BitShown@@ -82,8 +81,8 @@     where go _ 0  acc = acc           go n d acc = let w = (v !!! n) in             case popCount1 w of-              pc | d <= pc  -> select1 w d + acc-              pc -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)+              pc | d <= pc -> select1 w d + acc+              pc           -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)   {-# INLINE select1 #-}  instance Select1 (DVS.Vector Word16) where@@ -91,8 +90,8 @@     where go _ 0  acc = acc           go n d acc = let w = (v !!! n) in             case popCount1 w of-              pc | d <= pc  -> select1 w d + acc-              pc -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)+              pc | d <= pc -> select1 w d + acc+              pc           -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)   {-# INLINE select1 #-}  instance Select1 (DVS.Vector Word32) where@@ -100,8 +99,8 @@     where go _ 0  acc = acc           go n d acc = let w = (v !!! n) in             case popCount1 w of-              pc | d <= pc  -> select1 w d + acc-              pc -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)+              pc | d <= pc -> select1 w d + acc+              pc           -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)   {-# INLINE select1 #-}  instance Select1 (DVS.Vector Word64) where@@ -109,8 +108,8 @@     where go _ 0  acc = acc           go n d acc = let w = (v !!! n) in             case popCount1 w of-              pc | d <= pc  -> select1 w d + acc-              pc -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)+              pc | d <= pc -> select1 w d + acc+              pc           -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)   {-# INLINE select1 #-}  instance Select1 (DV.Vector Word8) where@@ -118,8 +117,8 @@     where go _ 0  acc = acc           go n d acc = let w = (v !!! n) in             case popCount1 w of-              pc | d <= pc  -> select1 w d + acc-              pc -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)+              pc | d <= pc -> select1 w d + acc+              pc           -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)   {-# INLINE select1 #-}  instance Select1 (DV.Vector Word16) where@@ -127,8 +126,8 @@     where go _ 0  acc = acc           go n d acc = let w = (v !!! n) in             case popCount1 w of-              pc | d <= pc  -> select1 w d + acc-              pc -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)+              pc | d <= pc -> select1 w d + acc+              pc           -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)   {-# INLINE select1 #-}  instance Select1 (DV.Vector Word32) where@@ -136,8 +135,8 @@     where go _ 0  acc = acc           go n d acc = let w = (v !!! n) in             case popCount1 w of-              pc | d <= pc  -> select1 w d + acc-              pc -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)+              pc | d <= pc -> select1 w d + acc+              pc           -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)   {-# INLINE select1 #-}  instance Select1 (DV.Vector Word64) where@@ -145,17 +144,6 @@     where go _ 0  acc = acc           go n d acc = let w = (v !!! n) in             case popCount1 w of-              pc | d <= pc  -> select1 w d + acc-              pc -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)-  {-# INLINE select1 #-}--instance (PopCount1 w, Select1 w, BitSize w) => Select1 [w] where-  select1 v c = go v c 0-    where go _ 0 acc = acc-          go u d acc = case u of-            w:ws -> let pc = popCount1 w in-              if d <= pc-                then select1 w d + acc-                else go ws (d - pc) (acc + bitCount w)-            [] -> acc+              pc | d <= pc -> select1 w d + acc+              pc           -> go (n + 1) (d - pc) (acc + elemFixedBitSize v)   {-# INLINE select1 #-}

@@ -49,14 +49,6 @@   genRank1UpTo8Spec (undefined :: Word16)   genRank1UpTo8Spec (undefined :: Word32)   genRank1UpTo8Spec (undefined :: Word64)-  genRank1UpTo8Spec (undefined :: [Word8])-  genRank1UpTo16Spec (undefined :: [Word8])-  genRank1UpTo8Spec (undefined :: [Word16])-  genRank1UpTo16Spec (undefined :: [Word16])-  genRank1UpTo8Spec (undefined :: [Word32])-  genRank1UpTo16Spec (undefined :: [Word32])-  genRank1UpTo8Spec (undefined :: [Word64])-  genRank1UpTo16Spec (undefined :: [Word64])   genRank1UpTo8Spec (undefined :: DV.Vector Word8)   genRank1UpTo16Spec (undefined :: DV.Vector Word8)   genRank1UpTo8Spec (undefined :: DV.Vector Word16)

@@ -67,21 +67,6 @@   genSelect1UpTo16Spec (undefined :: Word64)   genSelect1UpTo32Spec (undefined :: Word32)   genSelect1UpTo32Spec (undefined :: Word64)-  genSelect1UpTo8Spec  (undefined :: [Bool])-  genSelect1UpTo16Spec (undefined :: [Bool])-  genSelect1UpTo32Spec (undefined :: [Bool])-  genSelect1UpTo8Spec  (undefined :: [Word8])-  genSelect1UpTo16Spec (undefined :: [Word8])-  genSelect1UpTo32Spec (undefined :: [Word8])-  genSelect1UpTo8Spec  (undefined :: [Word16])-  genSelect1UpTo16Spec (undefined :: [Word16])-  genSelect1UpTo32Spec (undefined :: [Word16])-  genSelect1UpTo8Spec  (undefined :: [Word32])-  genSelect1UpTo16Spec (undefined :: [Word32])-  genSelect1UpTo32Spec (undefined :: [Word32])-  genSelect1UpTo8Spec  (undefined :: [Word64])-  genSelect1UpTo16Spec (undefined :: [Word64])-  genSelect1UpTo32Spec (undefined :: [Word64])   genSelect1UpTo8Spec  (undefined :: DV.Vector Word8)   genSelect1UpTo16Spec (undefined :: DV.Vector Word8)   genSelect1UpTo32Spec (undefined :: DV.Vector Word8)