hw-rankselect-base: Rank-select base

[ bsd3, data, library ] [ Propose Tags ]

Please see README.md


[Skip to Readme]
Versions 0.0.0.1, 0.1.0.0, 0.2.0.0, 0.2.0.1, 0.2.0.2, 0.3.0.0, 0.3.1.0, 0.3.2.0, 0.3.2.1
Dependencies 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.*) [details]
License BSD-3-Clause
Copyright 2016 John Ky
Author John Ky
Maintainer newhoggy@gmail.com
Category Data
Home page http://github.com/haskell-works/hw-rankselect-base#readme
Bug tracker https://github.com/haskell-works/hw-rankselect-base/issues
Source repo head: git clone https://github.com/haskell-works/hw-rankselect-base
Uploaded by haskellworks at Sat Aug 4 21:37:24 UTC 2018
Distributions LTSHaskell:0.3.2.1, NixOS:0.3.2.1, Stackage:0.3.2.1
Downloads 1286 total (77 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs available [build log]
Last success reported on 2018-08-04 [all 1 reports]
Hackage Matrix CI

Modules

[Index] [Quick Jump]

Flags

NameDescriptionDefaultType
bmi2

Enable bmi2 instruction set

DisabledAutomatic

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

Downloads

Maintainer's Corner

For package maintainers and hackage trustees


Readme for hw-rankselect-base-0.3.2.1

[back to package description]

hw-rankselect-base

CircleCI

Rank and select operations.

This library will use support for some BMI2 CPU instructions on some x86 based CPUs if compiled with the appropriate flags on ghc-8.4.1 or later.

Rank and select

This library provides the following functions on various types:

  • rank1
  • rank0
  • select1
  • select0

Type class instances are provided for the following primitive types:

  • Bool
  • Word8
  • Word16
  • Word32
  • Word64

Moreover additional type class instances are provided for [], Vector 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.

Bit-vectors larger than 64-bits need indexing to achieve higher performance. A indexed bit-vector implementation can found in the hw-rankselect package.

Notes

This library follows standard 1-based counting conventions typically found in Computer Science literature where select1 10 2 = 4 as illustrated here:

  8 7 6 5  [4]3 2 1
  0 0 0 0   1 0 1 0

The standard convention for the bmi2 implementation, comes at a small cost.

An internal function select1Word64Bmi2Base0 demonstrates 0-based counting that is slightly faster when implemented with the bmi2 instruction set where select1 10 1 = 3 as illustrated here:

  7 6 5 4  [3]2 1 0
  0 0 0 0   1 0 1 0

Compilation

It is sufficient to build, test and benchmark the library as follows for emulated behaviour:

stack build
stack test
stack bench

To target the BMI2 instruction set, add the bmi2 flag:

stack build --flag bits-extra:bmi2 --flag hw-rankselect-base:bmi2
stack test  --flag bits-extra:bmi2 --flag hw-rankselect-base:bmi2
stack bench --flag bits-extra:bmi2 --flag hw-rankselect-base:bmi2

Benchmark results

The following benchmark shows the kinds of performance gain that can be expected from enabling the BMI2 instruction set for CPU targets that support them:

benchmarking 64-bit/Once: Select1 Broadword
time                 14.75 ns   (14.63 ns .. 14.90 ns)
                     0.996 R²   (0.987 R² .. 0.999 R²)
mean                 15.35 ns   (14.92 ns .. 16.70 ns)
std dev              2.355 ns   (607.2 ps .. 4.849 ns)
variance introduced by outliers: 96% (severely inflated)

benchmarking 64-bit/Once: Select1 Bmi2
time                 6.026 ns   (5.933 ns .. 6.134 ns)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 6.024 ns   (5.966 ns .. 6.096 ns)
std dev              224.4 ps   (176.9 ps .. 318.6 ps)
variance introduced by outliers: 62% (severely inflated)

benchmarking 32-bit/Once: Select1 Broadword
time                 26.09 ns   (25.84 ns .. 26.40 ns)
                     0.999 R²   (0.998 R² .. 0.999 R²)
mean                 26.67 ns   (26.37 ns .. 27.01 ns)
std dev              1.017 ns   (848.4 ps .. 1.291 ns)
variance introduced by outliers: 61% (severely inflated)

benchmarking 32-bit/Once: Select1 Bmi2
time                 8.613 ns   (8.543 ns .. 8.687 ns)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 8.592 ns   (8.515 ns .. 8.671 ns)
std dev              248.3 ps   (216.2 ps .. 294.8 ps)
variance introduced by outliers: 48% (moderately inflated)