You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by us...@apache.org on 2025/08/29 14:53:45 UTC
(lucene) branch branch_10x updated: Backport of #15116: Rewrite of the GroupVInt optimization without lambdas, varhandles and no code in subclasses (#15138)
This is an automated email from the ASF dual-hosted git repository.
uschindler 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 62456110f2c Backport of #15116: Rewrite of the GroupVInt optimization without lambdas, varhandles and no code in subclasses (#15138)
62456110f2c is described below
commit 62456110f2c1676ea51ee774ab2af9c592683ad8
Author: Uwe Schindler <us...@apache.org>
AuthorDate: Fri Aug 29 16:53:39 2025 +0200
Backport of #15116: Rewrite of the GroupVInt optimization without lambdas, varhandles and no code in subclasses (#15138)
* Backport of:
Revision: ebfd863ac728f9abfcaa42fec7fce90b62900df5
Author: Uwe Schindler <us...@apache.org>
Date: 25.08.2025 22:58:28
Message:
Rewrite of the GroupVInt optimization without lambdas, varhandles and no code in subclasses (#15116)
* Rewrite of the GroupVInt optimization without lamdas, varhandles and no code in subclasses
* Remove optimized flag and duplicate code
* apply suggestions/fixes: fix maximum size; cleanup baseline method and hide internal details
* Apply suggestions from code review
Co-authored-by: Adrien Grand <jp...@gmail.com>
* add CHANGES.txt
* more docs and a visibility change for previously public method
---------
Co-authored-by: Adrien Grand <jp...@gmail.com>
---
lucene/CHANGES.txt | 5 +
.../lucene/benchmark/jmh/GroupVIntBenchmark.java | 33 +++----
.../apache/lucene/store/BufferedIndexInput.java | 11 ---
.../apache/lucene/store/ByteBuffersDataInput.java | 20 ----
.../apache/lucene/store/ByteBuffersIndexInput.java | 6 --
.../java/org/apache/lucene/store/DataInput.java | 13 ++-
.../java/org/apache/lucene/util/GroupVIntUtil.java | 104 ++++++++++++++-------
.../lucene/store/MemorySegmentIndexInput.java | 18 ----
8 files changed, 95 insertions(+), 115 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 84dd7462113..25942bd3b18 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -168,6 +168,11 @@ Optimizations
* GITHUB#15045: Use FixedBitSet#cardinality for counting liveDocs in CheckIndex (Zhang Chao)
+* GITHUB#15116, GITHUB#15138: Rewrite of the GroupVInt optimization without lambdas, varhandles
+ and no code in subclasses. The optimization now auto-detects if an IndexInput supports random access
+ and uses an optimized branchless approach. Any subclasses that have implemented the optimized method
+ need to remove it as it will disappear in Lucene 11. (Uwe Schindler)
+
Changes in Runtime Behavior
---------------------
* GITHUB#14823: Decrease TieredMergePolicy's default number of segments per
diff --git a/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/GroupVIntBenchmark.java b/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/GroupVIntBenchmark.java
index 6b40870c375..2b41fa262e3 100644
--- a/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/GroupVIntBenchmark.java
+++ b/lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/GroupVIntBenchmark.java
@@ -23,9 +23,8 @@ import java.util.Random;
import java.util.concurrent.TimeUnit;
import org.apache.lucene.store.ByteArrayDataInput;
import org.apache.lucene.store.ByteArrayDataOutput;
-import org.apache.lucene.store.ByteBuffersDataInput;
import org.apache.lucene.store.ByteBuffersDataOutput;
-import org.apache.lucene.store.DataInput;
+import org.apache.lucene.store.ByteBuffersDirectory;
import org.apache.lucene.store.Directory;
import org.apache.lucene.store.IOContext;
import org.apache.lucene.store.IndexInput;
@@ -50,8 +49,8 @@ import org.openjdk.jmh.infra.Blackhole;
@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@State(Scope.Benchmark)
-@Warmup(iterations = 3, time = 3)
-@Measurement(iterations = 5, time = 5)
+@Warmup(iterations = 4, time = 8)
+@Measurement(iterations = 5, time = 20)
@Fork(
value = 1,
jvmArgsPrepend = {"--add-modules=jdk.unsupported"})
@@ -92,7 +91,7 @@ public class GroupVIntBenchmark {
IndexInput mmapGVIntIn;
IndexInput nioGVIntIn;
IndexInput mmapVIntIn;
- ByteBuffersDataInput byteBuffersGVIntIn;
+ IndexInput byteBuffersGVIntIn;
ByteArrayDataInput byteArrayVIntIn;
ByteArrayDataInput byteArrayGVIntIn;
@@ -125,9 +124,11 @@ public class GroupVIntBenchmark {
}
void initByteBuffersInput(int[] docs) throws Exception {
- ByteBuffersDataOutput buffer = new ByteBuffersDataOutput();
- buffer.writeGroupVInts(docs, docs.length);
- byteBuffersGVIntIn = buffer.toDataInput();
+ Directory dir = new ByteBuffersDirectory();
+ IndexOutput out = dir.createOutput("gvint", IOContext.DEFAULT);
+ out.writeGroupVInts(docs, docs.length);
+ out.close();
+ byteBuffersGVIntIn = dir.openInput("gvint", IOContext.DEFAULT);
}
void initMMapInput(int[] docs) throws Exception {
@@ -145,16 +146,6 @@ public class GroupVIntBenchmark {
mmapVIntIn = dir.openInput("vint", IOContext.DEFAULT);
}
- private void readGroupVIntsBaseline(DataInput in, int[] dst, int limit) throws IOException {
- int i;
- for (i = 0; i <= limit - 4; i += 4) {
- GroupVIntUtil.readGroupVInt(in, dst, i);
- }
- for (; i < limit; ++i) {
- dst[i] = in.readVInt();
- }
- }
-
@Setup(Level.Trial)
public void init() throws Exception {
Random r = new Random(0);
@@ -193,7 +184,7 @@ public class GroupVIntBenchmark {
@Benchmark
public void benchMMapDirectoryInputs_readGroupVIntBaseline(Blackhole bh) throws IOException {
mmapGVIntIn.seek(0);
- this.readGroupVIntsBaseline(mmapGVIntIn, values, size);
+ GroupVIntUtil.readGroupVInts$Baseline(mmapGVIntIn, values, size);
bh.consume(values);
}
@@ -223,7 +214,7 @@ public class GroupVIntBenchmark {
@Benchmark
public void benchNIOFSDirectoryInputs_readGroupVIntBaseline(Blackhole bh) throws IOException {
nioGVIntIn.seek(0);
- this.readGroupVIntsBaseline(nioGVIntIn, values, size);
+ GroupVIntUtil.readGroupVInts$Baseline(nioGVIntIn, values, size);
bh.consume(values);
}
@@ -237,7 +228,7 @@ public class GroupVIntBenchmark {
@Benchmark
public void benchByteBuffersIndexInput_readGroupVIntBaseline(Blackhole bh) throws IOException {
byteBuffersGVIntIn.seek(0);
- this.readGroupVIntsBaseline(byteBuffersGVIntIn, values, size);
+ GroupVIntUtil.readGroupVInts$Baseline(byteBuffersGVIntIn, values, size);
bh.consume(values);
}
diff --git a/lucene/core/src/java/org/apache/lucene/store/BufferedIndexInput.java b/lucene/core/src/java/org/apache/lucene/store/BufferedIndexInput.java
index cd47500a2df..6ac73d78d29 100644
--- a/lucene/core/src/java/org/apache/lucene/store/BufferedIndexInput.java
+++ b/lucene/core/src/java/org/apache/lucene/store/BufferedIndexInput.java
@@ -20,7 +20,6 @@ import java.io.EOFException;
import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
-import org.apache.lucene.util.GroupVIntUtil;
/** Base implementation class for buffered {@link IndexInput}. */
public abstract class BufferedIndexInput extends IndexInput implements RandomAccessInput {
@@ -150,16 +149,6 @@ public abstract class BufferedIndexInput extends IndexInput implements RandomAcc
}
}
- @Override
- public void readGroupVInt(int[] dst, int offset) throws IOException {
- final int len =
- GroupVIntUtil.readGroupVInt(
- this, buffer.remaining(), p -> buffer.getInt((int) p), buffer.position(), dst, offset);
- if (len > 0) {
- buffer.position(buffer.position() + len);
- }
- }
-
@Override
public final long readLong() throws IOException {
if (Long.BYTES <= buffer.remaining()) {
diff --git a/lucene/core/src/java/org/apache/lucene/store/ByteBuffersDataInput.java b/lucene/core/src/java/org/apache/lucene/store/ByteBuffersDataInput.java
index dee5c8e3a73..3213ee373e5 100644
--- a/lucene/core/src/java/org/apache/lucene/store/ByteBuffersDataInput.java
+++ b/lucene/core/src/java/org/apache/lucene/store/ByteBuffersDataInput.java
@@ -29,7 +29,6 @@ import java.util.List;
import java.util.Locale;
import java.util.stream.Collectors;
import org.apache.lucene.util.Accountable;
-import org.apache.lucene.util.GroupVIntUtil;
import org.apache.lucene.util.RamUsageEstimator;
/**
@@ -203,25 +202,6 @@ public final class ByteBuffersDataInput extends DataInput
}
}
- @Override
- public void readGroupVInt(int[] dst, int offset) throws IOException {
- final ByteBuffer block = blocks[blockIndex(pos)];
- final int blockOffset = blockOffset(pos);
- // We MUST save the return value to local variable, could not use pos += readGroupVInt(...).
- // because `pos +=` in java will move current value(not address) of pos to register first,
- // then call the function, but we will update pos value in function via readByte(), then
- // `pos +=` will use an old pos value plus return value, thereby missing 1 byte.
- final int len =
- GroupVIntUtil.readGroupVInt(
- this,
- block.limit() - blockOffset,
- p -> block.getInt((int) p),
- blockOffset,
- dst,
- offset);
- pos += len;
- }
-
@Override
public long length() {
return length;
diff --git a/lucene/core/src/java/org/apache/lucene/store/ByteBuffersIndexInput.java b/lucene/core/src/java/org/apache/lucene/store/ByteBuffersIndexInput.java
index 959f429ecfc..839636e7ed7 100644
--- a/lucene/core/src/java/org/apache/lucene/store/ByteBuffersIndexInput.java
+++ b/lucene/core/src/java/org/apache/lucene/store/ByteBuffersIndexInput.java
@@ -205,12 +205,6 @@ public final class ByteBuffersIndexInput extends IndexInput implements RandomAcc
in.readLongs(dst, offset, length);
}
- @Override
- public void readGroupVInt(int[] dst, int offset) throws IOException {
- ensureOpen();
- in.readGroupVInt(dst, offset);
- }
-
@Override
public IndexInput clone() {
ensureOpen();
diff --git a/lucene/core/src/java/org/apache/lucene/store/DataInput.java b/lucene/core/src/java/org/apache/lucene/store/DataInput.java
index 369b631426b..1ec937c2594 100644
--- a/lucene/core/src/java/org/apache/lucene/store/DataInput.java
+++ b/lucene/core/src/java/org/apache/lucene/store/DataInput.java
@@ -27,7 +27,6 @@ import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;
import org.apache.lucene.util.BitUtil;
-import org.apache.lucene.util.GroupVIntUtil;
/**
* Abstract base class for performing read operations of Lucene's low-level data types.
@@ -100,13 +99,19 @@ public abstract class DataInput implements Cloneable {
}
/**
- * Override if you have an efficient implementation. In general this is when the input supports
- * random access.
+ * Legacy: This method allowed to implement GroupVInt encoding in a more efficient way when this
+ * implementation supports random access. It is no longer called by Lucene's code.
*
+ * <p>If you have implemented this method, simply remove it!
+ *
+ * @throws UnsupportedOperationException (always)
* @lucene.experimental
+ * @deprecated This method is no longer called. It is only kept for backwards compatibility
*/
+ @Deprecated
public void readGroupVInt(int[] dst, int offset) throws IOException {
- GroupVIntUtil.readGroupVInt(this, dst, offset);
+ throw new UnsupportedOperationException(
+ "This method is no longer called by Lucene's code and custom code should also not call it.");
}
/**
diff --git a/lucene/core/src/java/org/apache/lucene/util/GroupVIntUtil.java b/lucene/core/src/java/org/apache/lucene/util/GroupVIntUtil.java
index a1917d87a17..b1c1307331f 100644
--- a/lucene/core/src/java/org/apache/lucene/util/GroupVIntUtil.java
+++ b/lucene/core/src/java/org/apache/lucene/util/GroupVIntUtil.java
@@ -19,6 +19,8 @@ package org.apache.lucene.util;
import java.io.IOException;
import org.apache.lucene.store.DataInput;
import org.apache.lucene.store.DataOutput;
+import org.apache.lucene.store.IndexInput;
+import org.apache.lucene.store.RandomAccessInput;
/**
* This class contains utility methods and constants for group varint
@@ -26,8 +28,8 @@ import org.apache.lucene.store.DataOutput;
* @lucene.internal
*/
public final class GroupVIntUtil {
- // the maximum length of a single group-varint is 4 integers + 1 byte flag.
- public static final int MAX_LENGTH_PER_GROUP = 17;
+ // the maximum length of a single group-varint is 1 byte flag and 4 integers.
+ public static final int MAX_LENGTH_PER_GROUP = Byte.BYTES + 4 * Integer.BYTES;
private static final int[] INT_MASKS = new int[] {0xFF, 0xFFFF, 0xFFFFFF, ~0};
@@ -41,7 +43,7 @@ public final class GroupVIntUtil {
public static void readGroupVInts(DataInput in, int[] dst, int limit) throws IOException {
int i;
for (i = 0; i <= limit - 4; i += 4) {
- in.readGroupVInt(dst, i);
+ readGroupVInt(in, dst, i);
}
for (; i < limit; ++i) {
dst[i] = in.readVInt();
@@ -49,13 +51,17 @@ public final class GroupVIntUtil {
}
/**
- * Default implementation of read single group, for optimal performance, you should use {@link
- * GroupVIntUtil#readGroupVInts(DataInput, int[], int)} instead.
+ * Read single group, for optimal performance, you should use {@link
+ * GroupVIntUtil#readGroupVInts(DataInput, int[], int)} to decode a full group including tails
+ * instead.
*
* @param in the input to use to read data.
* @param dst the array to read ints into.
* @param offset the offset in the array to start storing ints.
+ * @deprecated Use {@link #readGroupVInts(DataInput, int[], int)} to decode a full group including
+ * tails instead
*/
+ @Deprecated
public static void readGroupVInt(DataInput in, int[] dst, int offset) throws IOException {
final int flag = in.readByte() & 0xFF;
@@ -64,6 +70,53 @@ public final class GroupVIntUtil {
final int n3Minus1 = (flag >> 2) & 0x03;
final int n4Minus1 = flag & 0x03;
+ // if our DataInput implements RandomAccessInput for absolute access and IndexInput for seeking,
+ // we use a branch-less implementation:
+ if (in instanceof RandomAccessInput rin && in instanceof IndexInput iin) {
+ long pos = iin.getFilePointer();
+ if (iin.length() - pos >= 4 * Integer.BYTES) {
+ dst[offset] = rin.readInt(pos) & INT_MASKS[n1Minus1];
+ pos += 1 + n1Minus1;
+ dst[offset + 1] = rin.readInt(pos) & INT_MASKS[n2Minus1];
+ pos += 1 + n2Minus1;
+ dst[offset + 2] = rin.readInt(pos) & INT_MASKS[n3Minus1];
+ pos += 1 + n3Minus1;
+ dst[offset + 3] = rin.readInt(pos) & INT_MASKS[n4Minus1];
+ pos += 1 + n4Minus1;
+
+ iin.seek(pos);
+ return;
+ }
+ }
+
+ // fall-through: default impl
+ dst[offset] = readIntInGroup(in, n1Minus1);
+ dst[offset + 1] = readIntInGroup(in, n2Minus1);
+ dst[offset + 2] = readIntInGroup(in, n3Minus1);
+ dst[offset + 3] = readIntInGroup(in, n4Minus1);
+ }
+
+ /** DO not use! Only visible for benchmarking purposes! */
+ public static void readGroupVInts$Baseline(DataInput in, int[] dst, int limit)
+ throws IOException {
+ int i;
+ for (i = 0; i <= limit - 4; i += 4) {
+ readGroupVInt$Baseline(in, dst, i);
+ }
+ for (; i < limit; ++i) {
+ dst[i] = in.readVInt();
+ }
+ }
+
+ private static void readGroupVInt$Baseline(DataInput in, int[] dst, int offset)
+ throws IOException {
+ final int flag = in.readByte() & 0xFF;
+
+ final int n1Minus1 = flag >> 6;
+ final int n2Minus1 = (flag >> 4) & 0x03;
+ final int n3Minus1 = (flag >> 2) & 0x03;
+ final int n4Minus1 = flag & 0x03;
+
dst[offset] = readIntInGroup(in, n1Minus1);
dst[offset + 1] = readIntInGroup(in, n2Minus1);
dst[offset + 2] = readIntInGroup(in, n3Minus1);
@@ -86,7 +139,11 @@ public final class GroupVIntUtil {
/**
* Provides an abstraction for read int values, so that decoding logic can be reused in different
* DataInput.
+ *
+ * @deprecated No longer used.
+ * @see #readGroupVInt(DataInput, long, IntReader, long, int[], int)
*/
+ @Deprecated
@FunctionalInterface
public static interface IntReader {
int read(long v);
@@ -96,40 +153,17 @@ public final class GroupVIntUtil {
* Faster implementation of read single group, It read values from the buffer that would not cross
* boundaries.
*
- * @param in the input to use to read data.
- * @param remaining the number of remaining bytes allowed to read for current block/segment.
- * @param reader the supplier of read int.
- * @param pos the start pos to read from the reader.
- * @param dst the array to read ints into.
- * @param offset the offset in the array to start storing ints.
- * @return the number of bytes read excluding the flag. this indicates the number of positions
- * should to be increased for caller, it is 0 or positive number and less than {@link
- * #MAX_LENGTH_PER_GROUP}
+ * @throws UnsupportedOperationException (always)
+ * @deprecated Don't call this method, it is no longer implemented. It was only provided for
+ * custom {@link DataInput} subclasses to allow to provide a faster GroupVInt encoding when
+ * random access is provided by the underlying storage. This is now obsolete, any
+ * implementation calling this should be removed in the calling class.
*/
+ @Deprecated
public static int readGroupVInt(
DataInput in, long remaining, IntReader reader, long pos, int[] dst, int offset)
throws IOException {
- if (remaining < MAX_LENGTH_PER_GROUP) {
- readGroupVInt(in, dst, offset);
- return 0;
- }
- final int flag = in.readByte() & 0xFF;
- final long posStart = ++pos; // exclude the flag bytes, the position has updated via readByte().
- final int n1Minus1 = flag >> 6;
- final int n2Minus1 = (flag >> 4) & 0x03;
- final int n3Minus1 = (flag >> 2) & 0x03;
- final int n4Minus1 = flag & 0x03;
-
- // This code path has fewer conditionals and tends to be significantly faster in benchmarks
- dst[offset] = reader.read(pos) & INT_MASKS[n1Minus1];
- pos += 1 + n1Minus1;
- dst[offset + 1] = reader.read(pos) & INT_MASKS[n2Minus1];
- pos += 1 + n2Minus1;
- dst[offset + 2] = reader.read(pos) & INT_MASKS[n3Minus1];
- pos += 1 + n3Minus1;
- dst[offset + 3] = reader.read(pos) & INT_MASKS[n4Minus1];
- pos += 1 + n4Minus1;
- return (int) (pos - posStart);
+ throw new UnsupportedOperationException("No longer implemented.");
}
private static int numBytes(int v) {
diff --git a/lucene/core/src/java21/org/apache/lucene/store/MemorySegmentIndexInput.java b/lucene/core/src/java21/org/apache/lucene/store/MemorySegmentIndexInput.java
index 83d61fb0b4d..e45d7d8f25b 100644
--- a/lucene/core/src/java21/org/apache/lucene/store/MemorySegmentIndexInput.java
+++ b/lucene/core/src/java21/org/apache/lucene/store/MemorySegmentIndexInput.java
@@ -29,7 +29,6 @@ import java.util.function.Function;
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.BitUtil;
import org.apache.lucene.util.Constants;
-import org.apache.lucene.util.GroupVIntUtil;
import org.apache.lucene.util.IOConsumer;
/**
@@ -455,23 +454,6 @@ abstract class MemorySegmentIndexInput extends IndexInput implements MemorySegme
}
}
- @Override
- public void readGroupVInt(int[] dst, int offset) throws IOException {
- try {
- final int len =
- GroupVIntUtil.readGroupVInt(
- this,
- curSegment.byteSize() - curPosition,
- p -> curSegment.get(LAYOUT_LE_INT, p),
- curPosition,
- dst,
- offset);
- curPosition += len;
- } catch (NullPointerException | IllegalStateException e) {
- throw alreadyClosed(e);
- }
- }
-
@Override
public void readBytes(long pos, byte[] b, int offset, int len) throws IOException {
try {