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.distribution;
19
20 import org.apache.commons.rng.RestorableUniformRandomProvider;
21 import org.apache.commons.rng.UniformRandomProvider;
22 import org.apache.commons.rng.sampling.distribution.DiscreteUniformSampler;
23 import org.apache.commons.rng.sampling.distribution.SharedStateDiscreteSampler;
24 import org.apache.commons.rng.simple.RandomSource;
25 import org.openjdk.jmh.annotations.Benchmark;
26 import org.openjdk.jmh.annotations.BenchmarkMode;
27 import org.openjdk.jmh.annotations.Mode;
28 import org.openjdk.jmh.annotations.Warmup;
29 import org.openjdk.jmh.infra.Blackhole;
30 import org.openjdk.jmh.annotations.Measurement;
31 import org.openjdk.jmh.annotations.State;
32 import org.openjdk.jmh.annotations.Fork;
33 import org.openjdk.jmh.annotations.Scope;
34 import org.openjdk.jmh.annotations.Setup;
35 import org.openjdk.jmh.annotations.OutputTimeUnit;
36 import org.openjdk.jmh.annotations.Param;
37
38 import java.util.concurrent.TimeUnit;
39
40 /**
41 * Executes benchmark to compare the speed of generation of integer numbers in a positive range
42 * using the {@link DiscreteUniformSampler} or {@link UniformRandomProvider#nextInt(int)}.
43 */
44 @BenchmarkMode(Mode.AverageTime)
45 @OutputTimeUnit(TimeUnit.NANOSECONDS)
46 @Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
47 @Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
48 @State(Scope.Benchmark)
49 @Fork(value = 1, jvmArgs = { "-server", "-Xms128M", "-Xmx128M" })
50 public class DiscreteUniformSamplerGenerationPerformance {
51 /** The number of samples. */
52 @Param({
53 "1",
54 "2",
55 "4",
56 "8",
57 "16",
58 "1000000",
59 })
60 private int samples;
61
62 /**
63 * The benchmark state (retrieve the various "RandomSource"s).
64 */
65 @State(Scope.Benchmark)
66 public static class Sources {
67 /**
68 * RNG providers.
69 *
70 * <p>Use different speeds.</p>
71 *
72 * @see <a href="https://commons.apache.org/proper/commons-rng/userguide/rng.html">
73 * Commons RNG user guide</a>
74 */
75 @Param({"SPLIT_MIX_64",
76 // Comment in for slower generators
77 //"MWC_256", "KISS", "WELL_1024_A",
78 //"WELL_44497_B"
79 })
80 private String randomSourceName;
81
82 /** RNG. */
83 private RestorableUniformRandomProvider generator;
84
85 /**
86 * @return the RNG.
87 */
88 public UniformRandomProvider getGenerator() {
89 return generator;
90 }
91
92 /** Instantiates generator. */
93 @Setup
94 public void setup() {
95 final RandomSource randomSource = RandomSource.valueOf(randomSourceName);
96 generator = randomSource.create();
97 }
98 }
99
100 /**
101 * The upper range for the {@code int} generation.
102 */
103 @State(Scope.Benchmark)
104 public static class IntRange {
105 /**
106 * The upper range for the {@code int} generation.
107 *
108 * <p>Note that the while loop uses a rejection algorithm. From the Javadoc for java.util.Random:</p>
109 *
110 * <pre>
111 * "The probability of a value being rejected depends on n. The
112 * worst case is n=2^30+1, for which the probability of a reject is 1/2,
113 * and the expected number of iterations before the loop terminates is 2."
114 * </pre>
115 */
116 @Param({
117 "256", // Even: 1 << 8
118 "257", // Prime number
119 "1073741825", // Worst case: (1 << 30) + 1
120 })
121 private int upperBound;
122
123 /**
124 * Gets the upper bound.
125 *
126 * @return the upper bound
127 */
128 public int getUpperBound() {
129 return upperBound;
130 }
131 }
132
133 // Benchmark methods.
134 // Avoid consuming the generated values inside the loop. Use a sum and
135 // consume at the end. This reduces the run-time as the BlackHole has
136 // a relatively high overhead compared with number generation.
137 // Subtracting the baseline from the other timings provides a measure
138 // of the extra work done by the algorithm to produce unbiased samples in a range.
139
140 /**
141 * @param bh the data sink
142 * @param source the source
143 */
144 @Benchmark
145 public void nextIntBaseline(Blackhole bh, Sources source) {
146 int sum = 0;
147 for (int i = 0; i < samples; i++) {
148 sum += source.getGenerator().nextInt();
149 }
150 bh.consume(sum);
151 }
152
153 /**
154 * @param bh the data sink
155 * @param source the source
156 * @param range the range
157 */
158 @Benchmark
159 public void nextIntRange(Blackhole bh, Sources source, IntRange range) {
160 final int n = range.getUpperBound();
161 int sum = 0;
162 for (int i = 0; i < samples; i++) {
163 sum += source.getGenerator().nextInt(n);
164 }
165 bh.consume(sum);
166 }
167
168 /**
169 * @param bh the data sink
170 * @param source the source
171 * @param range the range
172 */
173 @Benchmark
174 public void nextDiscreteUniformSampler(Blackhole bh, Sources source, IntRange range) {
175 // Note: The sampler upper bound is inclusive.
176 final SharedStateDiscreteSampler sampler = DiscreteUniformSampler.of(
177 source.getGenerator(), 0, range.getUpperBound() - 1);
178 int sum = 0;
179 for (int i = 0; i < samples; i++) {
180 sum += sampler.sample();
181 }
182 bh.consume(sum);
183 }
184 }