1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
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
56 private static final long POW_32 = 1L << 32;
57
58
59
60
61
62 private static final int RANDOM_ACCESS_SIZE_THRESHOLD = 5;
63
64
65
66
67 @State(Scope.Benchmark)
68 public static class ShuffleData {
69
70
71
72 @Param({"10", "100", "1000", "10000"})
73 private int size;
74
75
76 private UniformRandomProvider rng;
77
78
79 private Random random;
80
81
82
83
84
85
86 public int getSize() {
87 return size;
88 }
89
90
91
92
93
94
95 public UniformRandomProvider getRNG() {
96 return rng;
97 }
98
99
100
101
102
103
104 public Random getRandom() {
105 return random;
106 }
107
108
109
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
121
122 @State(Scope.Benchmark)
123 public static class ListData extends ShuffleData {
124
125
126
127 @Param({"Array", "Linked"})
128 private String type;
129
130
131 private List<Integer> list;
132
133
134
135
136
137
138 public List<Integer> getList() {
139 return list;
140 }
141
142
143
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
160
161
162
163
164 @State(Scope.Benchmark)
165 public static class LinkedListData {
166
167
168
169 @Param({"3", "4", "5", "6", "7", "8"})
170 private int size;
171
172
173 private UniformRandomProvider rng;
174
175
176 private List<Integer> list;
177
178
179
180
181
182
183 public UniformRandomProvider getRNG() {
184 return rng;
185 }
186
187
188
189
190
191
192 public List<Integer> getList() {
193 return list;
194 }
195
196
197
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
211
212
213
214 static final class SplitMix32RNG extends IntProvider {
215
216 private long state;
217
218
219
220
221
222
223 SplitMix32RNG(long seed) {
224 state = seed;
225 }
226
227 @Override
228 public int next() {
229 long key = state += 0x9e3779b97f4a7c15L;
230
231
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
239
240
241 long m = (next() & 0xffffffffL) * n;
242 long l = m & 0xffffffffL;
243 if (l < n) {
244
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
258
259
260
261 static final class SplitMix32Random extends Random {
262 private static final long serialVersionUID = 1L;
263
264
265 private long state;
266
267
268
269
270
271
272 SplitMix32Random(long seed) {
273 state = seed;
274 }
275
276
277
278
279
280
281 private int next() {
282 long key = state += 0x9e3779b97f4a7c15L;
283
284
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
292
293
294 long m = (next() & 0xffffffffL) * n;
295 long l = m & 0xffffffffL;
296 if (l < n) {
297
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
310 return next() >>> (32 - n);
311 }
312 }
313
314
315
316
317
318
319
320
321
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
337
338
339
340
341
342
343
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
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
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
372
373
374
375
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
381 for (int i = list.size(); i > 1; i--) {
382 swap(list, i - 1, rng.nextInt(i));
383 }
384 } else {
385
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
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
402
403
404
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
414
415
416
417
418 @SuppressWarnings({"rawtypes", "unchecked"})
419 private static void shuffleIterator(UniformRandomProvider rng, List<?> list) {
420 final Object[] array = list.toArray();
421
422
423 for (int i = array.length; i > 1; i--) {
424 swap(array, i - 1, rng.nextInt(i));
425 }
426
427
428 final ListIterator it = list.listIterator();
429 for (final Object value : array) {
430 it.next();
431 it.set(value);
432 }
433 }
434
435
436
437
438
439
440
441
442
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
462 if (towardHead) {
463 for (int i = start; i > 0; i--) {
464 swap(array, i, rng.nextInt(i + 1));
465 }
466
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
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
488
489
490
491
492
493
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
506
507
508
509
510
511 @SuppressWarnings({"rawtypes", "unchecked"})
512 private static void swap(List<?> list, int i, int j) {
513
514 final List l = list;
515 l.set(i, l.set(j, l.get(i)));
516 }
517
518
519
520
521
522
523
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
533
534
535
536
537
538
539 @Benchmark
540 public int baselineRandom(ShuffleData data) {
541 int sum = 0;
542 for (int i = data.getSize(); i > 1; i--) {
543
544 sum += (i - 1) * data.getRandom().nextInt(i);
545 }
546 return sum;
547 }
548
549
550
551
552
553
554
555
556 @Benchmark
557 public int baselineRNG(ShuffleData data) {
558 int sum = 0;
559 for (int i = data.getSize(); i > 1; i--) {
560
561 sum += (i - 1) * data.getRNG().nextInt(i);
562 }
563 return sum;
564 }
565
566
567
568
569
570
571
572
573 @Benchmark
574 public int baselineRNG2(ShuffleData data) {
575 int sum = 0;
576 for (int i = data.getSize(); i > 1; i--) {
577
578 sum += data.getRNG().nextInt(i) * (i - 1);
579 }
580 return sum;
581 }
582
583
584
585
586
587
588
589
590
591
592 @Benchmark
593 public int baselineRNG3(ShuffleData data) {
594 int sum = 0;
595 for (int i = data.getSize() - 1; i > 0; i--) {
596
597 sum += i * data.getRNG().nextInt(i + 1);
598 }
599 return sum;
600 }
601
602
603
604
605
606
607
608 @Benchmark
609 public Object usingCollections(ListData data) {
610 Collections.shuffle(data.getList(), data.getRandom());
611 return data.getList();
612 }
613
614
615
616
617
618
619
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
629
630
631
632
633
634
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
646
647
648
649
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
659
660
661
662
663
664
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
676
677
678
679
680 @Benchmark
681 public Object usingDirectRandomAccess(ListData data) {
682 shuffleDirectRandomAccess(data.getRNG(), data.getList());
683 return data.getList();
684 }
685
686
687
688
689
690
691
692
693
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
705
706
707
708
709
710
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
722
723
724
725
726 @Benchmark
727 public Object usingListSampler(ListData data) {
728 ListSampler.shuffle(data.getRNG(), data.getList());
729 return data.getList();
730 }
731
732
733
734
735
736
737
738
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
750
751
752
753
754 @Benchmark
755 public Object shuffleDirect(LinkedListData data) {
756 shuffleDirect(data.getRNG(), data.getList());
757 return data.getList();
758 }
759
760
761
762
763
764
765
766 @Benchmark
767 public Object shuffleIterator(LinkedListData data) {
768 shuffleIterator(data.getRNG(), data.getList());
769 return data.getList();
770 }
771 }