You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2016/05/30 08:31:14 UTC
[1/2] lucene-solr:master: LUCENE-7306: Speed up points
indexing/merging with radix sort.
Repository: lucene-solr
Updated Branches:
refs/heads/branch_6x a460addd2 -> 358d6f7e6
refs/heads/master 05ce40a0b -> ecec5244d
LUCENE-7306: Speed up points indexing/merging with radix sort.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/ecec5244
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/ecec5244
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/ecec5244
Branch: refs/heads/master
Commit: ecec5244df39705b00272f3a5c783c0f915a4c31
Parents: 05ce40a
Author: Adrien Grand <jp...@gmail.com>
Authored: Fri May 27 12:55:27 2016 +0200
Committer: Adrien Grand <jp...@gmail.com>
Committed: Mon May 30 10:29:59 2016 +0200
----------------------------------------------------------------------
lucene/CHANGES.txt | 5 +-
.../apache/lucene/util/BytesRefComparator.java | 55 +++++
.../lucene/util/FixedLengthBytesRefArray.java | 29 +++
.../org/apache/lucene/util/MSBRadixSorter.java | 219 +++++++++++++++++++
.../lucene/util/StringMSBRadixSorter.java | 158 ++-----------
.../org/apache/lucene/util/bkd/BKDWriter.java | 113 ++++------
.../apache/lucene/util/TestMSBRadixSorter.java | 117 ++++++++++
7 files changed, 487 insertions(+), 209 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/ecec5244/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 9413d14..5dc8a2c 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -90,7 +90,10 @@ Optimizations
(which is used by TermsQuery, multi-term queries and several point queries).
(Adrien Grand, Jeff Wartes, David Smiley)
-* LUCENE-7299: Speed up BytesRefHash.sort(). (Adrien Grand)
+* LUCENE-7299: Speed up BytesRefHash.sort() using radix sort. (Adrien Grand)
+
+* LUCENE-7306: Speed up points indexing and merging using radix sort.
+ (Adrien Grand)
Bug Fixes
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/ecec5244/lucene/core/src/java/org/apache/lucene/util/BytesRefComparator.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/BytesRefComparator.java b/lucene/core/src/java/org/apache/lucene/util/BytesRefComparator.java
new file mode 100644
index 0000000..821b8f2
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/util/BytesRefComparator.java
@@ -0,0 +1,55 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.util;
+
+import java.util.Comparator;
+
+/** Specialized {@link BytesRef} comparator that
+ * {@link FixedLengthBytesRefArray#iterator(Comparator)} has optimizations
+ * for.
+ * @lucene.internal */
+public abstract class BytesRefComparator implements Comparator<BytesRef> {
+
+ final int comparedBytesCount;
+
+ /** Sole constructor.
+ * @param comparedBytesCount the maximum number of bytes to compare. */
+ protected BytesRefComparator(int comparedBytesCount) {
+ this.comparedBytesCount = comparedBytesCount;
+ }
+
+ /** Return the unsigned byte to use for comparison at index {@code i}, or
+ * {@code -1} if all bytes that are useful for comparisons are exhausted.
+ * This may only be called with a value of {@code i} between {@code 0}
+ * included and {@code comparedBytesCount} excluded. */
+ protected abstract int byteAt(BytesRef ref, int i);
+
+ @Override
+ public int compare(BytesRef o1, BytesRef o2) {
+ for (int i = 0; i < comparedBytesCount; ++i) {
+ final int b1 = byteAt(o1, i);
+ final int b2 = byteAt(o2, i);
+ if (b1 != b2) {
+ return b1 - b2;
+ } else if (b1 == -1) {
+ break;
+ }
+ }
+ return 0;
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/ecec5244/lucene/core/src/java/org/apache/lucene/util/FixedLengthBytesRefArray.java
----------------------------------------------------------------------
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 346b908..4fc4108 100644
--- a/lucene/core/src/java/org/apache/lucene/util/FixedLengthBytesRefArray.java
+++ b/lucene/core/src/java/org/apache/lucene/util/FixedLengthBytesRefArray.java
@@ -105,6 +105,35 @@ final class FixedLengthBytesRefArray implements SortableBytesRefArray {
orderedEntries[i] = i;
}
+ if (comp instanceof BytesRefComparator) {
+ BytesRefComparator bComp = (BytesRefComparator) comp;
+ new MSBRadixSorter(bComp.comparedBytesCount) {
+
+ BytesRef scratch;
+
+ {
+ scratch = new BytesRef();
+ scratch.length = valueLength;
+ }
+
+ @Override
+ protected void swap(int i, int j) {
+ int o = orderedEntries[i];
+ orderedEntries[i] = orderedEntries[j];
+ orderedEntries[j] = o;
+ }
+
+ @Override
+ protected int byteAt(int i, int k) {
+ int index1 = orderedEntries[i];
+ scratch.bytes = blocks[index1 / valuesPerBlock];
+ scratch.offset = (index1 % valuesPerBlock) * valueLength;
+ return bComp.byteAt(scratch, k);
+ }
+ }.sort(0, size());
+ return orderedEntries;
+ }
+
final BytesRef pivot = new BytesRef();
final BytesRef scratch1 = new BytesRef();
final BytesRef scratch2 = new BytesRef();
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/ecec5244/lucene/core/src/java/org/apache/lucene/util/MSBRadixSorter.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/MSBRadixSorter.java b/lucene/core/src/java/org/apache/lucene/util/MSBRadixSorter.java
new file mode 100644
index 0000000..33f20b6
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/util/MSBRadixSorter.java
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.util;
+
+import java.util.Arrays;
+
+/** Radix sorter for variable-length strings. This class sorts based on the most
+ * significant byte first and falls back to {@link IntroSorter} when the size
+ * of the buckets to sort becomes small. It is <b>NOT</b> stable.
+ * Worst-case memory usage is about {@code 2.3 KB}.
+ * @lucene.internal */
+public abstract class MSBRadixSorter extends Sorter {
+
+ // after that many levels of recursion we fall back to introsort anyway
+ // this is used as a protection against the fact that radix sort performs
+ // worse when there are long common prefixes (probably because of cache
+ // locality)
+ private static final int LEVEL_THRESHOLD = 8;
+ // size of histograms: 256 + 1 to indicate that the string is finished
+ private static final int HISTOGRAM_SIZE = 257;
+ // buckets below this size will be sorted with introsort
+ private static final int LENGTH_THRESHOLD = 100;
+
+ // we store one histogram per recursion level
+ private final int[][] histograms = new int[LEVEL_THRESHOLD][];
+ private final int[] endOffsets = new int[HISTOGRAM_SIZE];
+
+ private final int maxLength;
+
+ /**
+ * Sole constructor.
+ * @param maxLength the maximum length of keys, pass {@link Integer#MAX_VALUE} if unknown.
+ */
+ protected MSBRadixSorter(int maxLength) {
+ this.maxLength = maxLength;
+ }
+
+ /** Return the k-th byte of the entry at index {@code i}, or {@code -1} if
+ * its length is less than or equal to {@code k}. This may only be called
+ * with a value of {@code i} between {@code 0} included and
+ * {@code maxLength} excluded. */
+ protected abstract int byteAt(int i, int k);
+
+ /** Get a fall-back sorter which may assume that the first k bytes of all compared strings are equal. */
+ protected Sorter getFallbackSorter(int k) {
+ return new IntroSorter() {
+ @Override
+ protected void swap(int i, int j) {
+ MSBRadixSorter.this.swap(i, j);
+ }
+
+ @Override
+ protected int compare(int i, int j) {
+ for (int o = k; o < maxLength; ++o) {
+ final int b1 = byteAt(i, o);
+ final int b2 = byteAt(j, o);
+ if (b1 != b2) {
+ return b1 - b2;
+ } else if (b1 == -1) {
+ break;
+ }
+ }
+ return 0;
+ }
+
+ @Override
+ protected void setPivot(int i) {
+ pivot.setLength(0);
+ for (int o = k; o < maxLength; ++o) {
+ final int b = byteAt(i, o);
+ if (b == -1) {
+ break;
+ }
+ pivot.append((byte) b);
+ }
+ }
+
+ @Override
+ protected int comparePivot(int j) {
+ for (int o = 0; o < pivot.length(); ++o) {
+ final int b1 = pivot.byteAt(o) & 0xff;
+ final int b2 = byteAt(j, k + o);
+ if (b1 != b2) {
+ return b1 - b2;
+ }
+ }
+ if (k + pivot.length() == maxLength) {
+ return 0;
+ }
+ return -1 - byteAt(j, k + pivot.length());
+ }
+
+ private final BytesRefBuilder pivot = new BytesRefBuilder();
+ };
+ }
+
+ @Override
+ protected final int compare(int i, int j) {
+ throw new UnsupportedOperationException("unused: not a comparison-based sort");
+ }
+
+ @Override
+ public void sort(int from, int to) {
+ checkRange(from, to);
+ sort(from, to, 0);
+ }
+
+ private void sort(int from, int to, int k) {
+ if (to - from <= LENGTH_THRESHOLD || k >= LEVEL_THRESHOLD) {
+ introSort(from, to, k);
+ } else {
+ radixSort(from, to, k);
+ }
+ }
+
+ private void introSort(int from, int to, int k) {
+ getFallbackSorter(k).sort(from, to);
+ }
+
+ private void radixSort(int from, int to, int k) {
+ int[] histogram = histograms[k];
+ if (histogram == null) {
+ histogram = histograms[k] = new int[HISTOGRAM_SIZE];
+ } else {
+ Arrays.fill(histogram, 0);
+ }
+
+ buildHistogram(from, to, k, histogram);
+
+ // short-circuit: if all keys have the same byte at offset k, then recurse directly
+ for (int i = 0; i < HISTOGRAM_SIZE; ++i) {
+ if (histogram[i] == to - from) {
+ // everything is in the same bucket, recurse
+ if (i > 0) {
+ sort(from, to, k + 1);
+ }
+ return;
+ } else if (histogram[i] != 0) {
+ break;
+ }
+ }
+
+ int[] startOffsets = histogram;
+ int[] endOffsets = this.endOffsets;
+ sumHistogram(histogram, endOffsets);
+ reorder(from, to, startOffsets, endOffsets, k);
+ endOffsets = startOffsets;
+
+ if (k + 1 < maxLength) {
+ // recurse on all but the first bucket since all keys are equals in this
+ // bucket (we already compared all bytes)
+ for (int prev = endOffsets[0], i = 1; i < HISTOGRAM_SIZE; ++i) {
+ int h = endOffsets[i];
+ final int bucketLen = h - prev;
+ if (bucketLen > 1) {
+ sort(from + prev, from + h, k + 1);
+ }
+ prev = h;
+ }
+ }
+ }
+
+ /** Return a number for the k-th character between 0 and {@link #HISTOGRAM_SIZE}. */
+ private int getBucket(int i, int k) {
+ return byteAt(i, k) + 1;
+ }
+
+ /** Build a histogram of the number of values per {@link #getBucket(int, int) bucket}. */
+ private int[] buildHistogram(int from, int to, int k, int[] histogram) {
+ for (int i = from; i < to; ++i) {
+ histogram[getBucket(i, k)]++;
+ }
+ return histogram;
+ }
+
+ /** Accumulate values of the histogram so that it does not store counts but
+ * start offsets. {@code endOffsets} will store the end offsets. */
+ private static void sumHistogram(int[] histogram, int[] endOffsets) {
+ int accum = 0;
+ for (int i = 0; i < HISTOGRAM_SIZE; ++i) {
+ final int count = histogram[i];
+ histogram[i] = accum;
+ accum += count;
+ endOffsets[i] = accum;
+ }
+ }
+
+ /**
+ * Reorder based on start/end offsets for each bucket. When this method
+ * returns, startOffsets and endOffsets are equal.
+ * @param startOffsets start offsets per bucket
+ * @param endOffsets end offsets per bucket
+ */
+ private void reorder(int from, int to, int[] startOffsets, int[] endOffsets, int k) {
+ // reorder in place, like the dutch flag problem
+ for (int i = 0; i < HISTOGRAM_SIZE; ++i) {
+ final int limit = endOffsets[i];
+ for (int h1 = startOffsets[i]; h1 < limit; h1 = startOffsets[i]) {
+ final int b = getBucket(from + h1, k);
+ final int h2 = startOffsets[b]++;
+ swap(from + h1, from + h2);
+ }
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/ecec5244/lucene/core/src/java/org/apache/lucene/util/StringMSBRadixSorter.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/StringMSBRadixSorter.java b/lucene/core/src/java/org/apache/lucene/util/StringMSBRadixSorter.java
index 84bd074..67cba2b 100644
--- a/lucene/core/src/java/org/apache/lucene/util/StringMSBRadixSorter.java
+++ b/lucene/core/src/java/org/apache/lucene/util/StringMSBRadixSorter.java
@@ -16,61 +16,36 @@
*/
package org.apache.lucene.util;
-import java.util.Arrays;
+abstract class StringMSBRadixSorter extends MSBRadixSorter {
-/** Radix sorter for variable-length strings. This class sorts based on the most
- * significant byte first and falls back to {@link IntroSorter} when the size
- * of the buckets to sort becomes small. It is <b>NOT</b> stable.
- * Worst-case memory usage is about {@code 2.3 KB}. */
-abstract class StringMSBRadixSorter extends Sorter {
-
- // after that many levels of recursion we fall back to introsort anyway
- // this is used as a protection against the fact that radix sort performs
- // worse when there are long common prefixes (probably because of cache
- // locality)
- private static final int LEVEL_THRESHOLD = 8;
- // size of histograms: 256 + 1 to indicate that the string is finished
- private static final int HISTOGRAM_SIZE = 257;
- // buckets below this size will be sorted with introsort
- private static final int LENGTH_THRESHOLD = 100;
-
- // we store one histogram per recursion level
- private final int[][] histograms = new int[LEVEL_THRESHOLD][];
- private final int[] endOffsets = new int[HISTOGRAM_SIZE];
+ StringMSBRadixSorter() {
+ super(Integer.MAX_VALUE);
+ }
/** Get a {@link BytesRef} for the given index. */
protected abstract BytesRef get(int i);
- /** Store bytes for the given index into {@code dest}, without the first k bytes. */
- private void get(int i, int k, BytesRef dest) {
- BytesRef ref = get(i);
- assert ref.length >= k;
- dest.bytes = ref.bytes;
- dest.offset = ref.offset + k;
- dest.length = ref.length - k;
- }
-
@Override
- protected final int compare(int i, int j) {
- throw new UnsupportedOperationException("unused: not a comparison-based sort");
+ protected int byteAt(int i, int k) {
+ BytesRef ref = get(i);
+ if (ref.length <= k) {
+ return -1;
+ }
+ return ref.bytes[ref.offset + k] & 0xff;
}
@Override
- public void sort(int from, int to) {
- checkRange(from, to);
- sort(from, to, 0);
- }
-
- private void sort(int from, int to, int k) {
- if (to - from <= LENGTH_THRESHOLD || k >= LEVEL_THRESHOLD) {
- introSort(from, to, k);
- } else {
- radixSort(from, to, k);
- }
- }
+ protected Sorter getFallbackSorter(int k) {
+ return new IntroSorter() {
+
+ private void get(int i, int k, BytesRef scratch) {
+ BytesRef ref = StringMSBRadixSorter.this.get(i);
+ assert ref.length >= k;
+ scratch.bytes = ref.bytes;
+ scratch.offset = ref.offset + k;
+ scratch.length = ref.length - k;
+ }
- private void introSort(int from, int to, int k) {
- new IntroSorter() {
@Override
protected void swap(int i, int j) {
StringMSBRadixSorter.this.swap(i, j);
@@ -95,96 +70,7 @@ abstract class StringMSBRadixSorter extends Sorter {
}
private final BytesRef pivot = new BytesRef(),
- scratch1 = new BytesRef(), scratch2 = new BytesRef();
- }.sort(from, to);
- }
-
- private void radixSort(int from, int to, int k) {
- int[] histogram = histograms[k];
- if (histogram == null) {
- histogram = histograms[k] = new int[HISTOGRAM_SIZE];
- } else {
- Arrays.fill(histogram, 0);
- }
-
- buildHistogram(from, to, k, histogram);
-
- // short-circuit: if all keys have the same byte at offset k, then recurse directly
- for (int i = 0; i < HISTOGRAM_SIZE; ++i) {
- if (histogram[i] == to - from) {
- // everything is in the same bucket, recurse
- if (i > 0) {
- sort(from, to, k + 1);
- }
- return;
- } else if (histogram[i] != 0) {
- break;
- }
- }
-
- int[] startOffsets = histogram;
- int[] endOffsets = this.endOffsets;
- sumHistogram(histogram, endOffsets);
- reorder(from, to, startOffsets, endOffsets, k);
- endOffsets = startOffsets;
-
- // recurse on all but the first bucket since all keys are equals in this
- // bucket (we already compared all bytes)
- for (int prev = endOffsets[0], i = 1; i < HISTOGRAM_SIZE; ++i) {
- int h = endOffsets[i];
- final int bucketLen = h - prev;
- if (bucketLen > 1) {
- sort(from + prev, from + h, k + 1);
- }
- prev = h;
- }
- }
-
- /** Return a number for the k-th character between 0 and {@link #HISTOGRAM_SIZE}. */
- private int getBucket(int id, int k) {
- BytesRef ref = get(id);
- if (ref.length <= k) {
- return 0;
- }
- final int b = ref.bytes[ref.offset + k] & 0xff;
- return b + 1;
- }
-
- /** Build a histogram of the number of values per {@link #getBucket(int, int) bucket}. */
- private int[] buildHistogram(int from, int to, int k, int[] histogram) {
- for (int i = from; i < to; ++i) {
- histogram[getBucket(i, k)]++;
- }
- return histogram;
- }
-
- /** Accumulate values of the histogram so that it does not store counts but
- * start offsets. {@code endOffsets} will store the end offsets. */
- private static void sumHistogram(int[] histogram, int[] endOffsets) {
- int accum = 0;
- for (int i = 0; i < HISTOGRAM_SIZE; ++i) {
- final int count = histogram[i];
- histogram[i] = accum;
- accum += count;
- endOffsets[i] = accum;
- }
- }
-
- /**
- * Reorder based on start/end offsets for each bucket. When this method
- * returns, startOffsets and endOffsets are equal.
- * @param startOffsets start offsets per bucket
- * @param endOffsets end offsets per bucket
- */
- private void reorder(int from, int to, int[] startOffsets, int[] endOffsets, int k) {
- // reorder in place, like the dutch flag problem
- for (int i = 0; i < HISTOGRAM_SIZE; ++i) {
- final int limit = endOffsets[i];
- for (int h1 = startOffsets[i]; h1 < limit; h1 = startOffsets[i]) {
- final int b = getBucket(from + h1, k);
- final int h2 = startOffsets[b]++;
- swap(from + h1, from + h2);
- }
- }
+ scratch1 = new BytesRef(), scratch2 = new BytesRef();
+ };
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/ecec5244/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
----------------------------------------------------------------------
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 09eef26..ad9dd5d 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
@@ -25,7 +25,6 @@ import java.util.List;
import org.apache.lucene.codecs.CodecUtil;
import org.apache.lucene.index.MergeState;
-import org.apache.lucene.store.ByteArrayDataInput;
import org.apache.lucene.store.ChecksumIndexInput;
import org.apache.lucene.store.Directory;
import org.apache.lucene.store.IOContext;
@@ -33,10 +32,11 @@ import org.apache.lucene.store.IndexOutput;
import org.apache.lucene.store.TrackingDirectoryWrapper;
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.BytesRefComparator;
import org.apache.lucene.util.FixedBitSet;
import org.apache.lucene.util.IOUtils;
-import org.apache.lucene.util.IntroSorter;
import org.apache.lucene.util.LongBitSet;
+import org.apache.lucene.util.MSBRadixSorter;
import org.apache.lucene.util.NumericUtils;
import org.apache.lucene.util.OfflineSorter;
import org.apache.lucene.util.PriorityQueue;
@@ -598,39 +598,26 @@ public class BKDWriter implements Closeable {
/** Sort the heap writer by the specified dim */
private void sortHeapPointWriter(final HeapPointWriter writer, int dim) {
+ final int pointCount = Math.toIntExact(this.pointCount);
+ // Tie-break by docID:
- assert pointCount < Integer.MAX_VALUE;
- //int[] swapCount = new int[1];
- //int[] cmpCount = new int[1];
-
- // System.out.println("SORT length=" + length);
-
- // All buffered points are still in heap; just do in-place sort:
- new IntroSorter() {
- private final byte[] pivotPackedValue = new byte[bytesPerDim];
- private int pivotDocID;
+ // No need to tie break on ord, for the case where the same doc has the same value in a given dimension indexed more than once: it
+ // can't matter at search time since we don't write ords into the index:
+ new MSBRadixSorter(bytesPerDim + Integer.BYTES) {
@Override
- protected void setPivot(int i) {
- pivotDocID = writer.docIDs[i];
- int block = i / writer.valuesPerBlock;
- int index = i % writer.valuesPerBlock;
- System.arraycopy(writer.blocks.get(block), index*packedBytesLength+dim*bytesPerDim, pivotPackedValue, 0, bytesPerDim);
- }
-
- @Override
- protected int comparePivot(int j) {
- //cmpCount[0]++;
- int block = j / writer.valuesPerBlock;
- int index = j % writer.valuesPerBlock;
- assert index >= 0: "index=" + index + " j=" + j;
- int cmp = StringHelper.compare(bytesPerDim, pivotPackedValue, 0, writer.blocks.get(block), bytesPerDim*(index*numDims+dim));
- if (cmp != 0) {
- return cmp;
+ protected int byteAt(int i, int k) {
+ assert k >= 0;
+ if (k < bytesPerDim) {
+ // dim bytes
+ int block = i / writer.valuesPerBlock;
+ int index = i % writer.valuesPerBlock;
+ return writer.blocks.get(block)[index * packedBytesLength + dim * bytesPerDim + k] & 0xff;
+ } else {
+ // doc id
+ int s = 3 - (k - bytesPerDim);
+ return (writer.docIDs[i] >>> (s * 8)) & 0xff;
}
-
- // Tie-break
- return Integer.compare(pivotDocID, writer.docIDs[j]);
}
@Override
@@ -664,26 +651,7 @@ public class BKDWriter implements Closeable {
System.arraycopy(scratch1, 0, blockJ, indexJ, packedBytesLength);
}
- @Override
- protected int compare(int i, int j) {
- //cmpCount[0]++;
- int blockI = i / writer.valuesPerBlock;
- int dimI = i % writer.valuesPerBlock;
- int blockJ = j / writer.valuesPerBlock;
- int dimJ = j % writer.valuesPerBlock;
- int cmp = StringHelper.compare(bytesPerDim, writer.blocks.get(blockI), bytesPerDim*(dimI*numDims+dim), writer.blocks.get(blockJ), bytesPerDim*(dimJ*numDims+dim));
- if (cmp != 0) {
- return cmp;
- }
-
- // Tie-break by docID:
-
- // No need to tie break on ord, for the case where the same doc has the same value in a given dimension indexed more than once: it
- // can't matter at search time since we don't write ords into the index:
- return Integer.compare(writer.docIDs[i], writer.docIDs[j]);
- }
- }.sort(0, Math.toIntExact(pointCount));
- //System.out.println("LEN=" + length + " SWAP=" + swapCount[0] + " CMP=" + cmpCount[0]);
+ }.sort(0, pointCount);
}
private PointWriter sort(int dim) throws IOException {
@@ -718,28 +686,28 @@ public class BKDWriter implements Closeable {
final int offset = bytesPerDim * dim;
- Comparator<BytesRef> cmp = new Comparator<BytesRef>() {
-
- final ByteArrayDataInput reader = new ByteArrayDataInput();
-
- @Override
- public int compare(BytesRef a, BytesRef b) {
- // First compare by the requested dimension we are sorting by:
- int cmp = StringHelper.compare(bytesPerDim, a.bytes, a.offset + offset, b.bytes, b.offset + offset);
-
- if (cmp != 0) {
- return cmp;
+ Comparator<BytesRef> cmp;
+ if (dim == numDims - 1) {
+ // in that case the bytes for the dimension and for the doc id are contiguous,
+ // so we don't need a branch
+ cmp = new BytesRefComparator(bytesPerDim + Integer.BYTES) {
+ @Override
+ protected int byteAt(BytesRef ref, int i) {
+ return ref.bytes[ref.offset + offset + i] & 0xff;
}
-
- // Tie-break by docID ... no need to tie break on ord, for the case where the same doc has
- // the same value in a given dimension indexed more than once: it can't matter at search
- // time since we don't write ords into the index:
-
- return StringHelper.compare(Integer.BYTES,
- a.bytes, a.offset + packedBytesLength,
- b.bytes, b.offset + packedBytesLength);
- }
- };
+ };
+ } else {
+ cmp = new BytesRefComparator(bytesPerDim + Integer.BYTES) {
+ @Override
+ protected int byteAt(BytesRef ref, int i) {
+ if (i < bytesPerDim) {
+ return ref.bytes[ref.offset + offset + i] & 0xff;
+ } else {
+ return ref.bytes[ref.offset + packedBytesLength + i - bytesPerDim] & 0xff;
+ }
+ }
+ };
+ }
OfflineSorter sorter = new OfflineSorter(tempDir, tempFileNamePrefix + "_bkd" + dim, cmp, offlineSorterBufferMB, offlineSorterMaxTempFiles, bytesPerDoc) {
@@ -1266,4 +1234,5 @@ public class BKDWriter implements Closeable {
return new OfflinePointWriter(tempDir, tempFileNamePrefix, packedBytesLength, longOrds, desc, count, singleValuePerDoc);
}
}
+
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/ecec5244/lucene/core/src/test/org/apache/lucene/util/TestMSBRadixSorter.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/test/org/apache/lucene/util/TestMSBRadixSorter.java b/lucene/core/src/test/org/apache/lucene/util/TestMSBRadixSorter.java
new file mode 100644
index 0000000..bc5af7f
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/util/TestMSBRadixSorter.java
@@ -0,0 +1,117 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.util;
+
+import java.util.Arrays;
+
+public class TestMSBRadixSorter extends LuceneTestCase {
+
+ private void test(BytesRef[] refs, int len) {
+ BytesRef[] expected = Arrays.copyOf(refs, len);
+ Arrays.sort(expected);
+
+ int maxLength = 0;
+ for (int i = 0; i < len; ++i) {
+ BytesRef ref = refs[i];
+ maxLength = Math.max(maxLength, ref.length);
+ }
+ switch (random().nextInt(3)) {
+ case 0:
+ maxLength += TestUtil.nextInt(random(), 1, 5);
+ break;
+ case 1:
+ maxLength = Integer.MAX_VALUE;
+ break;
+ default:
+ // leave unchanged
+ break;
+ }
+
+ new MSBRadixSorter(maxLength) {
+
+ protected int byteAt(int i, int k) {
+ BytesRef ref = refs[i];
+ if (ref.length <= k) {
+ return -1;
+ }
+ return ref.bytes[ref.offset + k] & 0xff;
+ }
+
+ @Override
+ protected void swap(int i, int j) {
+ BytesRef tmp = refs[i];
+ refs[i] = refs[j];
+ refs[j] = tmp;
+ }
+ }.sort(0, len);
+ BytesRef[] actual = Arrays.copyOf(refs, len);
+ assertArrayEquals(expected, actual);
+ }
+
+ public void testEmpty() {
+ test(new BytesRef[random().nextInt(5)], 0);
+ }
+
+ public void testOneValue() {
+ BytesRef bytes = new BytesRef(TestUtil.randomSimpleString(random()));
+ test(new BytesRef[] { bytes }, 1);
+ }
+
+ public void testTwoValues() {
+ BytesRef bytes1 = new BytesRef(TestUtil.randomSimpleString(random()));
+ BytesRef bytes2 = new BytesRef(TestUtil.randomSimpleString(random()));
+ test(new BytesRef[] { bytes1, bytes2 }, 2);
+ }
+
+ private void testRandom(int commonPrefixLen, int maxLen) {
+ byte[] commonPrefix = new byte[commonPrefixLen];
+ random().nextBytes(commonPrefix);
+ final int len = random().nextInt(100000);
+ BytesRef[] bytes = new BytesRef[len + random().nextInt(50)];
+ for (int i = 0; i < len; ++i) {
+ byte[] b = new byte[commonPrefixLen + random().nextInt(maxLen)];
+ random().nextBytes(b);
+ System.arraycopy(commonPrefix, 0, b, 0, commonPrefixLen);
+ bytes[i] = new BytesRef(b);
+ }
+ test(bytes, len);
+ }
+
+ public void testRandom() {
+ for (int iter = 0; iter < 10; ++iter) {
+ testRandom(0, 10);
+ }
+ }
+
+ public void testRandomWithLotsOfDuplicates() {
+ for (int iter = 0; iter < 10; ++iter) {
+ testRandom(0, 2);
+ }
+ }
+
+ public void testRandomWithSharedPrefix() {
+ for (int iter = 0; iter < 10; ++iter) {
+ testRandom(TestUtil.nextInt(random(), 1, 30), 10);
+ }
+ }
+
+ public void testRandomWithSharedPrefixAndLotsOfDuplicates() {
+ for (int iter = 0; iter < 10; ++iter) {
+ testRandom(TestUtil.nextInt(random(), 1, 30), 2);
+ }
+ }
+}
[2/2] lucene-solr:branch_6x: LUCENE-7306: Speed up points
indexing/merging with radix sort.
Posted by jp...@apache.org.
LUCENE-7306: Speed up points indexing/merging with radix sort.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/358d6f7e
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/358d6f7e
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/358d6f7e
Branch: refs/heads/branch_6x
Commit: 358d6f7e6be0b546c4c4a08e0277969d623fbbc0
Parents: a460add
Author: Adrien Grand <jp...@gmail.com>
Authored: Fri May 27 12:55:27 2016 +0200
Committer: Adrien Grand <jp...@gmail.com>
Committed: Mon May 30 10:30:40 2016 +0200
----------------------------------------------------------------------
lucene/CHANGES.txt | 5 +-
.../apache/lucene/util/BytesRefComparator.java | 55 +++++
.../lucene/util/FixedLengthBytesRefArray.java | 29 +++
.../org/apache/lucene/util/MSBRadixSorter.java | 219 +++++++++++++++++++
.../lucene/util/StringMSBRadixSorter.java | 158 ++-----------
.../org/apache/lucene/util/bkd/BKDWriter.java | 113 ++++------
.../apache/lucene/util/TestMSBRadixSorter.java | 117 ++++++++++
7 files changed, 487 insertions(+), 209 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/358d6f7e/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index a29ca44..fb60dba 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -86,7 +86,10 @@ Optimizations
(which is used by TermsQuery, multi-term queries and several point queries).
(Adrien Grand, Jeff Wartes, David Smiley)
-* LUCENE-7299: Speed up BytesRefHash.sort(). (Adrien Grand)
+* LUCENE-7299: Speed up BytesRefHash.sort() using radix sort. (Adrien Grand)
+
+* LUCENE-7306: Speed up points indexing and merging using radix sort.
+ (Adrien Grand)
Bug Fixes
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/358d6f7e/lucene/core/src/java/org/apache/lucene/util/BytesRefComparator.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/BytesRefComparator.java b/lucene/core/src/java/org/apache/lucene/util/BytesRefComparator.java
new file mode 100644
index 0000000..821b8f2
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/util/BytesRefComparator.java
@@ -0,0 +1,55 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.util;
+
+import java.util.Comparator;
+
+/** Specialized {@link BytesRef} comparator that
+ * {@link FixedLengthBytesRefArray#iterator(Comparator)} has optimizations
+ * for.
+ * @lucene.internal */
+public abstract class BytesRefComparator implements Comparator<BytesRef> {
+
+ final int comparedBytesCount;
+
+ /** Sole constructor.
+ * @param comparedBytesCount the maximum number of bytes to compare. */
+ protected BytesRefComparator(int comparedBytesCount) {
+ this.comparedBytesCount = comparedBytesCount;
+ }
+
+ /** Return the unsigned byte to use for comparison at index {@code i}, or
+ * {@code -1} if all bytes that are useful for comparisons are exhausted.
+ * This may only be called with a value of {@code i} between {@code 0}
+ * included and {@code comparedBytesCount} excluded. */
+ protected abstract int byteAt(BytesRef ref, int i);
+
+ @Override
+ public int compare(BytesRef o1, BytesRef o2) {
+ for (int i = 0; i < comparedBytesCount; ++i) {
+ final int b1 = byteAt(o1, i);
+ final int b2 = byteAt(o2, i);
+ if (b1 != b2) {
+ return b1 - b2;
+ } else if (b1 == -1) {
+ break;
+ }
+ }
+ return 0;
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/358d6f7e/lucene/core/src/java/org/apache/lucene/util/FixedLengthBytesRefArray.java
----------------------------------------------------------------------
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 346b908..4fc4108 100644
--- a/lucene/core/src/java/org/apache/lucene/util/FixedLengthBytesRefArray.java
+++ b/lucene/core/src/java/org/apache/lucene/util/FixedLengthBytesRefArray.java
@@ -105,6 +105,35 @@ final class FixedLengthBytesRefArray implements SortableBytesRefArray {
orderedEntries[i] = i;
}
+ if (comp instanceof BytesRefComparator) {
+ BytesRefComparator bComp = (BytesRefComparator) comp;
+ new MSBRadixSorter(bComp.comparedBytesCount) {
+
+ BytesRef scratch;
+
+ {
+ scratch = new BytesRef();
+ scratch.length = valueLength;
+ }
+
+ @Override
+ protected void swap(int i, int j) {
+ int o = orderedEntries[i];
+ orderedEntries[i] = orderedEntries[j];
+ orderedEntries[j] = o;
+ }
+
+ @Override
+ protected int byteAt(int i, int k) {
+ int index1 = orderedEntries[i];
+ scratch.bytes = blocks[index1 / valuesPerBlock];
+ scratch.offset = (index1 % valuesPerBlock) * valueLength;
+ return bComp.byteAt(scratch, k);
+ }
+ }.sort(0, size());
+ return orderedEntries;
+ }
+
final BytesRef pivot = new BytesRef();
final BytesRef scratch1 = new BytesRef();
final BytesRef scratch2 = new BytesRef();
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/358d6f7e/lucene/core/src/java/org/apache/lucene/util/MSBRadixSorter.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/MSBRadixSorter.java b/lucene/core/src/java/org/apache/lucene/util/MSBRadixSorter.java
new file mode 100644
index 0000000..33f20b6
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/util/MSBRadixSorter.java
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.util;
+
+import java.util.Arrays;
+
+/** Radix sorter for variable-length strings. This class sorts based on the most
+ * significant byte first and falls back to {@link IntroSorter} when the size
+ * of the buckets to sort becomes small. It is <b>NOT</b> stable.
+ * Worst-case memory usage is about {@code 2.3 KB}.
+ * @lucene.internal */
+public abstract class MSBRadixSorter extends Sorter {
+
+ // after that many levels of recursion we fall back to introsort anyway
+ // this is used as a protection against the fact that radix sort performs
+ // worse when there are long common prefixes (probably because of cache
+ // locality)
+ private static final int LEVEL_THRESHOLD = 8;
+ // size of histograms: 256 + 1 to indicate that the string is finished
+ private static final int HISTOGRAM_SIZE = 257;
+ // buckets below this size will be sorted with introsort
+ private static final int LENGTH_THRESHOLD = 100;
+
+ // we store one histogram per recursion level
+ private final int[][] histograms = new int[LEVEL_THRESHOLD][];
+ private final int[] endOffsets = new int[HISTOGRAM_SIZE];
+
+ private final int maxLength;
+
+ /**
+ * Sole constructor.
+ * @param maxLength the maximum length of keys, pass {@link Integer#MAX_VALUE} if unknown.
+ */
+ protected MSBRadixSorter(int maxLength) {
+ this.maxLength = maxLength;
+ }
+
+ /** Return the k-th byte of the entry at index {@code i}, or {@code -1} if
+ * its length is less than or equal to {@code k}. This may only be called
+ * with a value of {@code i} between {@code 0} included and
+ * {@code maxLength} excluded. */
+ protected abstract int byteAt(int i, int k);
+
+ /** Get a fall-back sorter which may assume that the first k bytes of all compared strings are equal. */
+ protected Sorter getFallbackSorter(int k) {
+ return new IntroSorter() {
+ @Override
+ protected void swap(int i, int j) {
+ MSBRadixSorter.this.swap(i, j);
+ }
+
+ @Override
+ protected int compare(int i, int j) {
+ for (int o = k; o < maxLength; ++o) {
+ final int b1 = byteAt(i, o);
+ final int b2 = byteAt(j, o);
+ if (b1 != b2) {
+ return b1 - b2;
+ } else if (b1 == -1) {
+ break;
+ }
+ }
+ return 0;
+ }
+
+ @Override
+ protected void setPivot(int i) {
+ pivot.setLength(0);
+ for (int o = k; o < maxLength; ++o) {
+ final int b = byteAt(i, o);
+ if (b == -1) {
+ break;
+ }
+ pivot.append((byte) b);
+ }
+ }
+
+ @Override
+ protected int comparePivot(int j) {
+ for (int o = 0; o < pivot.length(); ++o) {
+ final int b1 = pivot.byteAt(o) & 0xff;
+ final int b2 = byteAt(j, k + o);
+ if (b1 != b2) {
+ return b1 - b2;
+ }
+ }
+ if (k + pivot.length() == maxLength) {
+ return 0;
+ }
+ return -1 - byteAt(j, k + pivot.length());
+ }
+
+ private final BytesRefBuilder pivot = new BytesRefBuilder();
+ };
+ }
+
+ @Override
+ protected final int compare(int i, int j) {
+ throw new UnsupportedOperationException("unused: not a comparison-based sort");
+ }
+
+ @Override
+ public void sort(int from, int to) {
+ checkRange(from, to);
+ sort(from, to, 0);
+ }
+
+ private void sort(int from, int to, int k) {
+ if (to - from <= LENGTH_THRESHOLD || k >= LEVEL_THRESHOLD) {
+ introSort(from, to, k);
+ } else {
+ radixSort(from, to, k);
+ }
+ }
+
+ private void introSort(int from, int to, int k) {
+ getFallbackSorter(k).sort(from, to);
+ }
+
+ private void radixSort(int from, int to, int k) {
+ int[] histogram = histograms[k];
+ if (histogram == null) {
+ histogram = histograms[k] = new int[HISTOGRAM_SIZE];
+ } else {
+ Arrays.fill(histogram, 0);
+ }
+
+ buildHistogram(from, to, k, histogram);
+
+ // short-circuit: if all keys have the same byte at offset k, then recurse directly
+ for (int i = 0; i < HISTOGRAM_SIZE; ++i) {
+ if (histogram[i] == to - from) {
+ // everything is in the same bucket, recurse
+ if (i > 0) {
+ sort(from, to, k + 1);
+ }
+ return;
+ } else if (histogram[i] != 0) {
+ break;
+ }
+ }
+
+ int[] startOffsets = histogram;
+ int[] endOffsets = this.endOffsets;
+ sumHistogram(histogram, endOffsets);
+ reorder(from, to, startOffsets, endOffsets, k);
+ endOffsets = startOffsets;
+
+ if (k + 1 < maxLength) {
+ // recurse on all but the first bucket since all keys are equals in this
+ // bucket (we already compared all bytes)
+ for (int prev = endOffsets[0], i = 1; i < HISTOGRAM_SIZE; ++i) {
+ int h = endOffsets[i];
+ final int bucketLen = h - prev;
+ if (bucketLen > 1) {
+ sort(from + prev, from + h, k + 1);
+ }
+ prev = h;
+ }
+ }
+ }
+
+ /** Return a number for the k-th character between 0 and {@link #HISTOGRAM_SIZE}. */
+ private int getBucket(int i, int k) {
+ return byteAt(i, k) + 1;
+ }
+
+ /** Build a histogram of the number of values per {@link #getBucket(int, int) bucket}. */
+ private int[] buildHistogram(int from, int to, int k, int[] histogram) {
+ for (int i = from; i < to; ++i) {
+ histogram[getBucket(i, k)]++;
+ }
+ return histogram;
+ }
+
+ /** Accumulate values of the histogram so that it does not store counts but
+ * start offsets. {@code endOffsets} will store the end offsets. */
+ private static void sumHistogram(int[] histogram, int[] endOffsets) {
+ int accum = 0;
+ for (int i = 0; i < HISTOGRAM_SIZE; ++i) {
+ final int count = histogram[i];
+ histogram[i] = accum;
+ accum += count;
+ endOffsets[i] = accum;
+ }
+ }
+
+ /**
+ * Reorder based on start/end offsets for each bucket. When this method
+ * returns, startOffsets and endOffsets are equal.
+ * @param startOffsets start offsets per bucket
+ * @param endOffsets end offsets per bucket
+ */
+ private void reorder(int from, int to, int[] startOffsets, int[] endOffsets, int k) {
+ // reorder in place, like the dutch flag problem
+ for (int i = 0; i < HISTOGRAM_SIZE; ++i) {
+ final int limit = endOffsets[i];
+ for (int h1 = startOffsets[i]; h1 < limit; h1 = startOffsets[i]) {
+ final int b = getBucket(from + h1, k);
+ final int h2 = startOffsets[b]++;
+ swap(from + h1, from + h2);
+ }
+ }
+ }
+}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/358d6f7e/lucene/core/src/java/org/apache/lucene/util/StringMSBRadixSorter.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/StringMSBRadixSorter.java b/lucene/core/src/java/org/apache/lucene/util/StringMSBRadixSorter.java
index 84bd074..67cba2b 100644
--- a/lucene/core/src/java/org/apache/lucene/util/StringMSBRadixSorter.java
+++ b/lucene/core/src/java/org/apache/lucene/util/StringMSBRadixSorter.java
@@ -16,61 +16,36 @@
*/
package org.apache.lucene.util;
-import java.util.Arrays;
+abstract class StringMSBRadixSorter extends MSBRadixSorter {
-/** Radix sorter for variable-length strings. This class sorts based on the most
- * significant byte first and falls back to {@link IntroSorter} when the size
- * of the buckets to sort becomes small. It is <b>NOT</b> stable.
- * Worst-case memory usage is about {@code 2.3 KB}. */
-abstract class StringMSBRadixSorter extends Sorter {
-
- // after that many levels of recursion we fall back to introsort anyway
- // this is used as a protection against the fact that radix sort performs
- // worse when there are long common prefixes (probably because of cache
- // locality)
- private static final int LEVEL_THRESHOLD = 8;
- // size of histograms: 256 + 1 to indicate that the string is finished
- private static final int HISTOGRAM_SIZE = 257;
- // buckets below this size will be sorted with introsort
- private static final int LENGTH_THRESHOLD = 100;
-
- // we store one histogram per recursion level
- private final int[][] histograms = new int[LEVEL_THRESHOLD][];
- private final int[] endOffsets = new int[HISTOGRAM_SIZE];
+ StringMSBRadixSorter() {
+ super(Integer.MAX_VALUE);
+ }
/** Get a {@link BytesRef} for the given index. */
protected abstract BytesRef get(int i);
- /** Store bytes for the given index into {@code dest}, without the first k bytes. */
- private void get(int i, int k, BytesRef dest) {
- BytesRef ref = get(i);
- assert ref.length >= k;
- dest.bytes = ref.bytes;
- dest.offset = ref.offset + k;
- dest.length = ref.length - k;
- }
-
@Override
- protected final int compare(int i, int j) {
- throw new UnsupportedOperationException("unused: not a comparison-based sort");
+ protected int byteAt(int i, int k) {
+ BytesRef ref = get(i);
+ if (ref.length <= k) {
+ return -1;
+ }
+ return ref.bytes[ref.offset + k] & 0xff;
}
@Override
- public void sort(int from, int to) {
- checkRange(from, to);
- sort(from, to, 0);
- }
-
- private void sort(int from, int to, int k) {
- if (to - from <= LENGTH_THRESHOLD || k >= LEVEL_THRESHOLD) {
- introSort(from, to, k);
- } else {
- radixSort(from, to, k);
- }
- }
+ protected Sorter getFallbackSorter(int k) {
+ return new IntroSorter() {
+
+ private void get(int i, int k, BytesRef scratch) {
+ BytesRef ref = StringMSBRadixSorter.this.get(i);
+ assert ref.length >= k;
+ scratch.bytes = ref.bytes;
+ scratch.offset = ref.offset + k;
+ scratch.length = ref.length - k;
+ }
- private void introSort(int from, int to, int k) {
- new IntroSorter() {
@Override
protected void swap(int i, int j) {
StringMSBRadixSorter.this.swap(i, j);
@@ -95,96 +70,7 @@ abstract class StringMSBRadixSorter extends Sorter {
}
private final BytesRef pivot = new BytesRef(),
- scratch1 = new BytesRef(), scratch2 = new BytesRef();
- }.sort(from, to);
- }
-
- private void radixSort(int from, int to, int k) {
- int[] histogram = histograms[k];
- if (histogram == null) {
- histogram = histograms[k] = new int[HISTOGRAM_SIZE];
- } else {
- Arrays.fill(histogram, 0);
- }
-
- buildHistogram(from, to, k, histogram);
-
- // short-circuit: if all keys have the same byte at offset k, then recurse directly
- for (int i = 0; i < HISTOGRAM_SIZE; ++i) {
- if (histogram[i] == to - from) {
- // everything is in the same bucket, recurse
- if (i > 0) {
- sort(from, to, k + 1);
- }
- return;
- } else if (histogram[i] != 0) {
- break;
- }
- }
-
- int[] startOffsets = histogram;
- int[] endOffsets = this.endOffsets;
- sumHistogram(histogram, endOffsets);
- reorder(from, to, startOffsets, endOffsets, k);
- endOffsets = startOffsets;
-
- // recurse on all but the first bucket since all keys are equals in this
- // bucket (we already compared all bytes)
- for (int prev = endOffsets[0], i = 1; i < HISTOGRAM_SIZE; ++i) {
- int h = endOffsets[i];
- final int bucketLen = h - prev;
- if (bucketLen > 1) {
- sort(from + prev, from + h, k + 1);
- }
- prev = h;
- }
- }
-
- /** Return a number for the k-th character between 0 and {@link #HISTOGRAM_SIZE}. */
- private int getBucket(int id, int k) {
- BytesRef ref = get(id);
- if (ref.length <= k) {
- return 0;
- }
- final int b = ref.bytes[ref.offset + k] & 0xff;
- return b + 1;
- }
-
- /** Build a histogram of the number of values per {@link #getBucket(int, int) bucket}. */
- private int[] buildHistogram(int from, int to, int k, int[] histogram) {
- for (int i = from; i < to; ++i) {
- histogram[getBucket(i, k)]++;
- }
- return histogram;
- }
-
- /** Accumulate values of the histogram so that it does not store counts but
- * start offsets. {@code endOffsets} will store the end offsets. */
- private static void sumHistogram(int[] histogram, int[] endOffsets) {
- int accum = 0;
- for (int i = 0; i < HISTOGRAM_SIZE; ++i) {
- final int count = histogram[i];
- histogram[i] = accum;
- accum += count;
- endOffsets[i] = accum;
- }
- }
-
- /**
- * Reorder based on start/end offsets for each bucket. When this method
- * returns, startOffsets and endOffsets are equal.
- * @param startOffsets start offsets per bucket
- * @param endOffsets end offsets per bucket
- */
- private void reorder(int from, int to, int[] startOffsets, int[] endOffsets, int k) {
- // reorder in place, like the dutch flag problem
- for (int i = 0; i < HISTOGRAM_SIZE; ++i) {
- final int limit = endOffsets[i];
- for (int h1 = startOffsets[i]; h1 < limit; h1 = startOffsets[i]) {
- final int b = getBucket(from + h1, k);
- final int h2 = startOffsets[b]++;
- swap(from + h1, from + h2);
- }
- }
+ scratch1 = new BytesRef(), scratch2 = new BytesRef();
+ };
}
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/358d6f7e/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
----------------------------------------------------------------------
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 288ece4..e13e5cf 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
@@ -25,7 +25,6 @@ import java.util.List;
import org.apache.lucene.codecs.CodecUtil;
import org.apache.lucene.index.MergeState;
-import org.apache.lucene.store.ByteArrayDataInput;
import org.apache.lucene.store.ChecksumIndexInput;
import org.apache.lucene.store.Directory;
import org.apache.lucene.store.IOContext;
@@ -33,10 +32,11 @@ import org.apache.lucene.store.IndexOutput;
import org.apache.lucene.store.TrackingDirectoryWrapper;
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.BytesRefComparator;
import org.apache.lucene.util.FixedBitSet;
import org.apache.lucene.util.IOUtils;
-import org.apache.lucene.util.IntroSorter;
import org.apache.lucene.util.LongBitSet;
+import org.apache.lucene.util.MSBRadixSorter;
import org.apache.lucene.util.NumericUtils;
import org.apache.lucene.util.OfflineSorter;
import org.apache.lucene.util.PriorityQueue;
@@ -604,39 +604,26 @@ public class BKDWriter implements Closeable {
/** Sort the heap writer by the specified dim */
private void sortHeapPointWriter(final HeapPointWriter writer, int dim) {
+ final int pointCount = Math.toIntExact(this.pointCount);
+ // Tie-break by docID:
- assert pointCount < Integer.MAX_VALUE;
- //int[] swapCount = new int[1];
- //int[] cmpCount = new int[1];
-
- // System.out.println("SORT length=" + length);
-
- // All buffered points are still in heap; just do in-place sort:
- new IntroSorter() {
- private final byte[] pivotPackedValue = new byte[bytesPerDim];
- private int pivotDocID;
+ // No need to tie break on ord, for the case where the same doc has the same value in a given dimension indexed more than once: it
+ // can't matter at search time since we don't write ords into the index:
+ new MSBRadixSorter(bytesPerDim + Integer.BYTES) {
@Override
- protected void setPivot(int i) {
- pivotDocID = writer.docIDs[i];
- int block = i / writer.valuesPerBlock;
- int index = i % writer.valuesPerBlock;
- System.arraycopy(writer.blocks.get(block), index*packedBytesLength+dim*bytesPerDim, pivotPackedValue, 0, bytesPerDim);
- }
-
- @Override
- protected int comparePivot(int j) {
- //cmpCount[0]++;
- int block = j / writer.valuesPerBlock;
- int index = j % writer.valuesPerBlock;
- assert index >= 0: "index=" + index + " j=" + j;
- int cmp = StringHelper.compare(bytesPerDim, pivotPackedValue, 0, writer.blocks.get(block), bytesPerDim*(index*numDims+dim));
- if (cmp != 0) {
- return cmp;
+ protected int byteAt(int i, int k) {
+ assert k >= 0;
+ if (k < bytesPerDim) {
+ // dim bytes
+ int block = i / writer.valuesPerBlock;
+ int index = i % writer.valuesPerBlock;
+ return writer.blocks.get(block)[index * packedBytesLength + dim * bytesPerDim + k] & 0xff;
+ } else {
+ // doc id
+ int s = 3 - (k - bytesPerDim);
+ return (writer.docIDs[i] >>> (s * 8)) & 0xff;
}
-
- // Tie-break
- return Integer.compare(pivotDocID, writer.docIDs[j]);
}
@Override
@@ -670,26 +657,7 @@ public class BKDWriter implements Closeable {
System.arraycopy(scratch1, 0, blockJ, indexJ, packedBytesLength);
}
- @Override
- protected int compare(int i, int j) {
- //cmpCount[0]++;
- int blockI = i / writer.valuesPerBlock;
- int dimI = i % writer.valuesPerBlock;
- int blockJ = j / writer.valuesPerBlock;
- int dimJ = j % writer.valuesPerBlock;
- int cmp = StringHelper.compare(bytesPerDim, writer.blocks.get(blockI), bytesPerDim*(dimI*numDims+dim), writer.blocks.get(blockJ), bytesPerDim*(dimJ*numDims+dim));
- if (cmp != 0) {
- return cmp;
- }
-
- // Tie-break by docID:
-
- // No need to tie break on ord, for the case where the same doc has the same value in a given dimension indexed more than once: it
- // can't matter at search time since we don't write ords into the index:
- return Integer.compare(writer.docIDs[i], writer.docIDs[j]);
- }
- }.sort(0, Math.toIntExact(pointCount));
- //System.out.println("LEN=" + length + " SWAP=" + swapCount[0] + " CMP=" + cmpCount[0]);
+ }.sort(0, pointCount);
}
private PointWriter sort(int dim) throws IOException {
@@ -724,28 +692,28 @@ public class BKDWriter implements Closeable {
final int offset = bytesPerDim * dim;
- Comparator<BytesRef> cmp = new Comparator<BytesRef>() {
-
- final ByteArrayDataInput reader = new ByteArrayDataInput();
-
- @Override
- public int compare(BytesRef a, BytesRef b) {
- // First compare by the requested dimension we are sorting by:
- int cmp = StringHelper.compare(bytesPerDim, a.bytes, a.offset + offset, b.bytes, b.offset + offset);
-
- if (cmp != 0) {
- return cmp;
+ Comparator<BytesRef> cmp;
+ if (dim == numDims - 1) {
+ // in that case the bytes for the dimension and for the doc id are contiguous,
+ // so we don't need a branch
+ cmp = new BytesRefComparator(bytesPerDim + Integer.BYTES) {
+ @Override
+ protected int byteAt(BytesRef ref, int i) {
+ return ref.bytes[ref.offset + offset + i] & 0xff;
}
-
- // Tie-break by docID ... no need to tie break on ord, for the case where the same doc has
- // the same value in a given dimension indexed more than once: it can't matter at search
- // time since we don't write ords into the index:
-
- return StringHelper.compare(Integer.BYTES,
- a.bytes, a.offset + packedBytesLength,
- b.bytes, b.offset + packedBytesLength);
- }
- };
+ };
+ } else {
+ cmp = new BytesRefComparator(bytesPerDim + Integer.BYTES) {
+ @Override
+ protected int byteAt(BytesRef ref, int i) {
+ if (i < bytesPerDim) {
+ return ref.bytes[ref.offset + offset + i] & 0xff;
+ } else {
+ return ref.bytes[ref.offset + packedBytesLength + i - bytesPerDim] & 0xff;
+ }
+ }
+ };
+ }
OfflineSorter sorter = new OfflineSorter(tempDir, tempFileNamePrefix + "_bkd" + dim, cmp, offlineSorterBufferMB, offlineSorterMaxTempFiles, bytesPerDoc) {
@@ -1272,4 +1240,5 @@ public class BKDWriter implements Closeable {
return new OfflinePointWriter(tempDir, tempFileNamePrefix, packedBytesLength, longOrds, desc, count, singleValuePerDoc);
}
}
+
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/358d6f7e/lucene/core/src/test/org/apache/lucene/util/TestMSBRadixSorter.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/test/org/apache/lucene/util/TestMSBRadixSorter.java b/lucene/core/src/test/org/apache/lucene/util/TestMSBRadixSorter.java
new file mode 100644
index 0000000..bc5af7f
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/util/TestMSBRadixSorter.java
@@ -0,0 +1,117 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.util;
+
+import java.util.Arrays;
+
+public class TestMSBRadixSorter extends LuceneTestCase {
+
+ private void test(BytesRef[] refs, int len) {
+ BytesRef[] expected = Arrays.copyOf(refs, len);
+ Arrays.sort(expected);
+
+ int maxLength = 0;
+ for (int i = 0; i < len; ++i) {
+ BytesRef ref = refs[i];
+ maxLength = Math.max(maxLength, ref.length);
+ }
+ switch (random().nextInt(3)) {
+ case 0:
+ maxLength += TestUtil.nextInt(random(), 1, 5);
+ break;
+ case 1:
+ maxLength = Integer.MAX_VALUE;
+ break;
+ default:
+ // leave unchanged
+ break;
+ }
+
+ new MSBRadixSorter(maxLength) {
+
+ protected int byteAt(int i, int k) {
+ BytesRef ref = refs[i];
+ if (ref.length <= k) {
+ return -1;
+ }
+ return ref.bytes[ref.offset + k] & 0xff;
+ }
+
+ @Override
+ protected void swap(int i, int j) {
+ BytesRef tmp = refs[i];
+ refs[i] = refs[j];
+ refs[j] = tmp;
+ }
+ }.sort(0, len);
+ BytesRef[] actual = Arrays.copyOf(refs, len);
+ assertArrayEquals(expected, actual);
+ }
+
+ public void testEmpty() {
+ test(new BytesRef[random().nextInt(5)], 0);
+ }
+
+ public void testOneValue() {
+ BytesRef bytes = new BytesRef(TestUtil.randomSimpleString(random()));
+ test(new BytesRef[] { bytes }, 1);
+ }
+
+ public void testTwoValues() {
+ BytesRef bytes1 = new BytesRef(TestUtil.randomSimpleString(random()));
+ BytesRef bytes2 = new BytesRef(TestUtil.randomSimpleString(random()));
+ test(new BytesRef[] { bytes1, bytes2 }, 2);
+ }
+
+ private void testRandom(int commonPrefixLen, int maxLen) {
+ byte[] commonPrefix = new byte[commonPrefixLen];
+ random().nextBytes(commonPrefix);
+ final int len = random().nextInt(100000);
+ BytesRef[] bytes = new BytesRef[len + random().nextInt(50)];
+ for (int i = 0; i < len; ++i) {
+ byte[] b = new byte[commonPrefixLen + random().nextInt(maxLen)];
+ random().nextBytes(b);
+ System.arraycopy(commonPrefix, 0, b, 0, commonPrefixLen);
+ bytes[i] = new BytesRef(b);
+ }
+ test(bytes, len);
+ }
+
+ public void testRandom() {
+ for (int iter = 0; iter < 10; ++iter) {
+ testRandom(0, 10);
+ }
+ }
+
+ public void testRandomWithLotsOfDuplicates() {
+ for (int iter = 0; iter < 10; ++iter) {
+ testRandom(0, 2);
+ }
+ }
+
+ public void testRandomWithSharedPrefix() {
+ for (int iter = 0; iter < 10; ++iter) {
+ testRandom(TestUtil.nextInt(random(), 1, 30), 10);
+ }
+ }
+
+ public void testRandomWithSharedPrefixAndLotsOfDuplicates() {
+ for (int iter = 0; iter < 10; ++iter) {
+ testRandom(TestUtil.nextInt(random(), 1, 30), 2);
+ }
+ }
+}