.map() function

[ppiotrow]

I'd like to implement .map(IntToIntFunction f) that returns new RoaringBitmap as a result of mapping. Example:

RoaringBitmap r1 = RoaringBitmap.bitmapOf(1, 3, 6, 8, 9, 14)
RoaringBitmap r2 = r1.map(i -> (i*7)%13)
r2 // {7, 8, 3, 4, 11}

I would like to gather ideas how to solve problem with performance of inserting new values in non-ordered way.

Currently I can see that using java.util.BitSet as a temporary buffer gives me speed-up 6x. I assume it is because of skipping binary-search part.

public class Main {
  public static void main(String[] args) {
    RoaringBitmap b = new RoaringBitmap();
    Random r = new Random(1333);
    for (int i = 0; i < 120_000_000; i++) {
      b.add(r.nextInt(200_000_000));
    }
    b.runOptimize();

    for (int i = 0; i < 100; i++) { //naive benchmark
      Instant s = Instant.now();
      //RoaringBitmap res = new RoaringBitmap();
      BitSet altRes = new java.util.BitSet(77_333_333);
      b.forEach((IntConsumer) value -> altRes.set((value * 3) % 77_333_333));
      RoaringBitmap altResAsBitmap = BitSetUtil.bitmapOf(altRes);
      Instant e = Instant.now();
      System.out.println("res:" + altResAsBitmap.getCardinality() + " time: " + Duration.between(s, e).toMillis());
    }
  }
}

[lemire]

I have added a test called MapBenchmark to our jmh package. Here is what I get on my laptop...

cd jmh
./run.sh MapBenchmark
MapBenchmark.testMap           avgt    5  2870.069 ± 260.340  us/op
MapBenchmark.testMapViaBitset  avgt    5  6426.931 ± 883.076  us/op

Reference : https://github.com/RoaringBitmap/RoaringBitmap/blob/master/jmh/src/main/java/org/roaringbitmap/map/MapBenchmark.java

One point to note, if you set randomly about half the bits to true and half the bits to false, then it makes no sense to use a RoaringBitmap. It is a scenario where a pure BitSet is far superior to anything else. So in my test I am benchmarking something where there are long runs of missing values, and long runs of continuous values.

In an ideal world, we would have a benchmark that is representative of a real-world test. Given such a benchmark, then we may ask whether there is some way to optimize a map computation. But I'd recommend first agreeing on what the benchmark should be. It could be what I am proposing, but I submit to your that it cannot be your chosen benchmark.

[Kineolyan]

@lemire could you remind (me|us) the scenarios where RoaringBitmap outshine other bitmap implentations ? And when it is just as good as other more basic solutions ? Thanks a lot

[lemire]

could you remind (me|us) the scenarios where RoaringBitmap outshine other bitmap implentations?

Here are two freely available papers that cover this topic...

• Jianguo Wang, Chunbin Lin, Yannis Papakonstantinou, Steven Swanson, An Experimental Study of Bitmap Compression vs. Inverted List Compression, SIGMOD 2017, 2017.
• Daniel Lemire, Gregory Ssi-Yan-Kai, Owen Kaser, Consistently faster and smaller compressed bitmaps with Roaring, Software: Practice and Experience 46 (11), pages 1547-1569, November 2016.

For other references, please see...

http://roaringbitmap.org/publications/

And when it is just as good as other more basic solutions?

Choosing the best data structure is highly non-trivial. It depends on your application, your data, and so forth. People often come up with recipes, but they can be terribly wrong. So the best strategy is to try things out with your actual problems. Of course, sometimes this is too much work, so you must simulate your use case... but I would encourage you to simulate with real data as much as possible.

Here is an important point: it is ridiculously hard to simulate real data using simple code. You'd think that you can just use random numbers and that will be all... but real data is often quite far from random.

So using real data is a must if you care about a real problem.

Now... that's not to say that synthetic benchmarks cannot be instructive. They can. But one should be cautious about what can be concluded from them.

[ppiotrow]

@lemire I agree that the right benchmarks need to be added before actual work. In the meantime I can point what is wrong with newly added benchmark. In add bits to the new bitmap in-ordered way. To change that one can use such function (-20*x+700_000_000) % 77_333_333. This will make BitSets works 2x faster. IMHO it is caused by extensive binary search usage by Roaring. If BitSet would be preallocated to 73M then it is 3x faster than Roaring.

My ideas for map function would be to:

1. use lazy approach before mapped bitmap is created,
2. try to order Containers in RoaringArray it the way that is is easier O(1) to find them during the mapping.

[lemire]

@ppiotrow I think we will be glad to receive a PR on this... especially if it is accompanied with good benchmarking and unit testing.