1/* 2 * Copyright 2015 Goldman Sachs. 3 * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved. 4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 5 * 6 * This code is free software; you can redistribute it and/or modify it 7 * under the terms of the GNU General Public License version 2 only, as 8 * published by the Free Software Foundation. 9 * 10 * This code is distributed in the hope that it will be useful, but WITHOUT 11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 13 * version 2 for more details (a copy is included in the LICENSE file that 14 * accompanied this code). 15 * 16 * You should have received a copy of the GNU General Public License version 17 * 2 along with this work; if not, write to the Free Software Foundation, 18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 19 * 20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 21 * or visit www.oracle.com if you need additional information or have any 22 * questions. 23 */ 24 25import org.openjdk.jmh.annotations.Benchmark; 26import org.openjdk.jmh.annotations.BenchmarkMode; 27import org.openjdk.jmh.annotations.Measurement; 28import org.openjdk.jmh.annotations.Mode; 29import org.openjdk.jmh.annotations.OutputTimeUnit; 30import org.openjdk.jmh.annotations.Param; 31import org.openjdk.jmh.annotations.Scope; 32import org.openjdk.jmh.annotations.Setup; 33import org.openjdk.jmh.annotations.State; 34import org.openjdk.jmh.annotations.Warmup; 35 36import java.util.ArrayList; 37import java.util.Arrays; 38import java.util.HashSet; 39import java.util.List; 40import java.util.Random; 41import java.util.Set; 42import java.util.concurrent.TimeUnit; 43 44@State(Scope.Thread) 45@BenchmarkMode(Mode.Throughput) 46@OutputTimeUnit(TimeUnit.SECONDS) 47public class SortingLongBenchmarkTestJMH { 48 private static final int QUICKSORT_THRESHOLD = 286; 49 private static final int MAX_RUN_COUNT = 67; 50 private static final int INSERTION_SORT_THRESHOLD = 47; 51 public static final int MAX_VALUE = 1_000_000; 52 53 @Param({"pairFlipZeroPairFlip", "descendingAscending", "zeroHi", "hiZeroLow", "hiFlatLow", "identical", 54 "randomDups", "randomNoDups", "sortedReversedSorted", "pairFlip", "endLessThan"}) 55 public String listType; 56 57 private long[] array; 58 private static final int LIST_SIZE = 10_000_000; 59 public static final int NUMBER_OF_ITERATIONS = 10; 60 61 @Setup 62 public void setUp() { 63 Random random = new Random(123456789012345L); 64 this.array = new long[LIST_SIZE]; 65 int threeQuarters = (int) (LIST_SIZE * 0.75); 66 if ("zeroHi".equals(this.listType)) { 67 for (int i = 0; i < threeQuarters; i++) { 68 this.array[i] = 0; 69 } 70 int k = 1; 71 for (int i = threeQuarters; i < LIST_SIZE; i++) { 72 this.array[i] = k; 73 k++; 74 } 75 } 76 else if ("hiFlatLow".equals(this.listType)) { 77 int oneThird = LIST_SIZE / 3; 78 for (int i = 0; i < oneThird; i++) { 79 this.array[i] = i; 80 } 81 int twoThirds = oneThird * 2; 82 int constant = oneThird - 1; 83 for (int i = oneThird; i < twoThirds; i++) { 84 this.array[i] = constant; 85 } 86 for (int i = twoThirds; i < LIST_SIZE; i++) { 87 this.array[i] = constant - i + twoThirds; 88 } 89 } 90 else if ("hiZeroLow".equals(this.listType)) { 91 int oneThird = LIST_SIZE / 3; 92 for (int i = 0; i < oneThird; i++) { 93 this.array[i] = i; 94 } 95 int twoThirds = oneThird * 2; 96 for (int i = oneThird; i < twoThirds; i++) { 97 this.array[i] = 0; 98 } 99 for (int i = twoThirds; i < LIST_SIZE; i++) { 100 this.array[i] = oneThird - i + twoThirds; 101 } 102 } 103 else if ("identical".equals(this.listType)) { 104 for (int i = 0; i < LIST_SIZE; i++) { 105 this.array[i] = 0; 106 } 107 } 108 else if ("randomDups".equals(this.listType)) { 109 for (int i = 0; i < LIST_SIZE; i++) { 110 this.array[i] = random.nextInt(1000); 111 } 112 } 113 else if ("randomNoDups".equals(this.listType)) { 114 Set<Integer> set = new HashSet<>(); 115 while (set.size() < LIST_SIZE + 1) { 116 set.add(random.nextInt()); 117 } 118 List<Integer> list = new ArrayList<>(LIST_SIZE); 119 list.addAll(set); 120 for (int i = 0; i < LIST_SIZE; i++) { 121 this.array[i] = list.get(i); 122 } 123 } 124 else if ("sortedReversedSorted".equals(this.listType)) { 125 for (int i = 0; i < LIST_SIZE / 2; i++) { 126 this.array[i] = i; 127 } 128 int num = 0; 129 for (int i = LIST_SIZE / 2; i < LIST_SIZE; i++) { 130 this.array[i] = LIST_SIZE - num; 131 num++; 132 } 133 } 134 else if ("pairFlip".equals(this.listType)) { 135 for (int i = 0; i < LIST_SIZE; i++) { 136 this.array[i] = i; 137 } 138 for (int i = 0; i < LIST_SIZE; i += 2) { 139 long temp = this.array[i]; 140 this.array[i] = this.array[i + 1]; 141 this.array[i + 1] = temp; 142 } 143 } 144 else if ("endLessThan".equals(this.listType)) { 145 for (int i = 0; i < LIST_SIZE - 1; i++) { 146 this.array[i] = 3; 147 } 148 this.array[LIST_SIZE - 1] = 1; 149 } 150 else if ("pairFlipZeroPairFlip".equals(this.listType)) { 151 //pairflip 152 for (int i = 0; i < 64; i++) { 153 this.array[i] = i; 154 } 155 for (int i = 0; i < 64; i += 2) { 156 long temp = this.array[i]; 157 this.array[i] = this.array[i + 1]; 158 this.array[i + 1] = temp; 159 } 160 //zero 161 for (int i = 64; i < this.array.length - 64; i++) { 162 this.array[i] = 0; 163 } 164 //pairflip 165 for (int i = this.array.length - 64; i < this.array.length; i++) { 166 this.array[i] = i; 167 } 168 for (int i = this.array.length - 64; i < this.array.length; i += 2) { 169 long temp = this.array[i]; 170 this.array[i] = this.array[i + 1]; 171 this.array[i + 1] = temp; 172 } 173 } 174 else if ("pairFlipOneHundredPairFlip".equals(this.listType)) { 175 //10, 5 176 for (int i = 0; i < 64; i++) { 177 if (i % 2 == 0) { 178 this.array[i] = 10; 179 } 180 else { 181 this.array[i] = 5; 182 } 183 } 184 185 //100 186 for (int i = 64; i < this.array.length - 64; i++) { 187 this.array[i] = 100; 188 } 189 190 //10, 5 191 for (int i = this.array.length - 64; i < this.array.length; i++) { 192 if (i % 2 == 0) { 193 this.array[i] = 10; 194 } 195 else { 196 this.array[i] = 5; 197 } 198 } 199 } 200 } 201 202 @Warmup(iterations = 20) 203 @Measurement(iterations = 10) 204 @Benchmark 205 public void sortNewWay() { 206 for (int i = 0; i < NUMBER_OF_ITERATIONS; i++) { 207 SortingLongTestJMH.sort(this.array, 0, this.array.length - 1, null, 0, 0); 208 } 209 } 210 211 @Warmup(iterations = 20) 212 @Measurement(iterations = 10) 213 @Benchmark 214 public void sortOldWay() { 215 for (int i = 0; i < NUMBER_OF_ITERATIONS; i++) { 216 Arrays.sort(this.array); 217 } 218 } 219 220 /** 221 * Sorts the specified range of the array using the given 222 * workspace array slice if possible for merging 223 * 224 * @param a the array to be sorted 225 * @param left the index of the first element, inclusive, to be sorted 226 * @param right the index of the last element, inclusive, to be sorted 227 * @param work a workspace array (slice) 228 * @param workBase origin of usable space in work array 229 * @param workLen usable size of work array 230 */ 231 static void sort(long[] a, int left, int right, 232 long[] work, int workBase, int workLen) { 233// Use Quicksort on small arrays 234 if (right - left < QUICKSORT_THRESHOLD) { 235 SortingLongTestJMH.sort(a, left, right, true); 236 return; 237 } 238 239 /* 240 * Index run[i] is the start of i-th run 241 * (ascending or descending sequence). 242 */ 243 int[] run = new int[MAX_RUN_COUNT + 1]; 244 int count = 0; 245 run[0] = left; 246 247 // Check if the array is nearly sorted 248 for (int k = left; k < right; run[count] = k) { 249 while (k < right && a[k] == a[k + 1]) 250 k++; 251 if (k == right) break; 252 if (a[k] < a[k + 1]) { // ascending 253 while (++k <= right && a[k - 1] <= a[k]) ; 254 } 255 else if (a[k] > a[k + 1]) { // descending 256 while (++k <= right && a[k - 1] >= a[k]) ; 257 for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) { 258 long t = a[lo]; 259 a[lo] = a[hi]; 260 a[hi] = t; 261 } 262 } 263 if (run[count] > left && a[run[count]] >= a[run[count] - 1]) { 264 count--; 265 } 266 /* 267 * The array is not highly structured, 268 * use Quicksort instead of merge sort. 269 */ 270 if (++count == MAX_RUN_COUNT) { 271 sort(a, left, right, true); 272 return; 273 } 274 } 275 276 // Check special cases 277 // Implementation note: variable "right" is increased by 1. 278 if (run[count] == right++) { 279 run[++count] = right; 280 } 281 if (count <= 1) { // The array is already sorted 282 return; 283 } 284 285 // Determine alternation base for merge 286 byte odd = 0; 287 for (int n = 1; (n <<= 1) < count; odd ^= 1) { 288 } 289 290 // Use or create temporary array b for merging 291 long[] b; // temp array; alternates with a 292 int ao, bo; // array offsets from 'left' 293 int blen = right - left; // space needed for b 294 if (work == null || workLen < blen || workBase + blen > work.length) { 295 work = new long[blen]; 296 workBase = 0; 297 } 298 if (odd == 0) { 299 System.arraycopy(a, left, work, workBase, blen); 300 b = a; 301 bo = 0; 302 a = work; 303 ao = workBase - left; 304 } 305 else { 306 b = work; 307 ao = 0; 308 bo = workBase - left; 309 } 310 311 // Merging 312 for (int last; count > 1; count = last) { 313 for (int k = (last = 0) + 2; k <= count; k += 2) { 314 int hi = run[k], mi = run[k - 1]; 315 for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) { 316 if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) { 317 b[i + bo] = a[p++ + ao]; 318 } 319 else { 320 b[i + bo] = a[q++ + ao]; 321 } 322 } 323 run[++last] = hi; 324 } 325 if ((count & 1) != 0) { 326 for (int i = right, lo = run[count - 1]; --i >= lo; 327 b[i + bo] = a[i + ao] 328 ) { 329 } 330 run[++last] = right; 331 } 332 long[] t = a; 333 a = b; 334 b = t; 335 int o = ao; 336 ao = bo; 337 bo = o; 338 } 339 } 340 341 /** 342 * Sorts the specified range of the array by Dual-Pivot Quicksort. 343 * 344 * @param a the array to be sorted 345 * @param left the index of the first element, inclusive, to be sorted 346 * @param right the index of the last element, inclusive, to be sorted 347 * @param leftmost indicates if this part is the leftmost in the range 348 */ 349 private static void sort(long[] a, int left, int right, boolean leftmost) { 350 int length = right - left + 1; 351 352 // Use insertion sort on tiny arrays 353 if (length < INSERTION_SORT_THRESHOLD) { 354 if (leftmost) { 355 /* 356 * Traditional (without sentinel) insertion sort, 357 * optimized for server VM, is used in case of 358 * the leftmost part. 359 */ 360 for (int i = left, j = i; i < right; j = ++i) { 361 long ai = a[i + 1]; 362 while (ai < a[j]) { 363 a[j + 1] = a[j]; 364 if (j-- == left) { 365 break; 366 } 367 } 368 a[j + 1] = ai; 369 } 370 } 371 else { 372 /* 373 * Skip the longest ascending sequence. 374 */ 375 do { 376 if (left >= right) { 377 return; 378 } 379 } 380 while (a[++left] >= a[left - 1]); 381 382 /* 383 * Every element from adjoining part plays the role 384 * of sentinel, therefore this allows us to avoid the 385 * left range check on each iteration. Moreover, we use 386 * the more optimized algorithm, so called pair insertion 387 * sort, which is faster (in the context of Quicksort) 388 * than traditional implementation of insertion sort. 389 */ 390 for (int k = left; ++left <= right; k = ++left) { 391 long a1 = a[k], a2 = a[left]; 392 393 if (a1 < a2) { 394 a2 = a1; 395 a1 = a[left]; 396 } 397 while (a1 < a[--k]) { 398 a[k + 2] = a[k]; 399 } 400 a[++k + 1] = a1; 401 402 while (a2 < a[--k]) { 403 a[k + 1] = a[k]; 404 } 405 a[k + 1] = a2; 406 } 407 long last = a[right]; 408 409 while (last < a[--right]) { 410 a[right + 1] = a[right]; 411 } 412 a[right + 1] = last; 413 } 414 return; 415 } 416 417 // Inexpensive approximation of length / 7 418 int seventh = (length >> 3) + (length >> 6) + 1; 419 420 /* 421 * Sort five evenly spaced elements around (and including) the 422 * center element in the range. These elements will be used for 423 * pivot selection as described below. The choice for spacing 424 * these elements was empirically determined to work well on 425 * a wide variety of inputs. 426 */ 427 int e3 = (left + right) >>> 1; // The midpoint 428 int e2 = e3 - seventh; 429 int e1 = e2 - seventh; 430 int e4 = e3 + seventh; 431 int e5 = e4 + seventh; 432 433 // Sort these elements using insertion sort 434 if (a[e2] < a[e1]) { 435 long t = a[e2]; 436 a[e2] = a[e1]; 437 a[e1] = t; 438 } 439 440 if (a[e3] < a[e2]) { 441 long t = a[e3]; 442 a[e3] = a[e2]; 443 a[e2] = t; 444 if (t < a[e1]) { 445 a[e2] = a[e1]; 446 a[e1] = t; 447 } 448 } 449 if (a[e4] < a[e3]) { 450 long t = a[e4]; 451 a[e4] = a[e3]; 452 a[e3] = t; 453 if (t < a[e2]) { 454 a[e3] = a[e2]; 455 a[e2] = t; 456 if (t < a[e1]) { 457 a[e2] = a[e1]; 458 a[e1] = t; 459 } 460 } 461 } 462 if (a[e5] < a[e4]) { 463 long t = a[e5]; 464 a[e5] = a[e4]; 465 a[e4] = t; 466 if (t < a[e3]) { 467 a[e4] = a[e3]; 468 a[e3] = t; 469 if (t < a[e2]) { 470 a[e3] = a[e2]; 471 a[e2] = t; 472 if (t < a[e1]) { 473 a[e2] = a[e1]; 474 a[e1] = t; 475 } 476 } 477 } 478 } 479 480 // Pointers 481 int less = left; // The index of the first element of center part 482 int great = right; // The index before the first element of right part 483 484 if (a[e1] != a[e2] && a[e2] != a[e3] && a[e3] != a[e4] && a[e4] != a[e5]) { 485 /* 486 * Use the second and fourth of the five sorted elements as pivots. 487 * These values are inexpensive approximations of the first and 488 * second terciles of the array. Note that pivot1 <= pivot2. 489 */ 490 long pivot1 = a[e2]; 491 long pivot2 = a[e4]; 492 493 /* 494 * The first and the last elements to be sorted are moved to the 495 * locations formerly occupied by the pivots. When partitioning 496 * is complete, the pivots are swapped back into their final 497 * positions, and excluded from subsequent sorting. 498 */ 499 a[e2] = a[left]; 500 a[e4] = a[right]; 501 502 /* 503 * Skip elements, which are less or greater than pivot values. 504 */ 505 while (a[++less] < pivot1) { 506 } 507 while (a[--great] > pivot2) { 508 } 509 510 /* 511 * Partitioning: 512 * 513 * left part center part right part 514 * +--------------------------------------------------------------+ 515 * | < pivot1 | pivot1 <= && <= pivot2 | ? | > pivot2 | 516 * +--------------------------------------------------------------+ 517 * ^ ^ ^ 518 * | | | 519 * less k great 520 * 521 * Invariants: 522 * 523 * all in (left, less) < pivot1 524 * pivot1 <= all in [less, k) <= pivot2 525 * all in (great, right) > pivot2 526 * 527 * Pointer k is the first index of ?-part. 528 */ 529 outer: 530 for (int k = less - 1; ++k <= great; ) { 531 long ak = a[k]; 532 if (ak < pivot1) { // Move a[k] to left part 533 a[k] = a[less]; 534 /* 535 * Here and below we use "a[i] = b; i++;" instead 536 * of "a[i++] = b;" due to performance issue. 537 */ 538 a[less] = ak; 539 ++less; 540 } 541 else if (ak > pivot2) { // Move a[k] to right part 542 while (a[great] > pivot2) { 543 if (great-- == k) { 544 break outer; 545 } 546 } 547 if (a[great] < pivot1) { // a[great] <= pivot2 548 a[k] = a[less]; 549 a[less] = a[great]; 550 ++less; 551 } 552 else { // pivot1 <= a[great] <= pivot2 553 a[k] = a[great]; 554 } 555 /* 556 * Here and below we use "a[i] = b; i--;" instead 557 * of "a[i--] = b;" due to performance issue. 558 */ 559 a[great] = ak; 560 --great; 561 } 562 } 563 564 // Swap pivots into their final positions 565 a[left] = a[less - 1]; 566 a[less - 1] = pivot1; 567 a[right] = a[great + 1]; 568 a[great + 1] = pivot2; 569 570 // Sort left and right parts recursively, excluding known pivots 571 SortingLongTestJMH.sort(a, left, less - 2, leftmost); 572 SortingLongTestJMH.sort(a, great + 2, right, false); 573 574 /* 575 * If center part is too large (comprises > 4/7 of the array), 576 * swap internal pivot values to ends. 577 */ 578 if (less < e1 && e5 < great) { 579 /* 580 * Skip elements, which are equal to pivot values. 581 */ 582 while (a[less] == pivot1) { 583 ++less; 584 } 585 586 while (a[great] == pivot2) { 587 --great; 588 } 589 590 /* 591 * Partitioning: 592 * 593 * left part center part right part 594 * +----------------------------------------------------------+ 595 * | == pivot1 | pivot1 < && < pivot2 | ? | == pivot2 | 596 * +----------------------------------------------------------+ 597 * ^ ^ ^ 598 * | | | 599 * less k great 600 * 601 * Invariants: 602 * 603 * all in (*, less) == pivot1 604 * pivot1 < all in [less, k) < pivot2 605 * all in (great, *) == pivot2 606 * 607 * Pointer k is the first index of ?-part. 608 */ 609 outer: 610 for (int k = less - 1; ++k <= great; ) { 611 long ak = a[k]; 612 if (ak == pivot1) { // Move a[k] to left part 613 a[k] = a[less]; 614 a[less] = ak; 615 ++less; 616 } 617 else if (ak == pivot2) { // Move a[k] to right part 618 while (a[great] == pivot2) { 619 if (great-- == k) { 620 break outer; 621 } 622 } 623 if (a[great] == pivot1) { // a[great] < pivot2 624 a[k] = a[less]; 625 /* 626 * Even though a[great] equals to pivot1, the 627 * assignment a[less] = pivot1 may be incorrect, 628 * if a[great] and pivot1 are floating-point zeros 629 * of different signs. Therefore in float and 630 * double sorting methods we have to use more 631 * accurate assignment a[less] = a[great]. 632 */ 633 a[less] = pivot1; 634 ++less; 635 } 636 else { // pivot1 < a[great] < pivot2 637 a[k] = a[great]; 638 } 639 a[great] = ak; 640 --great; 641 } 642 } 643 } 644 645 // Sort center part recursively 646 SortingLongTestJMH.sort(a, less, great, false); 647 } 648 else { // Partitioning with one pivot 649 /* 650 * Use the third of the five sorted elements as pivot. 651 * This value is inexpensive approximation of the median. 652 */ 653 long pivot = a[e3]; 654 655 /* 656 * Partitioning degenerates to the traditional 3-way 657 * (or "Dutch National Flag") schema: 658 * 659 * left part center part right part 660 * +-------------------------------------------------+ 661 * | < pivot | == pivot | ? | > pivot | 662 * +-------------------------------------------------+ 663 * ^ ^ ^ 664 * | | | 665 * less k great 666 * 667 * Invariants: 668 * 669 * all in (left, less) < pivot 670 * all in [less, k) == pivot 671 * all in (great, right) > pivot 672 * 673 * Pointer k is the first index of ?-part. 674 */ 675 for (int k = less; k <= great; ++k) { 676 if (a[k] == pivot) { 677 continue; 678 } 679 long ak = a[k]; 680 if (ak < pivot) { // Move a[k] to left part 681 a[k] = a[less]; 682 a[less] = ak; 683 ++less; 684 } 685 else { // a[k] > pivot - Move a[k] to right part 686 while (a[great] > pivot) { 687 --great; 688 } 689 if (a[great] < pivot) { // a[great] <= pivot 690 a[k] = a[less]; 691 a[less] = a[great]; 692 ++less; 693 } 694 else { // a[great] == pivot 695 /* 696 * Even though a[great] equals to pivot, the 697 * assignment a[k] = pivot may be incorrect, 698 * if a[great] and pivot are floating-point 699 * zeros of different signs. Therefore in float 700 * and double sorting methods we have to use 701 * more accurate assignment a[k] = a[great]. 702 */ 703 a[k] = pivot; 704 } 705 a[great] = ak; 706 --great; 707 } 708 } 709 710 /* 711 * Sort left and right parts recursively. 712 * All elements from center part are equal 713 * and, therefore, already sorted. 714 */ 715 SortingLongTestJMH.sort(a, left, less - 1, leftmost); 716 SortingLongTestJMH.sort(a, great + 1, right, false); 717 } 718 } 719 720 private static void swap(long[] arr, int i, int j) { 721 long tmp = arr[i]; 722 arr[i] = arr[j]; 723 arr[j] = tmp; 724 } 725} 726