[lucene] branch main updated: Use MergeSorter in StableStringSorter (#12652)

[gu...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

guofeng pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git


The following commit(s) were added to refs/heads/main by this push:
     new da032535d60 Use MergeSorter in StableStringSorter (#12652)
da032535d60 is described below

commit da032535d6065da18c3463c956093bce081afb6e
Author: gf2121 <52...@users.noreply.github.com>
AuthorDate: Tue Oct 17 17:52:16 2023 +0800

    Use MergeSorter in StableStringSorter (#12652)
---
 .../org/apache/lucene/util/StableMSBRadixSorter.java | 20 +++++++++++++++++++-
 .../org/apache/lucene/util/StableStringSorter.java   | 12 +++++++++++-
 2 files changed, 30 insertions(+), 2 deletions(-)

diff --git a/lucene/core/src/java/org/apache/lucene/util/StableMSBRadixSorter.java b/lucene/core/src/java/org/apache/lucene/util/StableMSBRadixSorter.java
index ecccbc58f53..ed9d810d925 100644
--- a/lucene/core/src/java/org/apache/lucene/util/StableMSBRadixSorter.java
+++ b/lucene/core/src/java/org/apache/lucene/util/StableMSBRadixSorter.java
@@ -39,6 +39,16 @@ public abstract class StableMSBRadixSorter extends MSBRadixSorter {
   @Override
   protected Sorter getFallbackSorter(int k) {
     return new MergeSorter() {
+      @Override
+      protected void save(int i, int j) {
+        StableMSBRadixSorter.this.save(i, j);
+      }
+
+      @Override
+      protected void restore(int i, int j) {
+        StableMSBRadixSorter.this.restore(i, j);
+      }
+
       @Override
       protected void swap(int i, int j) {
         StableMSBRadixSorter.this.swap(i, j);
@@ -80,7 +90,7 @@ public abstract class StableMSBRadixSorter extends MSBRadixSorter {
   }
 
   /** A MergeSorter taking advantage of temporary storage. */
-  protected abstract class MergeSorter extends Sorter {
+  protected abstract static class MergeSorter extends Sorter {
     @Override
     public void sort(int from, int to) {
       checkRange(from, to);
@@ -98,6 +108,14 @@ public abstract class StableMSBRadixSorter extends MSBRadixSorter {
       }
     }
 
+    /** Save the i-th value into the j-th position in temporary storage. */
+    protected abstract void save(int i, int j);
+
+    /**
+     * Restore values between i-th and j-th(excluding) in temporary storage into original storage.
+     */
+    protected abstract void restore(int i, int j);
+
     /**
      * We tried to expose this to implementations to get a bulk copy optimization. But it did not
      * bring a noticeable improvement in benchmark as {@code len} is usually small.
diff --git a/lucene/core/src/java/org/apache/lucene/util/StableStringSorter.java b/lucene/core/src/java/org/apache/lucene/util/StableStringSorter.java
index 067a72e8084..9d08ade563f 100644
--- a/lucene/core/src/java/org/apache/lucene/util/StableStringSorter.java
+++ b/lucene/core/src/java/org/apache/lucene/util/StableStringSorter.java
@@ -65,7 +65,17 @@ abstract class StableStringSorter extends StringSorter {
   @Override
   protected Sorter fallbackSorter(Comparator<BytesRef> cmp) {
     // TODO: Maybe tim sort is better?
-    return new InPlaceMergeSorter() {
+    return new StableMSBRadixSorter.MergeSorter() {
+      @Override
+      protected void save(int i, int j) {
+        StableStringSorter.this.save(i, j);
+      }
+
+      @Override
+      protected void restore(int i, int j) {
+        StableStringSorter.this.restore(i, j);
+      }
+
       @Override
       protected int compare(int i, int j) {
         return StableStringSorter.this.compare(i, j);