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);
}