/gopherconrussia2019

Accompanying code for Gophercon Russia 2019 talk about Bitmap Indexes

Primary LanguageGo

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