This is an automated email from the ASF dual-hosted git repository.
aherbert pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-rng.git
The following commit(s) were added to refs/heads/master by this push:
new e37e90e4 RNG-187: Add benchmarks for shuffle without index checks
e37e90e4 is described below
commit e37e90e463f67d186fa68dd501f1c24a31a08cb1
Author: Alex Herbert <[email protected]>
AuthorDate: Mon Aug 26 22:14:38 2024 +0100
RNG-187: Add benchmarks for shuffle without index checks
---
.../jmh/sampling/ArrayShuffleBenchmark.java | 57 ++++++++++++++++++++--
.../jmh/sampling/ArrayShuffleBenchmarkTest.java | 20 ++++++++
2 files changed, 73 insertions(+), 4 deletions(-)
diff --git
a/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/sampling/ArrayShuffleBenchmark.java
b/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/sampling/ArrayShuffleBenchmark.java
index 419b44d0..63a84652 100644
---
a/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/sampling/ArrayShuffleBenchmark.java
+++
b/commons-rng-examples/examples-jmh/src/main/java/org/apache/commons/rng/examples/jmh/sampling/ArrayShuffleBenchmark.java
@@ -152,7 +152,10 @@ public class ArrayShuffleBenchmark {
/**
* Method name.
*/
- @Param({"shuffle", "shuffle2", "shuffle3", "shuffle4"})
+ @Param({"shuffle1",
+ // Effectively the same speed as shuffle1
+ //"shuffle1a",
+ "shuffle2", "shuffle3", "shuffle4"})
private String method;
/** Shuffle function. */
@@ -172,8 +175,10 @@ public class ArrayShuffleBenchmark {
*/
@Setup
public void setup() {
- if ("shuffle".equals(method)) {
+ if ("shuffle1".equals(method)) {
fun = ArrayShuffleBenchmark::shuffle1;
+ } else if ("shuffle1a".equals(method)) {
+ fun = ArrayShuffleBenchmark::shuffle1a;
} else if ("shuffle2".equals(method)) {
fun = ArrayShuffleBenchmark::shuffle2;
} else if ("shuffle3".equals(method)) {
@@ -214,6 +219,50 @@ public class ArrayShuffleBenchmark {
return array;
}
+ /**
+ * Generates an {@code int} value between 0 (inclusive) and the specified
value
+ * (exclusive).
+ *
+ * <p>Taken from {@code o.a.c.rng.UniformRandomProviderSupport}. This is
used
+ * to benchmark elimination of the conditional check for a negative index
in
+ * {@link UniformRandomProvider#nextInt(int)}.
+ *
+ * @param source Source of randomness.
+ * @param n Bound on the random number to be returned. Must be strictly
positive.
+ * @return a random {@code int} value between 0 (inclusive) and {@code n}
(exclusive).
+ */
+ static int nextInt(UniformRandomProvider source,
+ int n) {
+ // Lemire (2019): Fast Random Integer Generation in an Interval
+ // https://arxiv.org/abs/1805.10941
+ long m = (source.nextInt() & 0xffffffffL) * n;
+ long l = m & 0xffffffffL;
+ if (l < n) {
+ // 2^32 % n
+ final long t = POW_32 % n;
+ while (l < t) {
+ m = (source.nextInt() & 0xffffffffL) * n;
+ l = m & 0xffffffffL;
+ }
+ }
+ return (int) (m >>> 32);
+ }
+
+ /**
+ * Shuffles the entries of the given array.
+ * Uses a Fisher-Yates shuffle.
+ *
+ * @param rng Source of randomness.
+ * @param array Array whose entries will be shuffled (in-place).
+ * @return a reference to the given array
+ */
+ static int[] shuffle1a(UniformRandomProvider rng, int[] array) {
+ for (int i = array.length; i > 1; i--) {
+ swap(array, i - 1, nextInt(rng, i));
+ }
+ return array;
+ }
+
/**
* Return two random values in {@code [0, range1)} and {@code [0,
range2)}. The
* product bound is used for the reject algorithm. See Brackett-Rozinsky
and Lemire.
@@ -283,7 +332,7 @@ public class ArrayShuffleBenchmark {
}
/**
- * Return two random values in {@code [0, range1)}, {@code [0, range2)}
+ * Return three random values in {@code [0, range1)}, {@code [0, range2)}
* and {@code [0, range3)}. The
* product bound is used for the reject algorithm. See Brackett-Rozinsky
and Lemire.
*
@@ -372,7 +421,7 @@ public class ArrayShuffleBenchmark {
}
/**
- * Return two random values in {@code [0, range1)}, {@code [0, range2)},
+ * Return four random values in {@code [0, range1)}, {@code [0, range2)},
* {@code [0, range3)} and {@code [0, range4)}. The
* product bound is used for the reject algorithm. See Brackett-Rozinsky
and Lemire.
*
diff --git
a/commons-rng-examples/examples-jmh/src/test/java/org/apache/commons/rng/examples/jmh/sampling/ArrayShuffleBenchmarkTest.java
b/commons-rng-examples/examples-jmh/src/test/java/org/apache/commons/rng/examples/jmh/sampling/ArrayShuffleBenchmarkTest.java
index 4922ee7e..7a105824 100644
---
a/commons-rng-examples/examples-jmh/src/test/java/org/apache/commons/rng/examples/jmh/sampling/ArrayShuffleBenchmarkTest.java
+++
b/commons-rng-examples/examples-jmh/src/test/java/org/apache/commons/rng/examples/jmh/sampling/ArrayShuffleBenchmarkTest.java
@@ -125,4 +125,24 @@ class ArrayShuffleBenchmarkTest {
final double p = new ChiSquareTest().chiSquareTest(observed);
Assertions.assertFalse(p < 1e-3, () -> "p-value too small: " + p);
}
+
+ @ParameterizedTest
+ @CsvSource({
+ "257",
+ "8073",
+ })
+ void testShuffle1a(int length) {
+ final int[] a = PermutationSampler.natural(length);
+ final int[] b = a.clone();
+ final RandomSource source = RandomSource.XO_RO_SHI_RO_128_PP;
+ final byte[] seed = source.createSeed();
+ final UniformRandomProvider rng1 = source.create(seed);
+ final UniformRandomProvider rng2 = source.create(seed);
+ final int samples = 10;
+ for (int j = 0; j < samples; j++) {
+ ArrayShuffleBenchmark.shuffle1(rng1, a);
+ ArrayShuffleBenchmark.shuffle1(rng2, b);
+ Assertions.assertArrayEquals(a, b);
+ }
+ }
}
