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.core;
19  
20  import org.apache.commons.rng.UniformRandomProvider;
21  import org.apache.commons.rng.core.source32.IntProvider;
22  import org.apache.commons.rng.sampling.PermutationSampler;
23  import org.openjdk.jmh.annotations.Benchmark;
24  import org.openjdk.jmh.annotations.BenchmarkMode;
25  import org.openjdk.jmh.annotations.Fork;
26  import org.openjdk.jmh.annotations.Measurement;
27  import org.openjdk.jmh.annotations.Mode;
28  import org.openjdk.jmh.annotations.OperationsPerInvocation;
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.concurrent.ThreadLocalRandom;
37  import java.util.concurrent.TimeUnit;
38  
39  /**
40   * Executes benchmark to compare the speed of random number generators to create
41   * an int value in a range.
42   */
43  @BenchmarkMode(Mode.AverageTime)
44  @OutputTimeUnit(TimeUnit.NANOSECONDS)
45  @Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
46  @Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
47  @State(Scope.Benchmark)
48  @Fork(value = 1, jvmArgs = { "-server", "-Xms128M", "-Xmx128M" })
49  public class RngNextIntInRangeBenchmark {
50      /** The value. Must NOT be final to prevent JVM optimisation! */
51      private int intValue;
52  
53      /**
54       * The upper range for the {@code int} generation.
55       */
56      @State(Scope.Benchmark)
57      public static class IntRange {
58          /**
59           * The upper range for the {@code int} generation.
60           *
61           * <p>Note that the while loop uses a rejection algorithm. From the Javadoc for
62           * java.util.Random:</p>
63           *
64           * <pre>
65           * "The probability of a value being rejected depends on n. The
66           * worst case is n=2^30+1, for which the probability of a reject is 1/2,
67           * and the expected number of iterations before the loop terminates is 2."
68           * </pre>
69           */
70          @Param({"16", "17", "256", "257", "4096", "4097",
71                  // Worst case power-of-2: (1 << 30)
72                  "1073741824",
73                  // Worst case: (1 << 30) + 1
74                  "1073741825", })
75          private int n;
76  
77          /**
78           * Gets the upper bound {@code n}.
79           *
80           * @return the upper bound
81           */
82          public int getN() {
83              return n;
84          }
85      }
86  
87      /**
88       * The data used for the shuffle benchmark.
89       */
90      @State(Scope.Benchmark)
91      public static class IntData {
92          /**
93           * The size of the data.
94           */
95          @Param({ "4", "16", "256", "4096", "16384" })
96          private int size;
97  
98          /** The data. */
99          private int[] data;
100 
101         /**
102          * Gets the data.
103          *
104          * @return the data
105          */
106         public int[] getData() {
107             return data;
108         }
109 
110         /**
111          * Create the data.
112          */
113         @Setup
114         public void setup() {
115             data = PermutationSampler.natural(size);
116         }
117     }
118 
119     /**
120      * The source generator.
121      */
122     @State(Scope.Benchmark)
123     public static class Source {
124         /**
125          * The name of the generator.
126          */
127         @Param({ "jdk", "jdkPow2", "lemire", "lemirePow2", "lemire31", "lemire31Pow2"})
128         private String name;
129 
130         /** The random generator. */
131         private UniformRandomProvider rng;
132 
133         /**
134          * Gets the random generator.
135          *
136          * @return the generator
137          */
138         public UniformRandomProvider getRng() {
139             return rng;
140         }
141 
142         /** Create the generator. */
143         @Setup
144         public void setup() {
145             final long seed = ThreadLocalRandom.current().nextLong();
146             if ("jdk".equals(name)) {
147                 rng = new JDK(seed);
148             } else if ("jdkPow2".equals(name)) {
149                 rng = new JDKPow2(seed);
150             } else if ("lemire".equals(name)) {
151                 rng = new Lemire(seed);
152             } else if ("lemirePow2".equals(name)) {
153                 rng = new LemirePow2(seed);
154             } else if ("lemire31".equals(name)) {
155                 rng = new Lemire31(seed);
156             } else if ("lemire31Pow2".equals(name)) {
157                 rng = new Lemire31Pow2(seed);
158             }
159         }
160     }
161 
162     /**
163      * Implement the SplitMix algorithm from {@link java.util.SplittableRandom
164      * SplittableRandom} to output 32-bit int values.
165      *
166      * <p>This is a base generator to test nextInt(int) methods.
167      */
168     abstract static class SplitMix32 extends IntProvider {
169         /**
170          * The golden ratio, phi, scaled to 64-bits and rounded to odd.
171          */
172         private static final long GOLDEN_RATIO = 0x9e3779b97f4a7c15L;
173 
174         /** The state. */
175         protected long state;
176 
177         /**
178          * Create a new instance.
179          *
180          * @param seed the seed
181          */
182         SplitMix32(long seed) {
183             state = seed;
184         }
185 
186         @Override
187         public int next() {
188             long key = state += GOLDEN_RATIO;
189             // 32 high bits of Stafford variant 4 mix64 function as int:
190             // http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html
191             key = (key ^ (key >>> 33)) * 0x62a9d9ed799705f5L;
192             return (int) (((key ^ (key >>> 28)) * 0xcb24d0a5c88c35b3L) >>> 32);
193         }
194 
195         /**
196          * Check the value is strictly positive.
197          *
198          * @param n the value
199          */
200         void checkStrictlyPositive(int n) {
201             if (n <= 0) {
202                 throw new IllegalArgumentException("not strictly positive: " + n);
203             }
204         }
205     }
206 
207     /**
208      * Implement the nextInt(int) method of the JDK excluding the case for a power-of-2 range.
209      */
210     static class JDK extends SplitMix32 {
211         /**
212          * Create a new instance.
213          *
214          * @param seed the seed
215          */
216         JDK(long seed) {
217             super(seed);
218         }
219 
220         @Override
221         public int nextInt(int n) {
222             checkStrictlyPositive(n);
223 
224             int bits;
225             int val;
226             do {
227                 bits = next() >>> 1;
228                 val = bits % n;
229             } while (bits - val + n - 1 < 0);
230 
231             return val;
232         }
233     }
234 
235     /**
236      * Implement the nextInt(int) method of the JDK with a case for a power-of-2 range.
237      */
238     static class JDKPow2 extends SplitMix32 {
239         /**
240          * Create a new instance.
241          *
242          * @param seed the seed
243          */
244         JDKPow2(long seed) {
245             super(seed);
246         }
247 
248         @Override
249         public int nextInt(int n) {
250             checkStrictlyPositive(n);
251 
252             final int nm1 = n - 1;
253             if ((n & nm1) == 0) {
254                 // Power of 2
255                 return next() & nm1;
256             }
257 
258             int bits;
259             int val;
260             do {
261                 bits = next() >>> 1;
262                 val = bits % n;
263             } while (bits - val + nm1 < 0);
264 
265             return val;
266         }
267     }
268 
269     /**
270      * Implement the nextInt(int) method of Lemire (2019).
271      *
272      * @see <a href="https://arxiv.org/abs/1805.10941SplittableRandom"> Lemire
273      * (2019): Fast Random Integer Generation in an Interval</a>
274      */
275     static class Lemire extends SplitMix32 {
276         /** 2^32. */
277         static final long POW_32 = 1L << 32;
278 
279         /**
280          * Create a new instance.
281          *
282          * @param seed the seed
283          */
284         Lemire(long seed) {
285             super(seed);
286         }
287 
288         @Override
289         public int nextInt(int n) {
290             checkStrictlyPositive(n);
291 
292             long m = (next() & 0xffffffffL) * n;
293             long l = m & 0xffffffffL;
294             if (l < n) {
295                 // 2^32 % n
296                 final long t = POW_32 % n;
297                 while (l < t) {
298                     m = (next() & 0xffffffffL) * n;
299                     l = m & 0xffffffffL;
300                 }
301             }
302             return (int) (m >>> 32);
303         }
304     }
305 
306     /**
307      * Implement the nextInt(int) method of Lemire (2019) with a case for a power-of-2 range.
308      */
309     static class LemirePow2 extends SplitMix32 {
310         /** 2^32. */
311         static final long POW_32 = 1L << 32;
312 
313         /**
314          * Create a new instance.
315          *
316          * @param seed the seed
317          */
318         LemirePow2(long seed) {
319             super(seed);
320         }
321 
322         @Override
323         public int nextInt(int n) {
324             checkStrictlyPositive(n);
325 
326             final int nm1 = n - 1;
327             if ((n & nm1) == 0) {
328                 // Power of 2
329                 return next() & nm1;
330             }
331 
332             long m = (next() & 0xffffffffL) * n;
333             long l = m & 0xffffffffL;
334             if (l < n) {
335                 // 2^32 % n
336                 final long t = POW_32 % n;
337                 while (l < t) {
338                     m = (next() & 0xffffffffL) * n;
339                     l = m & 0xffffffffL;
340                 }
341             }
342             return (int) (m >>> 32);
343         }
344     }
345 
346     /**
347      * Implement the nextInt(int) method of Lemire (2019) modified to 31-bit arithmetic to use
348      * an int modulus operation.
349      */
350     static class Lemire31 extends SplitMix32 {
351         /** 2^32. */
352         static final long POW_32 = 1L << 32;
353 
354         /**
355          * Create a new instance.
356          *
357          * @param seed the seed
358          */
359         Lemire31(long seed) {
360             super(seed);
361         }
362 
363         @Override
364         public int nextInt(int n) {
365             checkStrictlyPositive(n);
366 
367             long m = (nextInt() & 0x7fffffffL) * n;
368             long l = m & 0x7fffffffL;
369             if (l < n) {
370                 // 2^31 % n
371                 final long t = (Integer.MIN_VALUE - n) % n;
372                 while (l < t) {
373                     m = (nextInt() & 0x7fffffffL) * n;
374                     l = m & 0x7fffffffL;
375                 }
376             }
377             return (int) (m >>> 31);
378         }
379     }
380 
381     /**
382      * Implement the nextInt(int) method of Lemire (2019) modified to 31-bit arithmetic to use
383      * an int modulus operation, with a case for a power-of-2 range.
384      */
385     static class Lemire31Pow2 extends SplitMix32 {
386         /** 2^32. */
387         static final long POW_32 = 1L << 32;
388 
389         /**
390          * Create a new instance.
391          *
392          * @param seed the seed
393          */
394         Lemire31Pow2(long seed) {
395             super(seed);
396         }
397 
398         @Override
399         public int nextInt(int n) {
400             checkStrictlyPositive(n);
401 
402             final int nm1 = n - 1;
403             if ((n & nm1) == 0) {
404                 // Power of 2
405                 return next() & nm1;
406             }
407 
408             long m = (nextInt() & 0x7fffffffL) * n;
409             long l = m & 0x7fffffffL;
410             if (l < n) {
411                 // 2^31 % n
412                 final long t = (Integer.MIN_VALUE - n) % n;
413                 while (l < t) {
414                     m = (nextInt() & 0x7fffffffL) * n;
415                     l = m & 0x7fffffffL;
416                 }
417             }
418             return (int) (m >>> 31);
419         }
420     }
421 
422     /**
423      * Baseline for a JMH method call returning an {@code int}.
424      *
425      * @return the value
426      */
427     @Benchmark
428     public int baselineInt() {
429         return intValue;
430     }
431 
432     /**
433      * Exercise the {@link UniformRandomProvider#nextInt()} method.
434      *
435      * @param range the range
436      * @param source Source of randomness.
437      * @return the int
438      */
439     @Benchmark
440     public int nextIntN(IntRange range, Source source) {
441         return source.getRng().nextInt(range.getN());
442     }
443 
444     /**
445      * Exercise the {@link UniformRandomProvider#nextInt()} method in a loop.
446      *
447      * @param range the range
448      * @param source Source of randomness.
449      * @return the int
450      */
451     @Benchmark
452     @OperationsPerInvocation(65_536)
453     public int nextIntNloop65536(IntRange range, Source source) {
454         int sum = 0;
455         for (int i = 0; i < 65_536; i++) {
456             sum += source.getRng().nextInt(range.getN());
457         }
458         return sum;
459     }
460 
461     /**
462      * Exercise the {@link UniformRandomProvider#nextInt(int)} method by shuffling
463      * data.
464      *
465      * @param data the data
466      * @param source Source of randomness.
467      * @return the shuffle data
468      */
469     @Benchmark
470     public int[] shuffle(IntData data, Source source) {
471         final int[] array = data.getData();
472         shuffle(array, source.getRng());
473         return array;
474     }
475 
476     /**
477      * Perform a Fischer-Yates shuffle.
478      *
479      * @param array the array
480      * @param rng the random generator
481      */
482     private static void shuffle(int[] array, UniformRandomProvider rng) {
483         for (int i = array.length - 1; i > 0; i--) {
484             // Swap index with any position down to 0
485             final int j = rng.nextInt(i);
486             final int tmp = array[j];
487             array[j] = array[i];
488             array[i] = tmp;
489         }
490     }
491 
492     /**
493      * Exercise the {@link UniformRandomProvider#nextInt(int)} method by creating
494      * random indices for shuffling data.
495      *
496      * @param data the data
497      * @param source Source of randomness.
498      * @return the sum
499      */
500     @Benchmark
501     public int pseudoShuffle(IntData data, Source source) {
502         int sum = 0;
503         for (int i = data.getData().length - 1; i > 0; i--) {
504             sum += source.getRng().nextInt(i);
505         }
506         return sum;
507     }
508 }