| /* | |
| * Copyright 2015 Goldman Sachs. | |
| * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved. | |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. | |
| * | |
| * This code is free software; you can redistribute it and/or modify it | |
| * under the terms of the GNU General Public License version 2 only, as | |
| * published by the Free Software Foundation. | |
| * | |
| * This code is distributed in the hope that it will be useful, but WITHOUT | |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| * version 2 for more details (a copy is included in the LICENSE file that | |
| * accompanied this code). | |
| * | |
| * You should have received a copy of the GNU General Public License version | |
| * 2 along with this work; if not, write to the Free Software Foundation, | |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
| * | |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA | |
| * or visit www.oracle.com if you need additional information or have any | |
| * questions. | |
| */ | |
| import org.openjdk.jmh.annotations.Benchmark; | |
| import org.openjdk.jmh.annotations.BenchmarkMode; | |
| import org.openjdk.jmh.annotations.Measurement; | |
| import org.openjdk.jmh.annotations.Mode; | |
| import org.openjdk.jmh.annotations.OutputTimeUnit; | |
| import org.openjdk.jmh.annotations.Param; | |
| import org.openjdk.jmh.annotations.Scope; | |
| import org.openjdk.jmh.annotations.Setup; | |
| import org.openjdk.jmh.annotations.State; | |
| import org.openjdk.jmh.annotations.Warmup; | |
| import java.util.ArrayList; | |
| import java.util.Arrays; | |
| import java.util.HashSet; | |
| import java.util.List; | |
| import java.util.Random; | |
| import java.util.Set; | |
| import java.util.concurrent.TimeUnit; | |
| @State(Scope.Thread) | |
| @BenchmarkMode(Mode.Throughput) | |
| @OutputTimeUnit(TimeUnit.SECONDS) | |
| public class SortingIntBenchmarkTestJMH { | |
| private static final int QUICKSORT_THRESHOLD = 286; | |
| private static final int MAX_RUN_COUNT = 67; | |
| private static final int INSERTION_SORT_THRESHOLD = 47; | |
| public static final int MAX_VALUE = 1_000_000; | |
| @Param({"pairFlipZeroPairFlip", "pairFlipOneHundredPairFlip" | |
| , "zeroHi", "hiZeroLow", "hiFlatLow", "identical", | |
| "randomDups", "randomNoDups", "sortedReversedSorted", "pairFlip", "endLessThan"}) | |
| public String listType; | |
| private int[] array; | |
| private static final int LIST_SIZE = 10_000_000; | |
| public static final int NUMBER_OF_ITERATIONS = 10; | |
| @Setup | |
| public void setUp() { | |
| Random random = new Random(123456789012345L); | |
| this.array = new int[LIST_SIZE]; | |
| int threeQuarters = (int) (LIST_SIZE * 0.75); | |
| if ("zeroHi".equals(this.listType)) { | |
| for (int i = 0; i < threeQuarters; i++) { | |
| this.array[i] = 0; | |
| } | |
| int k = 1; | |
| for (int i = threeQuarters; i < LIST_SIZE; i++) { | |
| this.array[i] = k; | |
| k++; | |
| } | |
| } | |
| else if ("hiFlatLow".equals(this.listType)) { | |
| int oneThird = LIST_SIZE / 3; | |
| for (int i = 0; i < oneThird; i++) { | |
| this.array[i] = i; | |
| } | |
| int twoThirds = oneThird * 2; | |
| int constant = oneThird - 1; | |
| for (int i = oneThird; i < twoThirds; i++) { | |
| this.array[i] = constant; | |
| } | |
| for (int i = twoThirds; i < LIST_SIZE; i++) { | |
| this.array[i] = constant - i + twoThirds; | |
| } | |
| } | |
| else if ("hiZeroLow".equals(this.listType)) { | |
| int oneThird = LIST_SIZE / 3; | |
| for (int i = 0; i < oneThird; i++) { | |
| this.array[i] = i; | |
| } | |
| int twoThirds = oneThird * 2; | |
| for (int i = oneThird; i < twoThirds; i++) { | |
| this.array[i] = 0; | |
| } | |
| for (int i = twoThirds; i < LIST_SIZE; i++) { | |
| this.array[i] = oneThird - i + twoThirds; | |
| } | |
| } | |
| else if ("identical".equals(this.listType)) { | |
| for (int i = 0; i < LIST_SIZE; i++) { | |
| this.array[i] = 0; | |
| } | |
| } | |
| else if ("randomDups".equals(this.listType)) { | |
| for (int i = 0; i < LIST_SIZE; i++) { | |
| this.array[i] = random.nextInt(1000); | |
| } | |
| } | |
| else if ("randomNoDups".equals(this.listType)) { | |
| Set<Integer> set = new HashSet(); | |
| while (set.size() < LIST_SIZE + 1) { | |
| set.add(random.nextInt()); | |
| } | |
| List<Integer> list = new ArrayList<>(LIST_SIZE); | |
| list.addAll(set); | |
| for (int i = 0; i < LIST_SIZE; i++) { | |
| this.array[i] = list.get(i); | |
| } | |
| } | |
| else if ("sortedReversedSorted".equals(this.listType)) { | |
| for (int i = 0; i < LIST_SIZE / 2; i++) { | |
| this.array[i] = i; | |
| } | |
| int num = 0; | |
| for (int i = LIST_SIZE / 2; i < LIST_SIZE; i++) { | |
| this.array[i] = LIST_SIZE - num; | |
| num++; | |
| } | |
| } | |
| else if ("pairFlip".equals(this.listType)) { | |
| for (int i = 0; i < LIST_SIZE; i++) { | |
| this.array[i] = i; | |
| } | |
| for (int i = 0; i < LIST_SIZE; i += 2) { | |
| int temp = this.array[i]; | |
| this.array[i] = this.array[i + 1]; | |
| this.array[i + 1] = temp; | |
| } | |
| } | |
| else if ("endLessThan".equals(this.listType)) { | |
| for (int i = 0; i < LIST_SIZE - 1; i++) { | |
| this.array[i] = 3; | |
| } | |
| this.array[LIST_SIZE - 1] = 1; | |
| } | |
| else if ("pairFlipZeroPairFlip".equals(this.listType)) { | |
| //pairflip | |
| for (int i = 0; i < 64; i++) { | |
| this.array[i] = i; | |
| } | |
| for (int i = 0; i < 64; i += 2) { | |
| int temp = this.array[i]; | |
| this.array[i] = this.array[i + 1]; | |
| this.array[i + 1] = temp; | |
| } | |
| //zero | |
| for (int i = 64; i < this.array.length - 64; i++) { | |
| this.array[i] = 0; | |
| } | |
| //pairflip | |
| for (int i = this.array.length - 64; i < this.array.length; i++) { | |
| this.array[i] = i; | |
| } | |
| for (int i = this.array.length - 64; i < this.array.length; i += 2) { | |
| int temp = this.array[i]; | |
| this.array[i] = this.array[i + 1]; | |
| this.array[i + 1] = temp; | |
| } | |
| } | |
| else if ("pairFlipOneHundredPairFlip".equals(this.listType)) { | |
| //10, 5 | |
| for (int i = 0; i < 64; i++) { | |
| if (i % 2 == 0) { | |
| this.array[i] = 10; | |
| } | |
| else { | |
| this.array[i] = 5; | |
| } | |
| } | |
| //100 | |
| for (int i = 64; i < this.array.length - 64; i++) { | |
| this.array[i] = 100; | |
| } | |
| //10, 5 | |
| for (int i = this.array.length - 64; i < this.array.length; i++) { | |
| if (i % 2 == 0) { | |
| this.array[i] = 10; | |
| } | |
| else { | |
| this.array[i] = 5; | |
| } | |
| } | |
| } | |
| } | |
| @Warmup(iterations = 20) | |
| @Measurement(iterations = 10) | |
| @Benchmark | |
| public void sortNewWay() { | |
| for (int i = 0; i < NUMBER_OF_ITERATIONS; i++) { | |
| SortingIntTestJMH.sort(this.array, 0, this.array.length - 1, null, 0, 0); | |
| } | |
| } | |
| @Warmup(iterations = 20) | |
| @Measurement(iterations = 10) | |
| @Benchmark | |
| public void sortCurrentWay() { | |
| for (int i = 0; i < NUMBER_OF_ITERATIONS; i++) { | |
| Arrays.sort(this.array); | |
| } | |
| } | |
| static void sort(int[] a, int left, int right, | |
| int[] work, int workBase, int workLen) { | |
| // Use Quicksort on small arrays | |
| if (right - left < QUICKSORT_THRESHOLD) { | |
| SortingIntTestJMH.sort(a, left, right, true); | |
| return; | |
| } | |
| /* | |
| * Index run[i] is the start of i-th run | |
| * (ascending or descending sequence). | |
| */ | |
| int[] run = new int[MAX_RUN_COUNT + 1]; | |
| int count = 0; | |
| run[0] = left; | |
| // Check if the array is nearly sorted | |
| for (int k = left; k < right; run[count] = k) { | |
| while (k < right && a[k] == a[k + 1]) | |
| k++; | |
| if (k == right) break; | |
| if (a[k] < a[k + 1]) { // ascending | |
| while (++k <= right && a[k - 1] <= a[k]) ; | |
| } | |
| else if (a[k] > a[k + 1]) { // descending | |
| while (++k <= right && a[k - 1] >= a[k]) ; | |
| for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) { | |
| int t = a[lo]; | |
| a[lo] = a[hi]; | |
| a[hi] = t; | |
| } | |
| } | |
| if (run[count] > left && a[run[count]] >= a[run[count] - 1]) { | |
| count--; | |
| } | |
| /* | |
| * The array is not highly structured, | |
| * use Quicksort instead of merge sort. | |
| */ | |
| if (++count == MAX_RUN_COUNT) { | |
| sort(a, left, right, true); | |
| return; | |
| } | |
| } | |
| // Check special cases | |
| // Implementation note: variable "right" is increased by 1. | |
| if (run[count] == right++) { | |
| run[++count] = right; | |
| } | |
| if (count <= 1) { // The array is already sorted | |
| return; | |
| } | |
| // Determine alternation base for merge | |
| byte odd = 0; | |
| for (int n = 1; (n <<= 1) < count; odd ^= 1) { | |
| } | |
| // Use or create temporary array b for merging | |
| int[] b; // temp array; alternates with a | |
| int ao, bo; // array offsets from 'left' | |
| int blen = right - left; // space needed for b | |
| if (work == null || workLen < blen || workBase + blen > work.length) { | |
| work = new int[blen]; | |
| workBase = 0; | |
| } | |
| if (odd == 0) { | |
| System.arraycopy(a, left, work, workBase, blen); | |
| b = a; | |
| bo = 0; | |
| a = work; | |
| ao = workBase - left; | |
| } | |
| else { | |
| b = work; | |
| ao = 0; | |
| bo = workBase - left; | |
| } | |
| // Merging | |
| for (int last; count > 1; count = last) { | |
| for (int k = (last = 0) + 2; k <= count; k += 2) { | |
| int hi = run[k], mi = run[k - 1]; | |
| for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) { | |
| if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) { | |
| b[i + bo] = a[p++ + ao]; | |
| } | |
| else { | |
| b[i + bo] = a[q++ + ao]; | |
| } | |
| } | |
| run[++last] = hi; | |
| } | |
| if ((count & 1) != 0) { | |
| for (int i = right, lo = run[count - 1]; --i >= lo; | |
| b[i + bo] = a[i + ao] | |
| ) { | |
| } | |
| run[++last] = right; | |
| } | |
| int[] t = a; | |
| a = b; | |
| b = t; | |
| int o = ao; | |
| ao = bo; | |
| bo = o; | |
| } | |
| } | |
| private static void sort(int[] a, int left, int right, boolean leftmost) { | |
| int length = right - left + 1; | |
| // Use insertion sort on tiny arrays | |
| if (length < INSERTION_SORT_THRESHOLD) { | |
| if (leftmost) { | |
| /* | |
| * Traditional (without sentinel) insertion sort, | |
| * optimized for server VM, is used in case of | |
| * the leftmost part. | |
| */ | |
| for (int i = left, j = i; i < right; j = ++i) { | |
| int ai = a[i + 1]; | |
| while (ai < a[j]) { | |
| a[j + 1] = a[j]; | |
| if (j-- == left) { | |
| break; | |
| } | |
| } | |
| a[j + 1] = ai; | |
| } | |
| } | |
| else { | |
| /* | |
| * Skip the longest ascending sequence. | |
| */ | |
| do { | |
| if (left >= right) { | |
| return; | |
| } | |
| } | |
| while (a[++left] >= a[left - 1]); | |
| /* | |
| * Every element from adjoining part plays the role | |
| * of sentinel, therefore this allows us to avoid the | |
| * left range check on each iteration. Moreover, we use | |
| * the more optimized algorithm, so called pair insertion | |
| * sort, which is faster (in the context of Quicksort) | |
| * than traditional implementation of insertion sort. | |
| */ | |
| for (int k = left; ++left <= right; k = ++left) { | |
| int a1 = a[k], a2 = a[left]; | |
| if (a1 < a2) { | |
| a2 = a1; | |
| a1 = a[left]; | |
| } | |
| while (a1 < a[--k]) { | |
| a[k + 2] = a[k]; | |
| } | |
| a[++k + 1] = a1; | |
| while (a2 < a[--k]) { | |
| a[k + 1] = a[k]; | |
| } | |
| a[k + 1] = a2; | |
| } | |
| int last = a[right]; | |
| while (last < a[--right]) { | |
| a[right + 1] = a[right]; | |
| } | |
| a[right + 1] = last; | |
| } | |
| return; | |
| } | |
| // Inexpensive approximation of length / 7 | |
| int seventh = (length >> 3) + (length >> 6) + 1; | |
| /* | |
| * Sort five evenly spaced elements around (and including) the | |
| * center element in the range. These elements will be used for | |
| * pivot selection as described below. The choice for spacing | |
| * these elements was empirically determined to work well on | |
| * a wide variety of inputs. | |
| */ | |
| int e3 = (left + right) >>> 1; // The midpoint | |
| int e2 = e3 - seventh; | |
| int e1 = e2 - seventh; | |
| int e4 = e3 + seventh; | |
| int e5 = e4 + seventh; | |
| // Sort these elements using insertion sort | |
| if (a[e2] < a[e1]) { | |
| int t = a[e2]; | |
| a[e2] = a[e1]; | |
| a[e1] = t; | |
| } | |
| if (a[e3] < a[e2]) { | |
| int t = a[e3]; | |
| a[e3] = a[e2]; | |
| a[e2] = t; | |
| if (t < a[e1]) { | |
| a[e2] = a[e1]; | |
| a[e1] = t; | |
| } | |
| } | |
| if (a[e4] < a[e3]) { | |
| int t = a[e4]; | |
| a[e4] = a[e3]; | |
| a[e3] = t; | |
| if (t < a[e2]) { | |
| a[e3] = a[e2]; | |
| a[e2] = t; | |
| if (t < a[e1]) { | |
| a[e2] = a[e1]; | |
| a[e1] = t; | |
| } | |
| } | |
| } | |
| if (a[e5] < a[e4]) { | |
| int t = a[e5]; | |
| a[e5] = a[e4]; | |
| a[e4] = t; | |
| if (t < a[e3]) { | |
| a[e4] = a[e3]; | |
| a[e3] = t; | |
| if (t < a[e2]) { | |
| a[e3] = a[e2]; | |
| a[e2] = t; | |
| if (t < a[e1]) { | |
| a[e2] = a[e1]; | |
| a[e1] = t; | |
| } | |
| } | |
| } | |
| } | |
| // Pointers | |
| int less = left; // The index of the first element of center part | |
| int great = right; // The index before the first element of right part | |
| if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) { | |
| /* | |
| * Use the second and fourth of the five sorted elements as pivots. | |
| * These values are inexpensive approximations of the first and | |
| * second terciles of the array. Note that pivot1 <= pivot2. | |
| */ | |
| int pivot1 = a[e2]; | |
| int pivot2 = a[e4]; | |
| /* | |
| * The first and the last elements to be sorted are moved to the | |
| * locations formerly occupied by the pivots. When partitioning | |
| * is complete, the pivots are swapped back into their final | |
| * positions, and excluded from subsequent sorting. | |
| */ | |
| a[e2] = a[left]; | |
| a[e4] = a[right]; | |
| /* | |
| * Skip elements, which are less or greater than pivot values. | |
| */ | |
| while (a[++less] < pivot1) { | |
| } | |
| while (a[--great] > pivot2) { | |
| } | |
| /* | |
| * Partitioning: | |
| * | |
| * left part center part right part | |
| * +--------------------------------------------------------------+ | |
| * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | | |
| * +--------------------------------------------------------------+ | |
| * ^ ^ ^ | |
| * | | | | |
| * less k great | |
| * | |
| * Invariants: | |
| * | |
| * all in (left, less) < pivot1 | |
| * pivot1 <= all in [less, k) <= pivot2 | |
| * all in (great, right) > pivot2 | |
| * | |
| * Pointer k is the first index of ?-part. | |
| */ | |
| outer: | |
| for (int k = less - 1; ++k <= great; ) { | |
| int ak = a[k]; | |
| if (ak < pivot1) { // Move a[k] to left part | |
| a[k] = a[less]; | |
| /* | |
| * Here and below we use "a[i] = b; i++;" instead | |
| * of "a[i++] = b;" due to performance issue. | |
| */ | |
| a[less] = ak; | |
| ++less; | |
| } | |
| else if (ak > pivot2) { // Move a[k] to right part | |
| while (a[great] > pivot2) { | |
| if (great-- == k) { | |
| break outer; | |
| } | |
| } | |
| if (a[great] < pivot1) { // a[great] <= pivot2 | |
| a[k] = a[less]; | |
| a[less] = a[great]; | |
| ++less; | |
| } | |
| else { // pivot1 <= a[great] <= pivot2 | |
| a[k] = a[great]; | |
| } | |
| /* | |
| * Here and below we use "a[i] = b; i--;" instead | |
| * of "a[i--] = b;" due to performance issue. | |
| */ | |
| a[great] = ak; | |
| --great; | |
| } | |
| } | |
| // Swap pivots into their final positions | |
| a[left] = a[less - 1]; | |
| a[less - 1] = pivot1; | |
| a[right] = a[great + 1]; | |
| a[great + 1] = pivot2; | |
| // Sort left and right parts recursively, excluding known pivots | |
| SortingIntTestJMH.sort(a, left, less - 2, leftmost); | |
| SortingIntTestJMH.sort(a, great + 2, right, false); | |
| /* | |
| * If center part is too large (comprises > 4/7 of the array), | |
| * swap internal pivot values to ends. | |
| */ | |
| if (less < e1 && e5 < great) { | |
| /* | |
| * Skip elements, which are equal to pivot values. | |
| */ | |
| while (a[less] == pivot1) { | |
| ++less; | |
| } | |
| while (a[great] == pivot2) { | |
| --great; | |
| } | |
| /* | |
| * Partitioning: | |
| * | |
| * left part center part right part | |
| * +----------------------------------------------------------+ | |
| * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | | |
| * +----------------------------------------------------------+ | |
| * ^ ^ ^ | |
| * | | | | |
| * less k great | |
| * | |
| * Invariants: | |
| * | |
| * all in (*, less) == pivot1 | |
| * pivot1 < all in [less, k) < pivot2 | |
| * all in (great, *) == pivot2 | |
| * | |
| * Pointer k is the first index of ?-part. | |
| */ | |
| outer: | |
| for (int k = less - 1; ++k <= great; ) { | |
| int ak = a[k]; | |
| if (ak == pivot1) { // Move a[k] to left part | |
| a[k] = a[less]; | |
| a[less] = ak; | |
| ++less; | |
| } | |
| else if (ak == pivot2) { // Move a[k] to right part | |
| while (a[great] == pivot2) { | |
| if (great-- == k) { | |
| break outer; | |
| } | |
| } | |
| if (a[great] == pivot1) { // a[great] < pivot2 | |
| a[k] = a[less]; | |
| /* | |
| * Even though a[great] equals to pivot1, the | |
| * assignment a[less] = pivot1 may be incorrect, | |
| * if a[great] and pivot1 are floating-point zeros | |
| * of different signs. Therefore in float and | |
| * double sorting methods we have to use more | |
| * accurate assignment a[less] = a[great]. | |
| */ | |
| a[less] = pivot1; | |
| ++less; | |
| } | |
| else { // pivot1 < a[great] < pivot2 | |
| a[k] = a[great]; | |
| } | |
| a[great] = ak; | |
| --great; | |
| } | |
| } | |
| } | |
| // Sort center part recursively | |
| SortingIntTestJMH.sort(a, less, great, false); | |
| } | |
| else { // Partitioning with one pivot | |
| /* | |
| * Use the third of the five sorted elements as pivot. | |
| * This value is inexpensive approximation of the median. | |
| */ | |
| int pivot = a[e3]; | |
| /* | |
| * Partitioning degenerates to the traditional 3-way | |
| * (or "Dutch National Flag") schema: | |
| * | |
| * left part center part right part | |
| * +-------------------------------------------------+ | |
| * | < pivot | == pivot | ? | > pivot | | |
| * +-------------------------------------------------+ | |
| * ^ ^ ^ | |
| * | | | | |
| * less k great | |
| * | |
| * Invariants: | |
| * | |
| * all in (left, less) < pivot | |
| * all in [less, k) == pivot | |
| * all in (great, right) > pivot | |
| * | |
| * Pointer k is the first index of ?-part. | |
| */ | |
| for (int k = less; k <= great; ++k) { | |
| if (a[k] == pivot) { | |
| continue; | |
| } | |
| int ak = a[k]; | |
| if (ak < pivot) { // Move a[k] to left part | |
| a[k] = a[less]; | |
| a[less] = ak; | |
| ++less; | |
| } | |
| else { // a[k] > pivot - Move a[k] to right part | |
| while (a[great] > pivot) { | |
| --great; | |
| } | |
| if (a[great] < pivot) { // a[great] <= pivot | |
| a[k] = a[less]; | |
| a[less] = a[great]; | |
| ++less; | |
| } | |
| else { // a[great] == pivot | |
| /* | |
| * Even though a[great] equals to pivot, the | |
| * assignment a[k] = pivot may be incorrect, | |
| * if a[great] and pivot are floating-point | |
| * zeros of different signs. Therefore in float | |
| * and double sorting methods we have to use | |
| * more accurate assignment a[k] = a[great]. | |
| */ | |
| a[k] = pivot; | |
| } | |
| a[great] = ak; | |
| --great; | |
| } | |
| } | |
| /* | |
| * Sort left and right parts recursively. | |
| * All elements from center part are equal | |
| * and, therefore, already sorted. | |
| */ | |
| SortingIntTestJMH.sort(a, left, less - 1, leftmost); | |
| SortingIntTestJMH.sort(a, great + 1, right, false); | |
| } | |
| } | |
| private static void swap(int[] arr, int i, int j) { | |
| int tmp = arr[i]; | |
| arr[i] = arr[j]; | |
| arr[j] = tmp; | |
| } | |
| } |