You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by pa...@apache.org on 2023/12/14 14:01:24 UTC
(lucene) branch branch_9x updated: Introduce growInRange to reduce array overallocation (#12844)
This is an automated email from the ASF dual-hosted git repository.
patrickz pushed a commit to branch branch_9x
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/branch_9x by this push:
new eb57db27bae Introduce growInRange to reduce array overallocation (#12844)
eb57db27bae is described below
commit eb57db27bae00dc359cf94fa1bda30ed30b564db
Author: Stefan Vodita <41...@users.noreply.github.com>
AuthorDate: Thu Dec 14 16:00:26 2023 +0200
Introduce growInRange to reduce array overallocation (#12844)
In cases where we know there is an upper limit to the potential size
of an array, we can use `growInRange` to avoid allocating beyond that
limit.
---
lucene/CHANGES.txt | 4 ++-
.../src/java/org/apache/lucene/util/ArrayUtil.java | 29 +++++++++++++++++---
.../test/org/apache/lucene/util/TestArrayUtil.java | 32 ++++++++++++++++++++++
.../directory/DirectoryTaxonomyReader.java | 6 ++--
4 files changed, 64 insertions(+), 7 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 878a9701c94..fefd13c3a7c 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -35,7 +35,9 @@ Improvements
Optimizations
---------------------
-(No changes)
+
+* GITHUB#12839: Introduce method to grow arrays up to a given upper limit and use it to reduce overallocation for
+ DirectoryTaxonomyReader#getBulkOrdinals. (Stefan Vodita)
Bug Fixes
---------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/ArrayUtil.java b/lucene/core/src/java/org/apache/lucene/util/ArrayUtil.java
index 629e289ef4d..336b5b3e6bb 100644
--- a/lucene/core/src/java/org/apache/lucene/util/ArrayUtil.java
+++ b/lucene/core/src/java/org/apache/lucene/util/ArrayUtil.java
@@ -330,15 +330,36 @@ public final class ArrayUtil {
return copy;
}
+ /**
+ * Returns an array whose size is at least {@code minLength}, generally over-allocating
+ * exponentially, but never allocating more than {@code maxLength} elements.
+ */
+ public static int[] growInRange(int[] array, int minLength, int maxLength) {
+ assert minLength >= 0
+ : "length must be positive (got " + minLength + "): likely integer overflow?";
+
+ if (minLength > maxLength) {
+ throw new IllegalArgumentException(
+ "requested minimum array length "
+ + minLength
+ + " is larger than requested maximum array length "
+ + maxLength);
+ }
+
+ if (array.length >= minLength) {
+ return array;
+ }
+
+ int potentialLength = oversize(minLength, Integer.BYTES);
+ return growExact(array, Math.min(maxLength, potentialLength));
+ }
+
/**
* Returns an array whose size is at least {@code minSize}, generally over-allocating
* exponentially
*/
public static int[] grow(int[] array, int minSize) {
- assert minSize >= 0 : "size must be positive (got " + minSize + "): likely integer overflow?";
- if (array.length < minSize) {
- return growExact(array, oversize(minSize, Integer.BYTES));
- } else return array;
+ return growInRange(array, minSize, Integer.MAX_VALUE);
}
/**
diff --git a/lucene/core/src/test/org/apache/lucene/util/TestArrayUtil.java b/lucene/core/src/test/org/apache/lucene/util/TestArrayUtil.java
index abc41a5bf9f..972fd0c3c84 100644
--- a/lucene/core/src/test/org/apache/lucene/util/TestArrayUtil.java
+++ b/lucene/core/src/test/org/apache/lucene/util/TestArrayUtil.java
@@ -18,6 +18,8 @@ package org.apache.lucene.util;
import static org.apache.lucene.util.ArrayUtil.copyOfSubArray;
import static org.apache.lucene.util.ArrayUtil.growExact;
+import static org.apache.lucene.util.ArrayUtil.growInRange;
+import static org.apache.lucene.util.ArrayUtil.oversize;
import java.util.Arrays;
import java.util.Collections;
@@ -371,6 +373,36 @@ public class TestArrayUtil extends LuceneTestCase {
() -> growExact(new String[] {"a", "b", "c"}, random().nextInt(3)));
}
+ public void testGrowInRange() {
+ int[] array = new int[] {1, 2, 3};
+
+ // If minLength is negative, maxLength does not matter
+ expectThrows(AssertionError.class, () -> growInRange(array, -1, 4));
+ expectThrows(AssertionError.class, () -> growInRange(array, -1, 0));
+ expectThrows(AssertionError.class, () -> growInRange(array, -1, -1));
+
+ // If minLength > maxLength, we throw an exception
+ expectThrows(IllegalArgumentException.class, () -> growInRange(array, 1, 0));
+ expectThrows(IllegalArgumentException.class, () -> growInRange(array, 4, 3));
+ expectThrows(IllegalArgumentException.class, () -> growInRange(array, 5, 4));
+
+ // If minLength is sufficient, we return the array
+ assertSame(array, growInRange(array, 1, 4));
+ assertSame(array, growInRange(array, 1, 2));
+ assertSame(array, growInRange(array, 1, 1));
+
+ int minLength = 4;
+ int maxLength = Integer.MAX_VALUE;
+
+ // The array grows normally if maxLength permits
+ assertEquals(
+ oversize(minLength, Integer.BYTES),
+ growInRange(new int[] {1, 2, 3}, minLength, maxLength).length);
+
+ // The array grows to maxLength if maxLength is limiting
+ assertEquals(minLength, growInRange(new int[] {1, 2, 3}, minLength, minLength).length);
+ }
+
public void testCopyOfSubArray() {
short[] shortArray = {1, 2, 3};
assertArrayEquals(new short[] {1}, copyOfSubArray(shortArray, 0, 1));
diff --git a/lucene/facet/src/java/org/apache/lucene/facet/taxonomy/directory/DirectoryTaxonomyReader.java b/lucene/facet/src/java/org/apache/lucene/facet/taxonomy/directory/DirectoryTaxonomyReader.java
index c19620f0ccd..a9d989a37b7 100644
--- a/lucene/facet/src/java/org/apache/lucene/facet/taxonomy/directory/DirectoryTaxonomyReader.java
+++ b/lucene/facet/src/java/org/apache/lucene/facet/taxonomy/directory/DirectoryTaxonomyReader.java
@@ -329,7 +329,8 @@ public class DirectoryTaxonomyReader extends TaxonomyReader implements Accountab
}
// First try to find results in the cache:
int[] result = new int[categoryPaths.length];
- int[] indexesMissingFromCache = new int[10]; // initial size, will grow when required
+ // Will grow when required, but never beyond categoryPaths.length
+ int[] indexesMissingFromCache = new int[Math.min(10, categoryPaths.length)];
int numberOfMissingFromCache = 0;
FacetLabel cp;
Integer res;
@@ -353,7 +354,8 @@ public class DirectoryTaxonomyReader extends TaxonomyReader implements Accountab
}
} else {
indexesMissingFromCache =
- ArrayUtil.grow(indexesMissingFromCache, numberOfMissingFromCache + 1);
+ ArrayUtil.growInRange(
+ indexesMissingFromCache, numberOfMissingFromCache + 1, categoryPaths.length);
indexesMissingFromCache[numberOfMissingFromCache++] = i;
}
}