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}