001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017
018package org.apache.commons.rng.examples.jmh.core;
019
020import org.apache.commons.rng.UniformRandomProvider;
021import org.apache.commons.rng.core.source32.IntProvider;
022import org.apache.commons.rng.sampling.PermutationSampler;
023import org.openjdk.jmh.annotations.Benchmark;
024import org.openjdk.jmh.annotations.BenchmarkMode;
025import org.openjdk.jmh.annotations.Fork;
026import org.openjdk.jmh.annotations.Measurement;
027import org.openjdk.jmh.annotations.Mode;
028import org.openjdk.jmh.annotations.OperationsPerInvocation;
029import org.openjdk.jmh.annotations.OutputTimeUnit;
030import org.openjdk.jmh.annotations.Param;
031import org.openjdk.jmh.annotations.Scope;
032import org.openjdk.jmh.annotations.Setup;
033import org.openjdk.jmh.annotations.State;
034import org.openjdk.jmh.annotations.Warmup;
035
036import java.util.concurrent.ThreadLocalRandom;
037import java.util.concurrent.TimeUnit;
038
039/**
040 * Executes benchmark to compare the speed of random number generators to create
041 * an int value in a range.
042 */
043@BenchmarkMode(Mode.AverageTime)
044@OutputTimeUnit(TimeUnit.NANOSECONDS)
045@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
046@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
047@State(Scope.Benchmark)
048@Fork(value = 1, jvmArgs = { "-server", "-Xms128M", "-Xmx128M" })
049public class RngNextIntInRangeBenchmark {
050    /** The value. Must NOT be final to prevent JVM optimisation! */
051    private int intValue;
052
053    /**
054     * The upper range for the {@code int} generation.
055     */
056    @State(Scope.Benchmark)
057    public static class IntRange {
058        /**
059         * The upper range for the {@code int} generation.
060         *
061         * <p>Note that the while loop uses a rejection algorithm. From the Javadoc for
062         * java.util.Random:</p>
063         *
064         * <pre>
065         * "The probability of a value being rejected depends on n. The
066         * worst case is n=2^30+1, for which the probability of a reject is 1/2,
067         * and the expected number of iterations before the loop terminates is 2."
068         * </pre>
069         */
070        @Param({"16", "17", "256", "257", "4096", "4097",
071                // Worst case power-of-2: (1 << 30)
072                "1073741824",
073                // Worst case: (1 << 30) + 1
074                "1073741825", })
075        private int n;
076
077        /**
078         * Gets the upper bound {@code n}.
079         *
080         * @return the upper bound
081         */
082        public int getN() {
083            return n;
084        }
085    }
086
087    /**
088     * The data used for the shuffle benchmark.
089     */
090    @State(Scope.Benchmark)
091    public static class IntData {
092        /**
093         * The size of the data.
094         */
095        @Param({ "4", "16", "256", "4096", "16384" })
096        private int size;
097
098        /** The data. */
099        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}