gf2121 commented on code in PR #12712:
URL: https://github.com/apache/lucene/pull/12712#discussion_r1370377164
##########
lucene/misc/src/java/org/apache/lucene/misc/index/BPIndexReorderer.java:
##########
@@ -991,4 +939,233 @@ static int readMonotonicInts(DataInput in, int[] ints)
throws IOException {
}
return len;
}
+
+ static class ForwardIndexSorter {
+
+ private static final int HISTOGRAM_SIZE = 256;
+ private static final int BUFFER_SIZE = 8192;
+ private static final int BUFFER_BYTES = BUFFER_SIZE * Long.BYTES;
+ private final Directory directory;
+ private final Bucket[] buckets = new Bucket[HISTOGRAM_SIZE];
+ private final double ramBudgetMB;
+
+ /** Fork of {@link org.apache.lucene.util.LSBRadixSorter} to sort longs. */
+ private static class MemorySorter {
+ private final int[] histogram = new int[HISTOGRAM_SIZE];
+
+ private static void buildHistogram(long[] array, int len, int[]
histogram, int shift) {
+ for (int i = 0; i < len; ++i) {
+ final int b = (int) ((array[i] >>> shift) & 0xFFL);
+ histogram[b] += 1;
+ }
+ }
+
+ private static void sumHistogram(int[] histogram) {
+ int accum = 0;
+ for (int i = 0; i < HISTOGRAM_SIZE; ++i) {
+ final int count = histogram[i];
+ histogram[i] = accum;
+ accum += count;
+ }
+ }
+
+ private static void reorder(long[] array, int len, int[] histogram, int
shift, long[] dest) {
+ for (int i = 0; i < len; ++i) {
+ final long v = array[i];
+ final int b = (int) ((v >>> shift) & 0xFF);
+ dest[histogram[b]++] = v;
+ }
+ }
+
+ private static boolean sort(long[] array, int len, int[] histogram, int
shift, long[] dest) {
+ Arrays.fill(histogram, 0);
+ buildHistogram(array, len, histogram, shift);
+ if (histogram[0] == len) {
+ return false;
+ }
+ sumHistogram(histogram);
+ reorder(array, len, histogram, shift, dest);
+ return true;
+ }
+
+ public void sortAndConsume(int numBits, long[] array, int len,
LongConsumer consumer)
+ throws IOException {
+ long[] buffer = new long[len];
+ for (int shift = 0; shift < numBits; shift += 8) {
+ if (sort(array, len, histogram, shift, buffer)) {
+ // swap arrays
+ long[] tmp = array;
+ array = buffer;
+ buffer = tmp;
+ }
+ }
+ for (int i = 0; i < len; i++) {
+ consumer.accept(array[i]);
+ }
+ consumer.onFinish();
+ }
+ }
+
+ private static class Bucket {
+ int bufferUsed;
+ int blockNum;
+ long lastFp;
+ final ByteBuffersDataOutput fps = new ByteBuffersDataOutput();
+ final long[] buffer = new long[BUFFER_SIZE];
+ int finalBlockSize;
+
+ void addEntry(long l, IndexOutput output) throws IOException {
Review Comment:
I like it too!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
