1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 package org.apache.commons.rng.examples.jmh.sampling;
19
20 import org.apache.commons.rng.UniformRandomProvider;
21 import org.apache.commons.rng.core.source32.IntProvider;
22 import org.apache.commons.rng.sampling.ListSampler;
23 import org.apache.commons.rng.sampling.PermutationSampler;
24 import org.openjdk.jmh.annotations.Benchmark;
25 import org.openjdk.jmh.annotations.BenchmarkMode;
26 import org.openjdk.jmh.annotations.Fork;
27 import org.openjdk.jmh.annotations.Measurement;
28 import org.openjdk.jmh.annotations.Mode;
29 import org.openjdk.jmh.annotations.OutputTimeUnit;
30 import org.openjdk.jmh.annotations.Param;
31 import org.openjdk.jmh.annotations.Scope;
32 import org.openjdk.jmh.annotations.Setup;
33 import org.openjdk.jmh.annotations.State;
34 import org.openjdk.jmh.annotations.Warmup;
35
36 import java.util.ArrayList;
37 import java.util.Collections;
38 import java.util.LinkedList;
39 import java.util.List;
40 import java.util.ListIterator;
41 import java.util.Random;
42 import java.util.RandomAccess;
43 import java.util.concurrent.TimeUnit;
44
45 /**
46 * Executes benchmark to compare the speed of shuffling a {@link List}.
47 */
48 @BenchmarkMode(Mode.AverageTime)
49 @OutputTimeUnit(TimeUnit.NANOSECONDS)
50 @Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
51 @Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
52 @State(Scope.Benchmark)
53 @Fork(value = 1, jvmArgs = { "-server", "-Xms128M", "-Xmx128M" })
54 public class ListShuffleBenchmark {
55 /** 2^32. Used for the nextInt(int) algorithm. */
56 private static final long POW_32 = 1L << 32;
57
58 /**
59 * The size threshold for using the random access algorithm
60 * when the list does not implement RandomAccess.
61 */
62 private static final int RANDOM_ACCESS_SIZE_THRESHOLD = 5;
63
64 /**
65 * The data for the shuffle. Contains the data size and the random generators.
66 */
67 @State(Scope.Benchmark)
68 public static class ShuffleData {
69 /**
70 * The list size.
71 */
72 @Param({"10", "100", "1000", "10000"})
73 private int size;
74
75 /** The UniformRandomProvider instance. */
76 private UniformRandomProvider rng;
77
78 /** The Random instance. */
79 private Random random;
80
81 /**
82 * Gets the size.
83 *
84 * @return the size
85 */
86 public int getSize() {
87 return size;
88 }
89
90 /**
91 * Gets the uniform random provider.
92 *
93 * @return the uniform random provider
94 */
95 public UniformRandomProvider getRNG() {
96 return rng;
97 }
98
99 /**
100 * Gets the random.
101 *
102 * @return the random
103 */
104 public Random getRandom() {
105 return random;
106 }
107
108 /**
109 * Create the random generators.
110 */
111 @Setup
112 public void setupGenerators() {
113 final long seed = System.currentTimeMillis();
114 rng = new SplitMix32RNG(seed);
115 random = new SplitMix32Random(seed);
116 }
117 }
118
119 /**
120 * The list to shuffle. Either an ArrayList or a LinkedList.
121 */
122 @State(Scope.Benchmark)
123 public static class ListData extends ShuffleData {
124 /**
125 * The list type.
126 */
127 @Param({"Array", "Linked"})
128 private String type;
129
130 /** The list. */
131 private List<Integer> list;
132
133 /**
134 * Gets the list.
135 *
136 * @return the list
137 */
138 public List<Integer> getList() {
139 return list;
140 }
141
142 /**
143 * Create the list.
144 */
145 @Setup
146 public void setupList() {
147 if ("Array".equals(type)) {
148 list = new ArrayList<>();
149 } else if ("Linked".equals(type)) {
150 list = new LinkedList<>();
151 }
152 for (int i = 0; i < getSize(); i++) {
153 list.add(i);
154 }
155 }
156 }
157
158 /**
159 * The LinkedList to shuffle.
160 *
161 * <p>This is used to determine the threshold to switch from the direct shuffle of a list
162 * without RandomAccess to the iterator based version.</p>
163 */
164 @State(Scope.Benchmark)
165 public static class LinkedListData {
166 /**
167 * The list size. The java.utils.Collections.shuffle method switches at size 5.
168 */
169 @Param({"3", "4", "5", "6", "7", "8"})
170 private int size;
171
172 /** The UniformRandomProvider instance. */
173 private UniformRandomProvider rng;
174
175 /** The list. */
176 private List<Integer> list;
177
178 /**
179 * Gets the uniform random provider.
180 *
181 * @return the uniform random provider
182 */
183 public UniformRandomProvider getRNG() {
184 return rng;
185 }
186
187 /**
188 * Gets the list.
189 *
190 * @return the list
191 */
192 public List<Integer> getList() {
193 return list;
194 }
195
196 /**
197 * Create the list.
198 */
199 @Setup
200 public void setup() {
201 rng = new SplitMix32RNG(System.currentTimeMillis());
202 list = new LinkedList<>();
203 for (int i = 0; i < size; i++) {
204 list.add(i);
205 }
206 }
207 }
208
209 /**
210 * Implement the SplitMix algorithm from {@link java.util.SplittableRandom
211 * SplittableRandom} to output 32-bit int values. Expose this through the
212 * {@link UniformRandomProvider} API.
213 */
214 static final class SplitMix32RNG extends IntProvider {
215 /** The state. */
216 private long state;
217
218 /**
219 * Create a new instance.
220 *
221 * @param seed the seed
222 */
223 SplitMix32RNG(long seed) {
224 state = seed;
225 }
226
227 @Override
228 public int next() {
229 long key = state += 0x9e3779b97f4a7c15L;
230 // 32 high bits of Stafford variant 4 mix64 function as int:
231 // http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html
232 key = (key ^ (key >>> 33)) * 0x62a9d9ed799705f5L;
233 return (int) (((key ^ (key >>> 28)) * 0xcb24d0a5c88c35b3L) >>> 32);
234 }
235
236 @Override
237 public int nextInt(int n) {
238 // No check for positive n.
239 // Implement the Lemire method to create an integer in a range.
240
241 long m = (next() & 0xffffffffL) * n;
242 long l = m & 0xffffffffL;
243 if (l < n) {
244 // 2^32 % n
245 final long t = POW_32 % n;
246 while (l < t) {
247 m = (next() & 0xffffffffL) * n;
248 l = m & 0xffffffffL;
249 }
250 }
251 return (int) (m >>> 32);
252 }
253 }
254
255
256 /**
257 * Implement the SplitMix algorithm from {@link java.util.SplittableRandom
258 * SplittableRandom} to output 32-bit int values. Expose this through the
259 * {@link java.util.Random} API.
260 */
261 static final class SplitMix32Random extends Random {
262 private static final long serialVersionUID = 1L;
263
264 /** The state. */
265 private long state;
266
267 /**
268 * Create a new instance.
269 *
270 * @param seed the seed
271 */
272 SplitMix32Random(long seed) {
273 state = seed;
274 }
275
276 /**
277 * Return the next value.
278 *
279 * @return the value
280 */
281 private int next() {
282 long key = state += 0x9e3779b97f4a7c15L;
283 // 32 high bits of Stafford variant 4 mix64 function as int:
284 // http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html
285 key = (key ^ (key >>> 33)) * 0x62a9d9ed799705f5L;
286 return (int) (((key ^ (key >>> 28)) * 0xcb24d0a5c88c35b3L) >>> 32);
287 }
288
289 @Override
290 public int nextInt(int n) {
291 // No check for positive n.
292 // Implement the Lemire method to create an integer in a range.
293
294 long m = (next() & 0xffffffffL) * n;
295 long l = m & 0xffffffffL;
296 if (l < n) {
297 // 2^32 % n
298 final long t = POW_32 % n;
299 while (l < t) {
300 m = (next() & 0xffffffffL) * n;
301 l = m & 0xffffffffL;
302 }
303 }
304 return (int) (m >>> 32);
305 }
306
307 @Override
308 protected int next(int n) {
309 // For the Random implementation. This is unused.
310 return next() >>> (32 - n);
311 }
312 }
313
314 /**
315 * ListSampler shuffle from version 1.2 delegates to the PermutationSampler.
316 *
317 * @param <T> Type of the list items.
318 * @param rng Random number generator.
319 * @param list List.
320 * @param start Index at which shuffling begins.
321 * @param towardHead Shuffling is performed to the beginning or end of the list.
322 */
323 private static <T> void shuffleUsingPermutationSampler(UniformRandomProvider rng, List<T> list,
324 int start, boolean towardHead) {
325 final int len = list.size();
326 final int[] indices = PermutationSampler.natural(len);
327 PermutationSampler.shuffle(rng, indices, start, towardHead);
328
329 final ArrayList<T> items = new ArrayList<>(list);
330 for (int i = 0; i < len; i++) {
331 list.set(i, items.get(indices[i]));
332 }
333 }
334
335 /**
336 * ListSampler shuffle from version 1.2 delegates to the PermutationSampler.
337 * Modified for RandomAccess lists.
338 *
339 * @param <T> Type of the list items.
340 * @param rng Random number generator.
341 * @param list List.
342 * @param start Index at which shuffling begins.
343 * @param towardHead Shuffling is performed to the beginning or end of the list.
344 */
345 @SuppressWarnings({"rawtypes", "unchecked"})
346 private static <T> void shuffleUsingPermutationSamplerRandomAccess(UniformRandomProvider rng, List<T> list,
347 int start, boolean towardHead) {
348 final int len = list.size();
349 final int[] indices = PermutationSampler.natural(len);
350 PermutationSampler.shuffle(rng, indices, start, towardHead);
351
352 // Copy back.
353 final ArrayList<T> items = new ArrayList<>(list);
354 final int low = towardHead ? 0 : start;
355 final int high = towardHead ? start + 1 : len;
356 if (list instanceof RandomAccess) {
357 for (int i = low; i < high; i++) {
358 list.set(i, items.get(indices[i]));
359 }
360 } else {
361 // Copy back. Use raw types.
362 final ListIterator it = list.listIterator(low);
363 for (int i = low; i < high; i++) {
364 it.next();
365 it.set(items.get(indices[i]));
366 }
367 }
368 }
369
370 /**
371 * Direct shuffle on the list adapted from JDK java.util.Collections.
372 * This handles RandomAccess lists.
373 *
374 * @param rng Random number generator.
375 * @param list List.
376 */
377 @SuppressWarnings({"rawtypes", "unchecked"})
378 private static void shuffleDirectRandomAccess(UniformRandomProvider rng, List<?> list) {
379 if (list instanceof RandomAccess || list.size() < RANDOM_ACCESS_SIZE_THRESHOLD) {
380 // Shuffle list in-place
381 for (int i = list.size(); i > 1; i--) {
382 swap(list, i - 1, rng.nextInt(i));
383 }
384 } else {
385 // Shuffle as an array
386 final Object[] array = list.toArray();
387 for (int i = array.length; i > 1; i--) {
388 swap(array, i - 1, rng.nextInt(i));
389 }
390
391 // Copy back. Use raw types.
392 final ListIterator it = list.listIterator();
393 for (final Object value : array) {
394 it.next();
395 it.set(value);
396 }
397 }
398 }
399
400 /**
401 * A direct list shuffle.
402 *
403 * @param rng Random number generator.
404 * @param list List.
405 */
406 private static void shuffleDirect(UniformRandomProvider rng, List<?> list) {
407 for (int i = list.size(); i > 1; i--) {
408 swap(list, i - 1, rng.nextInt(i));
409 }
410 }
411
412 /**
413 * A list shuffle using an iterator.
414 *
415 * @param rng Random number generator.
416 * @param list List.
417 */
418 @SuppressWarnings({"rawtypes", "unchecked"})
419 private static void shuffleIterator(UniformRandomProvider rng, List<?> list) {
420 final Object[] array = list.toArray();
421
422 // Shuffle array
423 for (int i = array.length; i > 1; i--) {
424 swap(array, i - 1, rng.nextInt(i));
425 }
426
427 // Copy back. Use raw types.
428 final ListIterator it = list.listIterator();
429 for (final Object value : array) {
430 it.next();
431 it.set(value);
432 }
433 }
434
435 /**
436 * Direct shuffle on the list adapted from JDK java.util.Collections.
437 * This has been modified to handle the directional shuffle from a start index.
438 *
439 * @param rng Random number generator.
440 * @param list List.
441 * @param start Index at which shuffling begins.
442 * @param towardHead Shuffling is performed to the beginning or end of the list.
443 */
444 @SuppressWarnings({"rawtypes", "unchecked"})
445 private static void shuffleDirectRandomAccessDirectional(UniformRandomProvider rng, List<?> list,
446 int start, boolean towardHead) {
447 final int size = list.size();
448 if (list instanceof RandomAccess || size < RANDOM_ACCESS_SIZE_THRESHOLD) {
449 if (towardHead) {
450 for (int i = start; i > 0; i--) {
451 swap(list, i, rng.nextInt(i + 1));
452 }
453 } else {
454 for (int i = size - 1; i > start; i--) {
455 swap(list, i, start + rng.nextInt(i + 1 - start));
456 }
457 }
458 } else {
459 final Object[] array = list.toArray();
460
461 // Shuffle array
462 if (towardHead) {
463 for (int i = start; i > 0; i--) {
464 swap(array, i, rng.nextInt(i + 1));
465 }
466 // Copy back. Use raw types.
467 final ListIterator it = list.listIterator();
468 for (int i = 0; i <= start; i++) {
469 it.next();
470 it.set(array[i]);
471 }
472 } else {
473 for (int i = size - 1; i > start; i--) {
474 swap(array, i, start + rng.nextInt(i + 1 - start));
475 }
476 // Copy back. Use raw types.
477 final ListIterator it = list.listIterator(start);
478 for (int i = start; i < array.length; i++) {
479 it.next();
480 it.set(array[i]);
481 }
482 }
483 }
484 }
485
486 /**
487 * Direct shuffle on the list using the JDK java.util.Collections method with a sub-list
488 * to handle the directional shuffle from a start index.
489 *
490 * @param rng Random number generator.
491 * @param list List.
492 * @param start Index at which shuffling begins.
493 * @param towardHead Shuffling is performed to the beginning or end of the list.
494 */
495 private static void shuffleDirectRandomAccessSubList(UniformRandomProvider rng, List<?> list,
496 int start, boolean towardHead) {
497 if (towardHead) {
498 shuffleDirectRandomAccess(rng, list.subList(0, start + 1));
499 } else {
500 shuffleDirectRandomAccess(rng, list.subList(start, list.size()));
501 }
502 }
503
504 /**
505 * Swaps the two specified elements in the specified list.
506 *
507 * @param list List.
508 * @param i First index.
509 * @param j Second index.
510 */
511 @SuppressWarnings({"rawtypes", "unchecked"})
512 private static void swap(List<?> list, int i, int j) {
513 // Use raw type
514 final List l = list;
515 l.set(i, l.set(j, l.get(i)));
516 }
517
518 /**
519 * Swaps the two specified elements in the specified array.
520 *
521 * @param array Array.
522 * @param i First index.
523 * @param j Second index.
524 */
525 private static void swap(Object[] array, int i, int j) {
526 final Object tmp = array[i];
527 array[i] = array[j];
528 array[j] = tmp;
529 }
530
531 /**
532 * Baseline a shuffle using the Random.
533 * This is the in java.util.Collections that decrements to above one.
534 * This should be the same speed as the benchmark using UniformRandomProvider.
535 *
536 * @param data Shuffle data.
537 * @return the sum
538 */
539 @Benchmark
540 public int baselineRandom(ShuffleData data) {
541 int sum = 0;
542 for (int i = data.getSize(); i > 1; i--) {
543 // A shuffle would swap (i-1) and j=nextInt(i)
544 sum += (i - 1) * data.getRandom().nextInt(i);
545 }
546 return sum;
547 }
548
549 /**
550 * Baseline a shuffle using the UniformRandomProvider.
551 * This should be the same speed as the benchmark using Random.
552 *
553 * @param data Shuffle data.
554 * @return the sum
555 */
556 @Benchmark
557 public int baselineRNG(ShuffleData data) {
558 int sum = 0;
559 for (int i = data.getSize(); i > 1; i--) {
560 // A shuffle would swap (i-1) and j=nextInt(i)
561 sum += (i - 1) * data.getRNG().nextInt(i);
562 }
563 return sum;
564 }
565
566 /**
567 * Baseline a shuffle using the UniformRandomProvider.
568 * This should be the same speed as the benchmark using Random.
569 *
570 * @param data Shuffle data.
571 * @return the sum
572 */
573 @Benchmark
574 public int baselineRNG2(ShuffleData data) {
575 int sum = 0;
576 for (int i = data.getSize(); i > 1; i--) {
577 // A shuffle would swap j=nextInt(i) and (i-1)
578 sum += data.getRNG().nextInt(i) * (i - 1);
579 }
580 return sum;
581 }
582
583 /**
584 * Baseline a shuffle using the UniformRandomProvider.
585 * This should be the same speed as the benchmark using Random.
586 * This uses a variant that decrements to above zero so that the index i is one
587 * of the indices to swap. This is included to determine if there is a difference.
588 *
589 * @param data Shuffle data.
590 * @return the sum
591 */
592 @Benchmark
593 public int baselineRNG3(ShuffleData data) {
594 int sum = 0;
595 for (int i = data.getSize() - 1; i > 0; i--) {
596 // A shuffle would swap i and j=nextInt(i+1)
597 sum += i * data.getRNG().nextInt(i + 1);
598 }
599 return sum;
600 }
601
602 /**
603 * Performs a shuffle using java.utils.Collections.
604 *
605 * @param data Shuffle data.
606 * @return the list
607 */
608 @Benchmark
609 public Object usingCollections(ListData data) {
610 Collections.shuffle(data.getList(), data.getRandom());
611 return data.getList();
612 }
613
614 /**
615 * Performs a shuffle using ListSampler shuffle method from version 1.2 which delegates
616 * to the PermuationSampler.
617 *
618 * @param data Shuffle data.
619 * @return the list
620 */
621 @Benchmark
622 public Object usingPermutationSampler(ListData data) {
623 shuffleUsingPermutationSampler(data.getRNG(), data.getList(), data.getSize() - 1, true);
624 return data.getList();
625 }
626
627 /**
628 * Performs a shuffle using ListSampler shuffle method from version 1.2 which delegates
629 * to the PermuationSampler.
630 * This performs two part shuffles from the middle
631 * towards the head and then towards the end.
632 *
633 * @param data Shuffle data.
634 * @return the list
635 */
636 @Benchmark
637 public Object usingPermutationSamplerBidirectional(ListData data) {
638 final int start = data.getSize() / 2;
639 shuffleUsingPermutationSampler(data.getRNG(), data.getList(), start, true);
640 shuffleUsingPermutationSampler(data.getRNG(), data.getList(), start + 1, false);
641 return data.getList();
642 }
643
644 /**
645 * Performs a shuffle using ListSampler shuffle method from version 1.2 which delegates
646 * to the PermuationSampler. The method has been modified to detect RandomAccess lists.
647 *
648 * @param data Shuffle data.
649 * @return the list
650 */
651 @Benchmark
652 public Object usingPermutationSamplerRandomAccess(ListData data) {
653 shuffleUsingPermutationSamplerRandomAccess(data.getRNG(), data.getList(), data.getSize() - 1, true);
654 return data.getList();
655 }
656
657 /**
658 * Performs a shuffle using ListSampler shuffle method from version 1.2 which delegates
659 * to the PermuationSampler. The method has been modified to detect RandomAccess lists.
660 * This performs two part shuffles from the middle
661 * towards the head and then towards the end.
662 *
663 * @param data Shuffle data.
664 * @return the list
665 */
666 @Benchmark
667 public Object usingPermutationSamplerRandomAccessBidirectional(ListData data) {
668 final int start = data.getSize() / 2;
669 shuffleUsingPermutationSamplerRandomAccess(data.getRNG(), data.getList(), start, true);
670 shuffleUsingPermutationSamplerRandomAccess(data.getRNG(), data.getList(), start + 1, false);
671 return data.getList();
672 }
673
674 /**
675 * Performs a direct shuffle on the list using JDK Collections method.
676 *
677 * @param data Shuffle data.
678 * @return the list
679 */
680 @Benchmark
681 public Object usingDirectRandomAccess(ListData data) {
682 shuffleDirectRandomAccess(data.getRNG(), data.getList());
683 return data.getList();
684 }
685
686 /**
687 * Performs a direct shuffle on the list using JDK Collections method modified to handle
688 * a directional shuffle from a start index.
689 * This performs two part shuffles from the middle
690 * towards the head and then towards the end.
691 *
692 * @param data Shuffle data.
693 * @return the list
694 */
695 @Benchmark
696 public Object usingDirectRandomAccessDirectionalBidirectional(ListData data) {
697 final int start = data.getSize() / 2;
698 shuffleDirectRandomAccessDirectional(data.getRNG(), data.getList(), start, true);
699 shuffleDirectRandomAccessDirectional(data.getRNG(), data.getList(), start + 1, false);
700 return data.getList();
701 }
702
703 /**
704 * Performs a direct shuffle on the list using JDK Collections method modified to handle
705 * a directional shuffle from a start index by extracting a sub-list.
706 * This performs two part shuffles from the middle
707 * towards the head and then towards the end.
708 *
709 * @param data Shuffle data.
710 * @return the list
711 */
712 @Benchmark
713 public Object usingDirectRandomAccessSublistBidirectional(ListData data) {
714 final int start = data.getSize() / 2;
715 shuffleDirectRandomAccessSubList(data.getRNG(), data.getList(), start, true);
716 shuffleDirectRandomAccessSubList(data.getRNG(), data.getList(), start + 1, false);
717 return data.getList();
718 }
719
720 /**
721 * Performs a shuffle using the current ListSampler shuffle.
722 *
723 * @param data Shuffle data.
724 * @return the list
725 */
726 @Benchmark
727 public Object usingListSampler(ListData data) {
728 ListSampler.shuffle(data.getRNG(), data.getList());
729 return data.getList();
730 }
731
732 /**
733 * Performs a shuffle using the current ListSampler shuffle.
734 * This performs two part shuffles from the middle
735 * towards the head and then towards the end.
736 *
737 * @param data Shuffle data.
738 * @return the list
739 */
740 @Benchmark
741 public Object usingListSamplerBidirectional(ListData data) {
742 final int start = data.getSize() / 2;
743 ListSampler.shuffle(data.getRNG(), data.getList(), start, true);
744 ListSampler.shuffle(data.getRNG(), data.getList(), start + 1, false);
745 return data.getList();
746 }
747
748 /**
749 * Performs a direct shuffle on a LinkedList.
750 *
751 * @param data Shuffle data.
752 * @return the list
753 */
754 @Benchmark
755 public Object shuffleDirect(LinkedListData data) {
756 shuffleDirect(data.getRNG(), data.getList());
757 return data.getList();
758 }
759
760 /**
761 * Performs a shuffle on a LinkedList using an iterator.
762 *
763 * @param data Shuffle data.
764 * @return the list
765 */
766 @Benchmark
767 public Object shuffleIterator(LinkedListData data) {
768 shuffleIterator(data.getRNG(), data.getList());
769 return data.getList();
770 }
771 }