RoaringBitmap.andNot does not produce optimal containers

[richardstartin]

Performing andNot on a large contiguous bitmap and a sparse bitmap does not produce run optimised bitmaps when it could, which inflates size:

    RoaringBitmap existence = new RoaringBitmap();
    existence.add(0L, 1_000_000L);
    printContainerStats(existence);
    RoaringBitmap sparse = new RoaringBitmap();
    for (int i = 0; i < 8000; ++i) {
      sparse.add(i * 125);
    }
    existence.andNot(sparse);
    printContainerStats(existence);
    existence.runOptimize();
    printContainerStats(existence);

This prints:

containers: 16x RunContainer, serialized size: 230, size:168
containers: 16x BitmapContainer, serialized size: 131208, size:131112
containers: 16x RunContainer, serialized size: 32226, size:32164

However, this leads to a seemingly spurious space/time tradeoff, because run optimisation slows subsequent intersections down, so I expect intersections with run containers could be improved:

@State(Scope.Benchmark)
public class AndNotBenchmark {

  @Param("1000000")
  private long size;

  @Param({"true", "false"})
  boolean runOptimise;

  private RoaringBitmap contiguous;
  private RoaringBitmap sparse;
  private RoaringBitmap combined;
  private RoaringBitmap otherSparse;

  @Setup(Level.Trial)
  public void setup() {
    contiguous = new RoaringBitmap();
    contiguous.add(0L, size);
    sparse = new RoaringBitmap();
    for (int i = 0; i < size; i += 125) {
      sparse.add(i);
    }
    combined = contiguous.clone();
    combined.andNot(sparse);
    otherSparse = new RoaringBitmap();
    for (int i = 1; i < size; i += 125) {
      otherSparse.add(i);
    }
    if (runOptimise) {
      combined.runOptimize();
    }
  }

  @Benchmark
  public RoaringBitmap andSparse() {
    return RoaringBitmap.and(combined, otherSparse);
  }

  @Benchmark
  public RoaringBitmap andContiguous() {
    return RoaringBitmap.and(combined, contiguous);
  }
}

Benchmark                      (runOptimise)   (size)  Mode  Cnt   Score   Error  Units
AndNotBenchmark.andContiguous           true  1000000  avgt    5  57.054 ± 0.030  us/op
AndNotBenchmark.andContiguous          false  1000000  avgt    5  20.811 ± 0.065  us/op
AndNotBenchmark.andSparse               true  1000000  avgt    5  39.442 ± 0.408  us/op
AndNotBenchmark.andSparse              false  1000000  avgt    5  20.641 ± 0.280  us/op