gf2121 commented on code in PR #12800: URL: https://github.com/apache/lucene/pull/12800#discussion_r1400210595
########## lucene/core/src/java/org/apache/lucene/util/BaseLSBRadixSorter.java: ########## @@ -0,0 +1,122 @@ +/* + * 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 fixed-length objects. This class sorts based on the least significant byte first + * and falls back to {@link #insertionSort} when the size to sort is small. + * + * <p>This algorithm is stable. + * + * @lucene.internal + */ +public abstract class BaseLSBRadixSorter extends Sorter { + + private static final int HISTOGRAM_SIZE = 256; + private final int[] histogram = new int[HISTOGRAM_SIZE]; + protected int bits = -1; + + protected BaseLSBRadixSorter(int bits) { + super(); + this.bits = bits; + } + + @Override + public void sort(int from, int to) { + if (to - from < INSERTION_SORT_THRESHOLD) { + insertionSort(from, to); + } else { + radixSort(from, to); + } + } + + private void radixSort(int from, int to) { + for (int shift = 0; shift < bits; shift += 8) { + if (sort(from, to, histogram, shift)) { + switchBuffer(); + } + } + restore(from, to); + } + + private boolean sort(int from, int to, int[] histogram, int shift) { + Arrays.fill(histogram, 0); + buildHistogram(from, to, histogram, shift); + if (histogram[0] == to - from) { + return false; + } + sumHistogram(histogram); + reorder(from, to, histogram, shift); + return true; + } + + 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; + } + } + + /** + * Build histogram with specified shift. Implementations should witten like: + * + * <pre>{@code + * protected void buildHistogram(int from, int to, int[] histogram, int shift) { Review Comment: When run jmh i find that the low level abstractions like `bucket` and `save` decreased the performance 4-5x when there are more than one implementations in single JVM. So i pull up the abstraction layer here. -- 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: issues-unsubscr...@lucene.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org For additional commands, e-mail: issues-h...@lucene.apache.org
