View Javadoc
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 }