I can believe that FixedBitSet is faster in some cases, but it's surprising to me that the memory usage of SparseFixedBitSet can go up to 2x that of FixedBitSet, this makes me wonder if SparseFixedBitSet#ramBytesUsed is buggy. A SparseFixedBitSet that has all its bits set (worst-case scenario for memory usage) has an overhead of one long, one object reference and and one array every 4096 bits = 64 longs, which doesn't feel to me it should ever use 2x more heap?

Separately, I wonder if you know the number of nodes that get visited (ie. the number of bits that end up being set) in your benchmark? Is it a force-merged index or do you have multiple segments?

@jpountz I re-ran my tests and double checked my numbers, I have some corrections, I accidentally double-counted sparse sizes, so previous numbers are 2x too big.

GLOVE-100-100_000:
sparse_total_usage: 10644328
fixed_total_usage: 12544000
num_nodes_visited_avg: 3561
num_nodes_visited_min: 1971
num_nodes_visited_max: 6904

Cohere-768-400_000:
sparse_total_usage: 51991232
fixed_total_usage: 50040000
num_nodes_visited_avg: 12324
num_nodes_visited_min: 3213
num_nodes_visited_max: 19979

EDIT:

@jpountz to confirm the sparse fixed bitset memory usage, I rewrote the ramBytesUsed to be more exact (instead of summing up the estimation).

  @Override
  public long ramBytesUsed() {
    long bytesUsed = BASE_RAM_BYTES_USED;
    bytesUsed += RamUsageEstimator.sizeOf(indices);
    bytesUsed += RamUsageEstimator.shallowSizeOf(bits);
    for (long[] bitArray : bits) {
      if (bitArray != null) {
        bytesUsed += RamUsageEstimator.sizeOf(bitArray);
      }
    }
    return bytesUsed;
  }

Obviously, this ran slightly slower, but from what I found, this didn't reduce the memory estimation. I still got 51991232

Thanks, the numbers make more sense to me now.

Intuitively, FixedBitSet performs better when a large percentage of nodes needs to be visited and SparseFixedBitSet performs better otherwise. Practically, the smaller segments of an index should probably always use a FixedBitSet. E.g. a simple threshold may consist of using SparseFixedBitSet when we would expect it to use less memory than FixedBitSet, ie. when less than 1/64 = 1.5% of the nodes get visited (or possibly a bit less: if both SparseFixedBitSet and FixedBitSet use similar amounts of memory, it probably makes sense to bias towards FixedBitSet) and FixedBitSet otherwise. I see that your benchmark visits between 2.0% and 6.9% of the nodes on GLOVE and between 0.8% and 5.0% on Cohere, so it makes sense to me that FixedBitSet performs better.

Is it possible to estimate the order of the number of nodes that a nn search needs to visit, so that we could use it as a threshold?

@jpountz searching scales logarithmically, but we do have to explore more if there are any pre-filtered nodes.

We can run some experiments to determine the appropriate threshold. I imagine it will be something along the lines of topK * log(graphSize) with some constant scaling applied.

++ This feels similar to IndexOrDocValuesQuery: we probably can't guess the absolute best threshold, but we can probably figure out something that is right more often than wrong. Hopefully we can keep it simple and not include maxConn and other parameters in the equation.