You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by iv...@apache.org on 2025/03/21 13:51:34 UTC
(lucene) branch branch_10x updated: Use FixedLengthBytesRefArray in OneDimensionBKDWriter to hold split values (#14383)
This is an automated email from the ASF dual-hosted git repository.
ivera 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 9b9c78041c8 Use FixedLengthBytesRefArray in OneDimensionBKDWriter to hold split values (#14383)
9b9c78041c8 is described below
commit 9b9c78041c83b9a1b99eff36e940508fd6aee0e9
Author: Ignacio Vera <iv...@apache.org>
AuthorDate: Fri Mar 21 14:49:27 2025 +0100
Use FixedLengthBytesRefArray in OneDimensionBKDWriter to hold split values (#14383)
---
lucene/CHANGES.txt | 2 ++
.../lucene/util/FixedLengthBytesRefArray.java | 21 ++++++++++++++++-
.../java/org/apache/lucene/util/bkd/BKDWriter.java | 15 ++++++++-----
.../lucene/util/TestFixedLengthBytesRefArray.java | 26 +++++++---------------
4 files changed, 39 insertions(+), 25 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 6ac98ef5ca3..0c2700ed41e 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -148,6 +148,8 @@ Optimizations
* GITHUB#14331: Speedup merging of HNSW graphs. (Mayya Sharipova, Tom Veasey)
+* GITHUB#14383: Use FixedLengthBytesRefArray in OneDimensionBKDWriter to hold split values. (Ignacio Vera)
+
Bug Fixes
---------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/FixedLengthBytesRefArray.java b/lucene/core/src/java/org/apache/lucene/util/FixedLengthBytesRefArray.java
index 0f1a9df3cd5..c774ced4b7b 100644
--- a/lucene/core/src/java/org/apache/lucene/util/FixedLengthBytesRefArray.java
+++ b/lucene/core/src/java/org/apache/lucene/util/FixedLengthBytesRefArray.java
@@ -17,6 +17,7 @@
package org.apache.lucene.util;
import java.util.Comparator;
+import java.util.Objects;
/**
* Just like {@link BytesRefArray} except all values have the same length.
@@ -26,7 +27,7 @@ import java.util.Comparator;
* @lucene.internal
* @lucene.experimental
*/
-final class FixedLengthBytesRefArray implements SortableBytesRefArray {
+public final class FixedLengthBytesRefArray implements SortableBytesRefArray {
private final int valueLength;
private final int valuesPerBlock;
@@ -90,6 +91,24 @@ final class FixedLengthBytesRefArray implements SortableBytesRefArray {
return size++;
}
+ /**
+ * Returns the <i>n'th</i> element of this {@link FixedLengthBytesRefArray}
+ *
+ * @param spare a spare {@link BytesRef} instance. The length of this spare should be equal to the
+ * fixed length.
+ * @param index the elements index to retrieve
+ * @return the <i>n'th</i> element of this {@link FixedLengthBytesRefArray}
+ */
+ public BytesRef get(BytesRef spare, int index) {
+ Objects.checkIndex(index, size);
+ assert spare.length == valueLength;
+ final int block = index / valuesPerBlock;
+ final int pos = index % valuesPerBlock;
+ spare.bytes = blocks[block];
+ spare.offset = pos * valueLength;
+ return spare;
+ }
+
/**
* Returns the current size of this {@link FixedLengthBytesRefArray}
*
diff --git a/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java b/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
index 6f2c7498f15..3fb80e5c303 100644
--- a/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
@@ -40,6 +40,7 @@ import org.apache.lucene.util.ArrayUtil.ByteArrayComparator;
import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.BytesRefBuilder;
import org.apache.lucene.util.FixedBitSet;
+import org.apache.lucene.util.FixedLengthBytesRefArray;
import org.apache.lucene.util.IORunnable;
import org.apache.lucene.util.IOUtils;
import org.apache.lucene.util.NumericUtils;
@@ -678,7 +679,8 @@ public class BKDWriter implements Closeable {
final IndexOutput metaOut, indexOut, dataOut;
final long dataStartFP;
final LongArrayList leafBlockFPs = new LongArrayList();
- final List<byte[]> leafBlockStartValues = new ArrayList<>();
+ final FixedLengthBytesRefArray leafBlockStartValues =
+ new FixedLengthBytesRefArray(config.packedIndexBytesLength());
final byte[] leafValues = new byte[config.maxPointsInLeafNode() * config.packedBytesLength()];
final int[] leafDocs = new int[config.maxPointsInLeafNode()];
private long valueCount;
@@ -768,7 +770,7 @@ public class BKDWriter implements Closeable {
pointCount = valueCount;
- scratchBytesRef1.length = config.bytesPerDim();
+ scratchBytesRef1.length = config.packedIndexBytesLength();
scratchBytesRef1.offset = 0;
assert leafBlockStartValues.size() + 1 == leafBlockFPs.size();
BKDTreeLeafNodes leafNodes =
@@ -780,8 +782,7 @@ public class BKDWriter implements Closeable {
@Override
public BytesRef getSplitValue(int index) {
- scratchBytesRef1.bytes = leafBlockStartValues.get(index);
- return scratchBytesRef1;
+ return leafBlockStartValues.get(scratchBytesRef1, index);
}
@Override
@@ -816,8 +817,10 @@ public class BKDWriter implements Closeable {
if (leafBlockFPs.size() > 0) {
// Save the first (minimum) value in each leaf block except the first, to build the split
// value index in the end:
- leafBlockStartValues.add(
- ArrayUtil.copyOfSubArray(leafValues, 0, config.packedBytesLength()));
+ scratchBytesRef1.bytes = leafValues;
+ scratchBytesRef1.offset = 0;
+ scratchBytesRef1.length = config.packedIndexBytesLength();
+ leafBlockStartValues.append(scratchBytesRef1);
}
leafBlockFPs.add(dataOut.getFilePointer());
checkMaxLeafNodeCount(leafBlockFPs.size());
diff --git a/lucene/core/src/test/org/apache/lucene/util/TestFixedLengthBytesRefArray.java b/lucene/core/src/test/org/apache/lucene/util/TestFixedLengthBytesRefArray.java
index d962e9ccece..1ddf92479c7 100644
--- a/lucene/core/src/test/org/apache/lucene/util/TestFixedLengthBytesRefArray.java
+++ b/lucene/core/src/test/org/apache/lucene/util/TestFixedLengthBytesRefArray.java
@@ -18,7 +18,6 @@
package org.apache.lucene.util;
import java.util.Arrays;
-import java.util.Comparator;
import org.apache.lucene.tests.util.LuceneTestCase;
import org.apache.lucene.tests.util.TestUtil;
@@ -32,15 +31,7 @@ public class TestFixedLengthBytesRefArray extends LuceneTestCase {
a.append(new BytesRef(bytes));
}
- BytesRefIterator iterator =
- a.iterator(
- new Comparator<BytesRef>() {
- @Override
- public int compare(BytesRef a, BytesRef b) {
- return a.compareTo(b);
- }
- });
-
+ BytesRefIterator iterator = a.iterator(BytesRef::compareTo);
BytesRef last = null;
int count = 0;
@@ -64,6 +55,8 @@ public class TestFixedLengthBytesRefArray extends LuceneTestCase {
int length = TestUtil.nextInt(random(), 4, 10);
int count = atLeast(10000);
BytesRef[] values = new BytesRef[count];
+ BytesRef scratch = new BytesRef();
+ scratch.length = length;
FixedLengthBytesRefArray a = new FixedLengthBytesRefArray(length);
for (int i = 0; i < count; i++) {
@@ -73,15 +66,12 @@ public class TestFixedLengthBytesRefArray extends LuceneTestCase {
a.append(value);
}
+ for (int i = 0; i < count; i++) {
+ assertEquals(values[i], a.get(scratch, i));
+ }
+
Arrays.sort(values);
- BytesRefIterator iterator =
- a.iterator(
- new Comparator<BytesRef>() {
- @Override
- public int compare(BytesRef a, BytesRef b) {
- return a.compareTo(b);
- }
- });
+ BytesRefIterator iterator = a.iterator(BytesRef::compareTo);
for (int i = 0; i < count; i++) {
BytesRef next = iterator.next();
assertNotNull(next);