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

mmerli pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/bookkeeper.git


The following commit(s) were added to refs/heads/master by this push:
     new f65b72d54b Use mixed quick/insertion sort (#3807)
f65b72d54b is described below

commit f65b72d54bff677adb273c509d84ada7f93727a9
Author: Matteo Merli <[email protected]>
AuthorDate: Sun Feb 26 20:41:28 2023 -0800

    Use mixed quick/insertion sort (#3807)
---
 .../bookie/storage/ldb/ArrayGroupSort.java         | 96 +++++++++++++---------
 .../bookkeeper/bookie/storage/ldb/WriteCache.java  |  4 +-
 .../bookie/storage/ldb/ArraySortGroupTest.java     | 36 ++------
 .../bookkeeper/bookie/GroupSortBenchmark.java      | 11 +--
 4 files changed, 70 insertions(+), 77 deletions(-)

diff --git 
a/bookkeeper-server/src/main/java/org/apache/bookkeeper/bookie/storage/ldb/ArrayGroupSort.java
 
b/bookkeeper-server/src/main/java/org/apache/bookkeeper/bookie/storage/ldb/ArrayGroupSort.java
index 78cf3396ec..af4f3ef931 100644
--- 
a/bookkeeper-server/src/main/java/org/apache/bookkeeper/bookie/storage/ldb/ArrayGroupSort.java
+++ 
b/bookkeeper-server/src/main/java/org/apache/bookkeeper/bookie/storage/ldb/ArrayGroupSort.java
@@ -22,58 +22,61 @@ package org.apache.bookkeeper.bookie.storage.ldb;
 
 import static com.google.common.base.Preconditions.checkArgument;
 
+import lombok.experimental.UtilityClass;
+
 /**
  * Sort an array of longs, grouping the items in tuples.
  *
  * <p>Group size decides how many longs are included in the tuples and key 
size controls how many items to use for
  * comparison.
  */
+@UtilityClass
 public class ArrayGroupSort {
 
-    private final int keySize;
-    private final int groupSize;
+    private static final int INSERTION_SORT_THRESHOLD = 100;
 
-    public ArrayGroupSort(int keySize, int groupSize) {
-        checkArgument(keySize > 0);
-        checkArgument(groupSize > 0);
-        checkArgument(keySize <= groupSize, "keySize need to be less or equal 
the groupSize");
-        this.keySize = keySize;
-        this.groupSize = groupSize;
-    }
+    private static final int GROUP_SIZE = 4;
 
     public void sort(long[] array) {
         sort(array, 0, array.length);
     }
 
-    public void sort(long[] array, int offset, int length) {
-        checkArgument(length % groupSize == 0, "Array length must be multiple 
of groupSize");
-        quickSort(array, offset, (length + offset - groupSize));
+    public static void sort(long[] array, int offset, int length) {
+        checkArgument(length % GROUP_SIZE == 0, "Array length must be multiple 
of 4");
+        quickSort(array, offset, (length + offset - GROUP_SIZE));
     }
 
     ////// Private
 
-    private void quickSort(long[] array, int low, int high) {
-        if (low < high) {
-            int pivotIdx = partition(array, low, high);
-            quickSort(array, low, pivotIdx - groupSize);
-            quickSort(array, pivotIdx + groupSize, high);
+    private static void quickSort(long[] array, int low, int high) {
+        if (low >= high) {
+            return;
         }
+
+        if (high - low < INSERTION_SORT_THRESHOLD) {
+            insertionSort(array, low, high);
+            return;
+        }
+
+        int pivotIdx = partition(array, low, high);
+        quickSort(array, low, pivotIdx - GROUP_SIZE);
+        quickSort(array, pivotIdx + GROUP_SIZE, high);
     }
 
-    private int alignGroup(int count) {
-        return count - (count % groupSize);
+    private static int alignGroup(int count) {
+        return count - (count % GROUP_SIZE);
     }
 
-    private int partition(long[] array, int low, int high) {
+    private static int partition(long[] array, int low, int high) {
         int mid = low + alignGroup((high - low) / 2);
         swap(array, mid, high);
 
         int i = low;
 
-        for (int j = low; j < high; j += groupSize) {
+        for (int j = low; j < high; j += GROUP_SIZE) {
             if (isLess(array, j, high)) {
                 swap(array, j, i);
-                i += groupSize;
+                i += GROUP_SIZE;
             }
         }
 
@@ -81,26 +84,43 @@ public class ArrayGroupSort {
         return i;
     }
 
-    private void swap(long[] array, int a, int b) {
-        long tmp;
-        for (int k = 0; k < groupSize; k++) {
-            tmp = array[a + k];
-            array[a + k] = array[b + k];
-            array[b + k] = tmp;
+    private static void swap(long[] array, int a, int b) {
+        long tmp0 = array[a];
+        long tmp1 = array[a + 1];
+        long tmp2 = array[a + 2];
+        long tmp3 = array[a + 3];
+
+        array[a] = array[b];
+        array[a + 1] = array[b + 1];
+        array[a + 2] = array[b + 2];
+        array[a + 3] = array[b + 3];
+
+        array[b] = tmp0;
+        array[b + 1] = tmp1;
+        array[b + 2] = tmp2;
+        array[b + 3] = tmp3;
+    }
+
+    private static boolean isLess(long[] array, int a, int b) {
+        long a0 = array[a];
+        long b0 = array[b];
+
+        if (a0 < b0) {
+            return true;
+        } else if (a0 > b0) {
+            return false;
         }
+
+        return array[a + 1] < array[b + 1];
     }
 
-    private boolean isLess(long[] array, int idx1, int idx2) {
-        for (int i = 0; i < keySize; i++) {
-            long k1 = array[idx1 + i];
-            long k2 = array[idx2 + i];
-            if (k1 < k2) {
-                return true;
-            } else if (k1 > k2) {
-                return false;
+    private static void insertionSort(long[] a, int low, int high) {
+        for (int i = low + GROUP_SIZE; i <= high; i += GROUP_SIZE) {
+            int j = i;
+            while (j > 0 && isLess(a, j, j - GROUP_SIZE)) {
+                swap(a, j, j - GROUP_SIZE);
+                j -= GROUP_SIZE;
             }
         }
-
-        return false;
     }
 }
diff --git 
a/bookkeeper-server/src/main/java/org/apache/bookkeeper/bookie/storage/ldb/WriteCache.java
 
b/bookkeeper-server/src/main/java/org/apache/bookkeeper/bookie/storage/ldb/WriteCache.java
index 10a4a198b4..d152c6fc1d 100644
--- 
a/bookkeeper-server/src/main/java/org/apache/bookkeeper/bookie/storage/ldb/WriteCache.java
+++ 
b/bookkeeper-server/src/main/java/org/apache/bookkeeper/bookie/storage/ldb/WriteCache.java
@@ -217,8 +217,6 @@ public class WriteCache implements Closeable {
         deletedLedgers.add(ledgerId);
     }
 
-    private static final ArrayGroupSort groupSorter = new ArrayGroupSort(2, 4);
-
     public void forEach(EntryConsumer consumer) throws IOException {
         sortedEntriesLock.lock();
 
@@ -251,7 +249,7 @@ public class WriteCache implements Closeable {
             startTime = MathUtils.nowInNano();
 
             // Sort entries by (ledgerId, entryId) maintaining the 4 items 
groups
-            groupSorter.sort(sortedEntries, 0, sortedEntriesIdx);
+            ArrayGroupSort.sort(sortedEntries, 0, sortedEntriesIdx);
             if (log.isDebugEnabled()) {
                 log.debug("sorting {} ms", (MathUtils.elapsedNanos(startTime) 
/ 1e6));
             }
diff --git 
a/bookkeeper-server/src/test/java/org/apache/bookkeeper/bookie/storage/ldb/ArraySortGroupTest.java
 
b/bookkeeper-server/src/test/java/org/apache/bookkeeper/bookie/storage/ldb/ArraySortGroupTest.java
index ad1e4dc02e..94ca14fd6c 100644
--- 
a/bookkeeper-server/src/test/java/org/apache/bookkeeper/bookie/storage/ldb/ArraySortGroupTest.java
+++ 
b/bookkeeper-server/src/test/java/org/apache/bookkeeper/bookie/storage/ldb/ArraySortGroupTest.java
@@ -51,37 +51,19 @@ public class ArraySortGroupTest {
                 5, 6, 3, 1, //
         };
 
-        ArrayGroupSort sorter = new ArrayGroupSort(2, 4);
-        sorter.sort(data);
+        ArrayGroupSort.sort(data);
 
         assertArrayEquals(expectedSorted, data);
     }
 
-    @Test(expected = IllegalArgumentException.class)
-    public void keySmallerThanTotalSize() {
-        new ArrayGroupSort(3, 2);
-    }
-
-    @Test(expected = IllegalArgumentException.class)
-    public void negativeKeySize() {
-        new ArrayGroupSort(-1, 2);
-    }
-
-    @Test(expected = IllegalArgumentException.class)
-    public void negativeTotalSize() {
-        new ArrayGroupSort(1, -1);
-    }
-
     @Test(expected = IllegalArgumentException.class)
     public void arraySizeIsNotMultiple() {
-        ArrayGroupSort sorter = new ArrayGroupSort(1, 3);
-        sorter.sort(new long[] { 1, 2, 3, 4 });
+        ArrayGroupSort.sort(new long[] { 1, 2, 3, 4, 5 });
     }
 
     @Test(expected = IllegalArgumentException.class)
     public void arraySizeIsShorterThanRequired() {
-        ArrayGroupSort sorter = new ArrayGroupSort(1, 3);
-        sorter.sort(new long[] { 1, 2 });
+        ArrayGroupSort.sort(new long[] { 1, 2 });
     }
 
     @Test
@@ -90,8 +72,7 @@ public class ArraySortGroupTest {
 
         long[] expectedSorted = new long[] {};
 
-        ArrayGroupSort sorter = new ArrayGroupSort(2, 4);
-        sorter.sort(data);
+        ArrayGroupSort.sort(data);
 
         assertArrayEquals(expectedSorted, data);
     }
@@ -101,8 +82,7 @@ public class ArraySortGroupTest {
         long[] data = new long[] { 1, 2, 3, 4 };
         long[] expectedSorted = new long[] { 1, 2, 3, 4 };
 
-        ArrayGroupSort sorter = new ArrayGroupSort(2, 4);
-        sorter.sort(data);
+        ArrayGroupSort.sort(data);
 
         assertArrayEquals(expectedSorted, data);
     }
@@ -112,8 +92,7 @@ public class ArraySortGroupTest {
         long[] data = new long[] { 1, 2, 3, 4, 1, 1, 5, 5 };
         long[] expectedSorted = new long[] { 1, 1, 5, 5, 1, 2, 3, 4 };
 
-        ArrayGroupSort sorter = new ArrayGroupSort(2, 4);
-        sorter.sort(data);
+        ArrayGroupSort.sort(data);
 
         assertArrayEquals(expectedSorted, data);
     }
@@ -123,8 +102,7 @@ public class ArraySortGroupTest {
         long[] data = new long[] { 1, 2, 3, 4, 1, 1, 5, 5, 1, 0, 2, 1 };
         long[] expectedSorted = new long[] { 1, 0, 2, 1, 1, 1, 5, 5, 1, 2, 3, 
4 };
 
-        ArrayGroupSort sorter = new ArrayGroupSort(2, 4);
-        sorter.sort(data);
+        ArrayGroupSort.sort(data);
 
         assertArrayEquals(expectedSorted, data);
     }
diff --git 
a/microbenchmarks/src/main/java/org/apache/bookkeeper/bookie/GroupSortBenchmark.java
 
b/microbenchmarks/src/main/java/org/apache/bookkeeper/bookie/GroupSortBenchmark.java
index 8290e54fb4..8df5691ae7 100644
--- 
a/microbenchmarks/src/main/java/org/apache/bookkeeper/bookie/GroupSortBenchmark.java
+++ 
b/microbenchmarks/src/main/java/org/apache/bookkeeper/bookie/GroupSortBenchmark.java
@@ -54,9 +54,6 @@ public class GroupSortBenchmark {
 
         private long[] items;
 
-
-        private final ArrayGroupSort sorter = new ArrayGroupSort(2, 4);
-
         public TestState() {
             Random r = new Random();
             for (int i = 0; i < (N * 4); i++) {
@@ -64,7 +61,7 @@ public class GroupSortBenchmark {
             }
 
             groupSortedItems = Arrays.copyOf(randomItems, randomItems.length);
-            sorter.sort(groupSortedItems);
+            ArrayGroupSort.sort(groupSortedItems);
             for (int i = 0; i < (N * 4); i += 4) {
                 reverseGroupSortedItems[i] = groupSortedItems[(N - 1) * 4 - i];
                 reverseGroupSortedItems[i + 1] = groupSortedItems[(N - 1) * 4 
- i + 1];
@@ -87,7 +84,7 @@ public class GroupSortBenchmark {
 
     @Benchmark
     public void randomGroupSort(GroupSortBenchmark.TestState s) {
-        s.sorter.sort(s.items);
+        ArrayGroupSort.sort(s.items);
     }
 
 
@@ -99,7 +96,7 @@ public class GroupSortBenchmark {
 
     @Benchmark
     public void preSortedGroupSort(GroupSortBenchmark.TestState s) {
-        s.sorter.sort(s.groupSortedItems);
+        ArrayGroupSort.sort(s.groupSortedItems);
     }
 
 
@@ -110,7 +107,7 @@ public class GroupSortBenchmark {
 
     @Benchmark
     public void reverseSortedGroupSort(GroupSortBenchmark.TestState s) {
-        s.sorter.sort(s.reverseGroupSortedItems);
+        ArrayGroupSort.sort(s.reverseGroupSortedItems);
     }
 
 

Reply via email to