hw-rankselect-base 0.2.0.0 → 0.2.0.1
raw patch · 3 files changed
+38/−54 lines, 3 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
Files
- bench/Main.hs +17/−1
- hw-rankselect-base.cabal +1/−1
- src/HaskellWorks/Data/RankSelect/Base/Rank1.hs +20/−52
bench/Main.hs view
@@ -12,7 +12,23 @@ benchRankSelect :: [Benchmark] benchRankSelect =- [ env (setupEnvVector 1000000) $ \bv -> bgroup "Rank"+ [ env (return ()) $ \_ -> bgroup "8-bit"+ [ bench "Rank - Once" (whnf (rank1 (0x55 :: Word8)) 8)+ , bench "Select - Once" (whnf (select1 (0x55 :: Word8)) 8)+ ]+ , env (return ()) $ \_ -> bgroup "16-bit"+ [ bench "Rank - Once" (whnf (rank1 (0x5555 :: Word16)) 16)+ , bench "Select - Once" (whnf (select1 (0x5555 :: Word16)) 16)+ ]+ , env (return ()) $ \_ -> bgroup "32-bit"+ [ bench "Rank - Once" (whnf (rank1 (0x55555555 :: Word32)) 32)+ , bench "Select - Once" (whnf (select1 (0x55555555 :: Word32)) 32)+ ]+ , env (return ()) $ \_ -> bgroup "64-bit"+ [ bench "Rank - Once" (whnf (rank1 (0x5555555555555555 :: Word64)) 64)+ , bench "Select - Once" (whnf (select1 (0x5555555555555555 :: Word64)) 64)+ ]+ , env (setupEnvVector 1000000) $ \bv -> bgroup "64-bit vector" [ bench "Rank - Once" (whnf (rank1 bv) 1) , bench "Select - Once" (whnf (select1 bv) 1) , bench "Rank - Many" (nf (map (rank1 bv)) [0, 1000..10000000])
hw-rankselect-base.cabal view
@@ -1,5 +1,5 @@ name: hw-rankselect-base-version: 0.2.0.0+version: 0.2.0.1 synopsis: Rank-select base description: Please see README.md homepage: http://github.com/haskell-works/hw-rankselect-base#readme
src/HaskellWorks/Data/RankSelect/Base/Rank1.hs view
@@ -6,18 +6,18 @@ ( Rank1(..) ) where -import qualified Data.Vector as DV-import qualified Data.Vector.Storable as DVS-import Data.Word-import HaskellWorks.Data.AtIndex-import HaskellWorks.Data.Bits.BitShown-import HaskellWorks.Data.Bits.BitWise-import HaskellWorks.Data.Bits.ElemFixedBitSize-import HaskellWorks.Data.Bits.PopCount.PopCount1-import HaskellWorks.Data.Int.Widen.Widen64-import HaskellWorks.Data.Positioning-import Prelude as P+import Data.Word+import HaskellWorks.Data.AtIndex+import HaskellWorks.Data.Bits.BitShown+import HaskellWorks.Data.Bits.BitWise+import HaskellWorks.Data.Bits.ElemFixedBitSize+import HaskellWorks.Data.Bits.PopCount.PopCount1+import HaskellWorks.Data.Positioning+import Prelude as P +import qualified Data.Vector as DV+import qualified Data.Vector.Storable as DVS+ {-# ANN module ("HLint: Ignore Reduce duplication" :: String) #-} class Rank1 v where@@ -26,60 +26,28 @@ deriving instance Rank1 a => Rank1 (BitShown a) instance Rank1 Word8 where- rank1 _ 0 = 0- rank1 v s0 =- -- Shift out bits after given position.- let r0 = v .<. (8 - s0) in- -- Count set bits in parallel.- let r1 = (r0 .&. 0x55) + ((r0 .>. 1) .&. 0x55) in- let r2 = (r1 .&. 0x33) + ((r1 .>. 2) .&. 0x33) in- let r3 = (r2 .&. 0x0f) + ((r2 .>. 4) .&. 0x0f) in- let r4 = r3 `mod` 255 in- widen64 r4+ rank1 _ 0 = 0+ rank1 v i = popCount1 (v .&. ((1 .<. fromIntegral i) - 1)) {-# INLINABLE rank1 #-} instance Rank1 Word16 where- rank1 _ 0 = 0- rank1 v s0 =- -- Shift out bits after given position.- let r0 = v .<. (16 - s0) in- -- Count set bits in parallel.- let r1 = (r0 .&. 0x5555) + ((r0 .>. 1) .&. 0x5555) in- let r2 = (r1 .&. 0x3333) + ((r1 .>. 2) .&. 0x3333) in- let r3 = (r2 .&. 0x0f0f) + ((r2 .>. 4) .&. 0x0f0f) in- let r4 = r3 `mod` 255 in- widen64 r4+ rank1 _ 0 = 0+ rank1 v i = popCount1 (v .&. ((1 .<. fromIntegral i) - 1)) {-# INLINABLE rank1 #-} instance Rank1 Word32 where- rank1 _ 0 = 0- rank1 v s0 =- -- Shift out bits after given position.- let r0 = v .<. (32 - s0) in- -- Count set bits in parallel.- let r1 = (r0 .&. 0x55555555) + ((r0 .>. 1) .&. 0x55555555) in- let r2 = (r1 .&. 0x33333333) + ((r1 .>. 2) .&. 0x33333333) in- let r3 = (r2 .&. 0x0f0f0f0f) + ((r2 .>. 4) .&. 0x0f0f0f0f) in- let r4 = r3 `mod` 255 in- widen64 r4+ rank1 _ 0 = 0+ rank1 v i = popCount1 (v .&. ((1 .<. fromIntegral i) - 1)) {-# INLINABLE rank1 #-} instance Rank1 Word64 where- rank1 _ 0 = 0- rank1 v s0 =- -- Shift out bits after given position.- let r0 = v .<. (64 - s0) in- -- Count set bits in parallel.- let r1 = (r0 .&. 0x5555555555555555) + ((r0 .>. 1) .&. 0x5555555555555555) in- let r2 = (r1 .&. 0x3333333333333333) + ((r1 .>. 2) .&. 0x3333333333333333) in- let r3 = (r2 .&. 0x0f0f0f0f0f0f0f0f) + ((r2 .>. 4) .&. 0x0f0f0f0f0f0f0f0f) in- let r4 = r3 `mod` 255 in- r4+ rank1 _ 0 = 0+ rank1 v i = popCount1 (v .&. ((1 .<. fromIntegral i) - 1)) {-# INLINABLE rank1 #-} instance Rank1 [Bool] where rank1 = go 0- where go r _ 0 = r+ where go r _ 0 = r go r (True :bs) p = go (r + 1) bs (p - 1) go r (False:bs) p = go r bs (p - 1) go _ [] _ = error "Out of range"