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.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
41
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
51 private int intValue;
52
53
54
55
56 @State(Scope.Benchmark)
57 public static class IntRange {
58
59
60
61
62
63
64
65
66
67
68
69
70 @Param({"16", "17", "256", "257", "4096", "4097",
71
72 "1073741824",
73
74 "1073741825", })
75 private int n;
76
77
78
79
80
81
82 public int getN() {
83 return n;
84 }
85 }
86
87
88
89
90 @State(Scope.Benchmark)
91 public static class IntData {
92
93
94
95 @Param({ "4", "16", "256", "4096", "16384" })
96 private int size;
97
98
99 private int[] data;
100
101
102
103
104
105
106 public int[] getData() {
107 return data;
108 }
109
110
111
112
113 @Setup
114 public void setup() {
115 data = PermutationSampler.natural(size);
116 }
117 }
118
119
120
121
122 @State(Scope.Benchmark)
123 public static class Source {
124
125
126
127 @Param({ "jdk", "jdkPow2", "lemire", "lemirePow2", "lemire31", "lemire31Pow2"})
128 private String name;
129
130
131 private UniformRandomProvider rng;
132
133
134
135
136
137
138 public UniformRandomProvider getRng() {
139 return rng;
140 }
141
142
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
164
165
166
167
168 abstract static class SplitMix32 extends IntProvider {
169
170
171
172 private static final long GOLDEN_RATIO = 0x9e3779b97f4a7c15L;
173
174
175 protected long state;
176
177
178
179
180
181
182 SplitMix32(long seed) {
183 state = seed;
184 }
185
186 @Override
187 public int next() {
188 long key = state += GOLDEN_RATIO;
189
190
191 key = (key ^ (key >>> 33)) * 0x62a9d9ed799705f5L;
192 return (int) (((key ^ (key >>> 28)) * 0xcb24d0a5c88c35b3L) >>> 32);
193 }
194
195
196
197
198
199
200 void checkStrictlyPositive(int n) {
201 if (n <= 0) {
202 throw new IllegalArgumentException("not strictly positive: " + n);
203 }
204 }
205 }
206
207
208
209
210 static class JDK extends SplitMix32 {
211
212
213
214
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
237
238 static class JDKPow2 extends SplitMix32 {
239
240
241
242
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
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
271
272
273
274
275 static class Lemire extends SplitMix32 {
276
277 static final long POW_32 = 1L << 32;
278
279
280
281
282
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
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
308
309 static class LemirePow2 extends SplitMix32 {
310
311 static final long POW_32 = 1L << 32;
312
313
314
315
316
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
329 return next() & nm1;
330 }
331
332 long m = (next() & 0xffffffffL) * n;
333 long l = m & 0xffffffffL;
334 if (l < n) {
335
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
348
349
350 static class Lemire31 extends SplitMix32 {
351
352 static final long POW_32 = 1L << 32;
353
354
355
356
357
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
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
383
384
385 static class Lemire31Pow2 extends SplitMix32 {
386
387 static final long POW_32 = 1L << 32;
388
389
390
391
392
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
405 return next() & nm1;
406 }
407
408 long m = (nextInt() & 0x7fffffffL) * n;
409 long l = m & 0x7fffffffL;
410 if (l < n) {
411
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
424
425
426
427 @Benchmark
428 public int baselineInt() {
429 return intValue;
430 }
431
432
433
434
435
436
437
438
439 @Benchmark
440 public int nextIntN(IntRange range, Source source) {
441 return source.getRng().nextInt(range.getN());
442 }
443
444
445
446
447
448
449
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
463
464
465
466
467
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
478
479
480
481
482 private static void shuffle(int[] array, UniformRandomProvider rng) {
483 for (int i = array.length - 1; i > 0; i--) {
484
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
494
495
496
497
498
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 }