Skip to content
Accompanying code for Gophercon Russia 2019 talk about Bitmap Indexes
Branch: master
Clone or download
Latest commit 235b8b0 Apr 11, 2019
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
biggerbatch changes Apr 8, 2019
pilosa added pilosa example Mar 30, 2019
roar added bench results Mar 31, 2019
simple changes Apr 8, 2019
simplesimd changes Apr 8, 2019
.gitignore add scalar asm version Mar 17, 2019
GopherconRussia2019.pdf fix slides Apr 11, 2019
README.md fix slides Apr 11, 2019
go.mod added pilosa example Mar 30, 2019
go.sum added pilosa example Mar 30, 2019

README.md

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
    
You can’t perform that action at this time.