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