Accompanying code for Gophercon Russia 2019 talk about Bitmap Indexes

Slides

Gophercon Russia 2019 -> PDF

Code structure

| Directory | Description | | ----------- | -------------------------------------------------------- | | simple | Simple implementation for a Bitmap Index in Go. | | biggerbatch | Similar to previous one, but using 64 bit batches. | | simplesimd | Implementation in assembly for scalar and SIMD versions. | | roar | Implementation using roaring bitmaps Go modules. | | pilosa | Implementation using pilosa DB. |

Simple

name                                         time/op
SimpleBitmapIndex-12                         10.8µs ± 0%
SimpleBitmapIndexInlined-12                  8.88µs ± 0%
SimpleBitmapIndexInlinedAndNoBoundsCheck-12  8.33µs ± 0%

Biggerbatch

name                                              time/op
BiggerBatchBitmapIndex-12                         1.18µs ± 0%
BiggerBatchBitmapIndexInlined-12                  1.31µs ± 0%
BiggerBatchBitmapIndexNoBoundsCheck-12            1.06µs ± 0%
BiggerBatchBitmapIndexInlinedAndNoBoundsCheck-12  1.12µs ± 0%

Simplesimd

name                              time/op
SimpleSIMDBitmapIndex-12           160ns ± 0%
SimpleScalarFasterBitmapIndex-12  1.06µs ± 1%
SimpleScalarBitmapIndex-12        1.24µs ± 0%

Roaring bitmaps

name                   time/op
RoaringBitmapIndex-8   10.9µs ±17%
CRoaringBitmapIndex-8  10.6µs ±16%

name                   alloc/op
RoaringBitmapIndex-8   13.2kB ± 1%
CRoaringBitmapIndex-8   16.0B ± 0%

name                   allocs/op
RoaringBitmapIndex-8     12.0 ± 0%
CRoaringBitmapIndex-8    2.00 ± 0%

Pilosa

1. Download and run the pilosa
2. Run the provided program

   $ go run pilosa.go
   2019/03/30 20:41:12 filling the data...
   2019/03/30 20:41:47 finished filling the data
   2019/03/30 20:41:47 got 2796 columns