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 7f263fa8f4 Fixed the pivot selection in the group quick-sort (#3800)
7f263fa8f4 is described below
commit 7f263fa8f41924ef0996f84beffdf008480075d8
Author: Matteo Merli <[email protected]>
AuthorDate: Sun Feb 26 17:00:02 2023 -0800
Fixed the pivot selection in the group quick-sort (#3800)
* Fixed the pivot selection in the group quick-sort
* Fixed formatting
* Fixed alignment
---
.../bookie/storage/ldb/ArrayGroupSort.java | 10 +-
.../bookkeeper/bookie/GroupSortBenchmark.java | 121 +++++++++++++++++++++
2 files changed, 129 insertions(+), 2 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 27874e1c8c..78cf3396ec 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
@@ -60,12 +60,18 @@ public class ArrayGroupSort {
}
}
+ private int alignGroup(int count) {
+ return count - (count % groupSize);
+ }
+
private int partition(long[] array, int low, int high) {
- int pivotIdx = high;
+ int mid = low + alignGroup((high - low) / 2);
+ swap(array, mid, high);
+
int i = low;
for (int j = low; j < high; j += groupSize) {
- if (isLess(array, j, pivotIdx)) {
+ if (isLess(array, j, high)) {
swap(array, j, i);
i += groupSize;
}
diff --git
a/microbenchmarks/src/main/java/org/apache/bookkeeper/bookie/GroupSortBenchmark.java
b/microbenchmarks/src/main/java/org/apache/bookkeeper/bookie/GroupSortBenchmark.java
new file mode 100644
index 0000000000..8290e54fb4
--- /dev/null
+++
b/microbenchmarks/src/main/java/org/apache/bookkeeper/bookie/GroupSortBenchmark.java
@@ -0,0 +1,121 @@
+/*
+ *
+ * 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.bookkeeper.bookie;
+
+import java.util.Arrays;
+import java.util.Random;
+import java.util.concurrent.TimeUnit;
+import org.apache.bookkeeper.bookie.storage.ldb.ArrayGroupSort;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Warmup;
+
+@OutputTimeUnit(TimeUnit.SECONDS)
+@Fork(1)
+@Warmup(iterations = 1, time = 10)
+@Measurement(iterations = 3, time = 10)
+public class GroupSortBenchmark {
+
+ private static final int N = 10_000;
+
+ @State(Scope.Benchmark)
+ public static class TestState {
+
+ private final long[] randomItems = new long[N * 4];
+ private final long[] sortedItems;
+ private final long[] reverseSortedItems = new long[N * 4];
+ private final long[] groupSortedItems;
+ private final long[] reverseGroupSortedItems = new long[N * 4];
+
+ 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++) {
+ randomItems[i] = r.nextLong();
+ }
+
+ groupSortedItems = Arrays.copyOf(randomItems, randomItems.length);
+ sorter.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];
+ reverseGroupSortedItems[i + 2] = groupSortedItems[(N - 1) * 4
- i + 2];
+ reverseGroupSortedItems[i + 3] = groupSortedItems[(N - 1) * 4
- i + 3];
+ }
+
+ sortedItems = Arrays.copyOf(randomItems, randomItems.length);
+ Arrays.sort(sortedItems);
+ for (int i = 0; i < (N * 4); i++) {
+ reverseSortedItems[i] = sortedItems[N * 4 - 1 - i];
+ }
+ }
+
+ @Setup(Level.Invocation)
+ public void setupInvocation() {
+ items = Arrays.copyOf(randomItems, randomItems.length);
+ }
+ }
+
+ @Benchmark
+ public void randomGroupSort(GroupSortBenchmark.TestState s) {
+ s.sorter.sort(s.items);
+ }
+
+
+ @Benchmark
+ public void randomArraySort(GroupSortBenchmark.TestState s) {
+ Arrays.sort(s.items);
+ }
+
+
+ @Benchmark
+ public void preSortedGroupSort(GroupSortBenchmark.TestState s) {
+ s.sorter.sort(s.groupSortedItems);
+ }
+
+
+ @Benchmark
+ public void preSortedArraySort(GroupSortBenchmark.TestState s) {
+ Arrays.sort(s.sortedItems);
+ }
+
+ @Benchmark
+ public void reverseSortedGroupSort(GroupSortBenchmark.TestState s) {
+ s.sorter.sort(s.reverseGroupSortedItems);
+ }
+
+
+ @Benchmark
+ public void reverseSortedArraySort(GroupSortBenchmark.TestState s) {
+ Arrays.sort(s.reverseSortedItems);
+ }
+}