richardstartin commented on issue #6764: Consider using RoaringBitmapWriter for bitmap construction URL: https://github.com/apache/incubator-druid/pull/6764#issuecomment-450848581 In fact, here's a benchmark to isolate the construction time from the iteration time: ```java @Benchmark public Object construct(ConstructAndIterState state) { int dataSize = state.dataSize; int[] data = state.data; MutableBitmap mutableBitmap = factory.makeEmptyMutableBitmap(); for (int i = 0; i < dataSize; i++) { mutableBitmap.add(data[i]); } return factory.makeImmutableBitmap(mutableBitmap); } ``` and at `114a9fc38feda5f85799d24889007bc572d04dea` (master) I get ``` Benchmark (bitmapAlgo) (prob) (size) Mode Cnt Score Error Units BitmapIterationBenchmark.construct roaring 0.0 1000000 avgt 5 124.236 ± 6.597 ns/op BitmapIterationBenchmark.construct roaring 0.001 1000000 avgt 5 14045.045 ± 1026.400 ns/op BitmapIterationBenchmark.construct roaring 0.1 1000000 avgt 5 1317274.340 ± 153275.511 ns/op BitmapIterationBenchmark.construct roaring 0.5 1000000 avgt 5 7415001.388 ± 377532.457 ns/op BitmapIterationBenchmark.construct roaring 0.99 1000000 avgt 5 10687372.213 ± 860813.095 ns/op BitmapIterationBenchmark.construct roaring 1.0 1000000 avgt 5 10790794.579 ± 961663.105 ns/op ``` And at `1afb602de27d31367440b1cccc86ec799c59dc4c` (this PR) I get: ``` Benchmark (bitmapAlgo) (prob) (size) Mode Cnt Score Error Units BitmapIterationBenchmark.construct roaring 0.0 1000000 avgt 5 187.924 ± 12.126 ns/op BitmapIterationBenchmark.construct roaring 0.001 1000000 avgt 5 12674.625 ± 267.506 ns/op BitmapIterationBenchmark.construct roaring 0.1 1000000 avgt 5 868981.551 ± 21139.938 ns/op BitmapIterationBenchmark.construct roaring 0.5 1000000 avgt 5 3391372.332 ± 86345.168 ns/op BitmapIterationBenchmark.construct roaring 0.99 1000000 avgt 5 7314761.225 ± 335907.952 ns/op BitmapIterationBenchmark.construct roaring 1.0 1000000 avgt 5 7147180.460 ± 107730.956 ns/op ``` So there's a good boost to be had from avoiding the binary searches, and it sounds like druid does write its bitmaps in an ordered fashion.
---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: [email protected] With regards, Apache Git Services --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
