(lucene) branch branch_10x updated: Add small bias towards bit set encoding. (#14155)

[jp...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

jpountz pushed a commit to branch branch_10x
in repository https://gitbox.apache.org/repos/asf/lucene.git


The following commit(s) were added to refs/heads/branch_10x by this push:
     new 4b270750eba Add small bias towards bit set encoding. (#14155)
4b270750eba is described below

commit 4b270750eba2b9cf89f4462123e07a766044f6bb
Author: Adrien Grand <jp...@gmail.com>
AuthorDate: Thu Jan 23 14:40:03 2025 +0100

    Add small bias towards bit set encoding. (#14155)
    
    Currently, blocks of postings get encoded as a bit set instead of packed deltas
    (FOR) whenever the bit set is more storage-efficient. However, the bit set
    approach is quite more CPU-efficient at search time, so this PR introduces a
    small bias towards the bit set encoding by using it as soon as it's more
    storage-efficient than FOR with the next number of bits per value.
    
    The impact on storage efficiency of the Wikipedia dataset is negligible (+0.15%
    on `.doc` files, while `.doc` files don't dominate storage requirements,
    positions do) while some queries get a good speedup.
---
 .../codecs/lucene101/Lucene101PostingsWriter.java       | 17 +++++++++--------
 1 file changed, 9 insertions(+), 8 deletions(-)

diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene101/Lucene101PostingsWriter.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene101/Lucene101PostingsWriter.java
index 1cabefe681e..3d19a69b82d 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene101/Lucene101PostingsWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene101/Lucene101PostingsWriter.java
@@ -424,15 +424,17 @@ public class Lucene101PostingsWriter extends PushPostingsWriterBase {
       long numSkipBytes = level0Output.size();
       // Now we need to decide whether to encode block deltas as packed integers (FOR) or unary
       // codes (bit set). FOR makes #nextDoc() a bit faster while the bit set approach makes
-      // #advance() sometimes faster and #intoBitSet() much faster. Since the trade-off is not
-      // obvious, we make the decision purely based on storage efficiency, using the approach that
-      // requires fewer bits to encode the block.
+      // #advance() usually faster and #intoBitSet() much faster. In the end, we make the decision
+      // based on storage requirements, picking the bit set approach whenever it's more
+      // storage-efficient than the next number of bits per value (which effectively slightly biases
+      // towards the bit set approach).
       int bitsPerValue = forDeltaUtil.bitsRequired(docDeltaBuffer);
       int sum = Math.toIntExact(Arrays.stream(docDeltaBuffer).sum());
       int numBitSetLongs = FixedBitSet.bits2words(sum);
+      int numBitsNextBitsPerValue = Math.min(Integer.SIZE, bitsPerValue + 1) * BLOCK_SIZE;
       if (sum == BLOCK_SIZE) {
         level0Output.writeByte((byte) 0);
-      } else if (version < VERSION_DENSE_BLOCKS_AS_BITSETS || bitsPerValue * BLOCK_SIZE < sum) {
+      } else if (version < VERSION_DENSE_BLOCKS_AS_BITSETS || numBitsNextBitsPerValue <= sum) {
         level0Output.writeByte((byte) bitsPerValue);
         forDeltaUtil.encodeDeltas(bitsPerValue, docDeltaBuffer, level0Output);
       } else {
@@ -444,10 +446,9 @@ public class Lucene101PostingsWriter extends PushPostingsWriterBase {
           s += i;
           spareBitSet.set(s);
         }
-        // Since we use the bit set encoding when it's more storage efficient than storing deltas,
-        // we know that each doc ID uses less than 32 bits, the maximum number of bits required to
-        // store a delta between consecutive doc IDs. So in the end, the bit set cannot have more
-        // than BLOCK_SIZE * Integer.SIZE / Long.SIZE = 64 longs, which fits on a byte.
+        // We never use the bit set encoding when it requires more than Integer.SIZE=32 bits per
+        // value. So the bit set cannot have more than BLOCK_SIZE * Integer.SIZE / Long.SIZE = 64
+        // longs, which fits on a byte.
         assert numBitSetLongs <= BLOCK_SIZE / 2;
         level0Output.writeByte((byte) -numBitSetLongs);
         for (int i = 0; i < numBitSetLongs; ++i) {