Fix flaky test accord.utils.RandomSourceTest.testBiasedInts (#73)
patch by David Capwell; reviewed by Benedict Elliott Smith for CASSANDRA-19114
diff --git a/accord-core/src/test/java/accord/utils/RandomSourceTest.java b/accord-core/src/test/java/accord/utils/RandomSourceTest.java
index 3d5aaa1..31e2823 100644
--- a/accord-core/src/test/java/accord/utils/RandomSourceTest.java
+++ b/accord-core/src/test/java/accord/utils/RandomSourceTest.java
@@ -19,13 +19,14 @@
package accord.utils;
import java.util.Arrays;
-import java.util.Random;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
+import static accord.utils.RandomTestRunner.test;
+
public class RandomSourceTest
{
private static final Logger logger = LoggerFactory.getLogger(RandomSourceTest.class);
@@ -33,11 +34,7 @@
@Test
public void testBiasedInts()
{
- RandomSource random = RandomSource.wrap(new Random());
- long seed = random.nextLong();
- logger.info("Seed: {}", seed);
- random.setSeed(seed);
- testBiasedInts(random, 1000, 100000, 0.01, 0.1);
+ test().check(random -> testBiasedInts(random, 1000, 100000, 0.01, 0.1));
}
private void testBiasedInts(RandomSource random, int tests, int perTest, double fudge, double perTestFudge)
@@ -54,7 +51,7 @@
overallDrift /= tests;
Assertions.assertTrue(overallDrift < fudge);
Assertions.assertTrue(overallDrift > -fudge);
- System.out.println(overallDrift);
+ logger.info("{}", overallDrift);
}
private double testOneBiasedInts(RandomSource random, int min, int median, int max, int[] results, double fudge)
@@ -63,9 +60,9 @@
results[i] = random.nextBiasedInt(min, median, max);
Arrays.sort(results);
- int i = Arrays.binarySearch(results, median);
+ int i = ceil(results, median);
if (i < 0) i = -1 - i;
- int j = Arrays.binarySearch(results, median + 1);
+ int j = ceil(results, median + 1);
if (j < 0) j = -2 - j;
else --j;
i -= results.length/2;
@@ -74,18 +71,14 @@
// find minimum distance of the target median value from the actual median value
double distance = Math.abs(i) < Math.abs(j) ? i : j;
double ratio = distance / results.length;
- Assertions.assertTrue(ratio < fudge);
+ Assertions.assertTrue(ratio < fudge, () -> String.format("ratio (%,2f) >= fudge (%,2f); results.length (%,d)", ratio, fudge, results.length));
return ratio;
}
@Test
public void testBiasedLongs()
{
- RandomSource random = RandomSource.wrap(new Random());
- long seed = random.nextLong();
- logger.info("Seed: {}", seed);
- random.setSeed(seed);
- testBiasedLongs(random, 1000, 100000, 0.01, 0.1);
+ test().check(random -> testBiasedLongs(random, 1000, 100000, 0.01, 0.1));
}
private void testBiasedLongs(RandomSource random, int tests, int perTest, double fudge, double perTestFudge)
@@ -102,7 +95,7 @@
overallDrift /= tests;
Assertions.assertTrue(overallDrift < fudge);
Assertions.assertTrue(overallDrift > -fudge);
- System.out.println(overallDrift);
+ logger.info("{}", overallDrift);
}
private double testOneBiasedLongs(RandomSource random, int min, int median, int max, long[] results, double fudge)
@@ -111,18 +104,99 @@
results[i] = random.nextBiasedInt(min, median, max);
Arrays.sort(results);
- int i = Arrays.binarySearch(results, median);
+ int i = ceil(results, median);
if (i < 0) i = -1 - i;
- int j = Arrays.binarySearch(results, median + 1);
+ int j = ceil(results, median + 1);
if (j < 0) j = -2 - j;
else --j;
i -= results.length/2;
j -= results.length/2;
// find minimum distance of the target median value from the actual median value
- double distance = Math.abs(i) < Math.abs(j) ? i : j;
+ double distance = Math.min(i, j);
+
double ratio = distance / results.length;
- Assertions.assertTrue(ratio < fudge);
- return ratio;
+ Assertions.assertTrue(ratio < fudge, () -> String.format("ratio (%,2f) >= fudge (%,2f); results.length (%,d)", ratio, fudge, results.length));
+ return distance / results.length;
+ }
+
+ private static int ceil(int[] array, int target)
+ {
+ return ceil(array, target, 0, array.length);
+ }
+
+ /**
+ * Yields the minimum index in the range <code>a[fromIndex, toIndex)</code> containing a value that is greater than or equal to the provided key.
+ * The method requires (but does not check) that the range is sorted in ascending order; a result of toIndex indicates no value greater than or
+ * equal to the key exists in the range
+ *
+ * @param a list to look in, where this.isOrdered(a) holds
+ * @param key key to find
+ * @param fromIndex first index to look in
+ * @param toIndex first index to exclude from search (i.e. exclusive upper bound)
+ * @return minimum index in the range containing a value that is greater than or equal to the provided key
+ */
+ private static int ceil(final int[] a, final int key, final int fromIndex, final int toIndex)
+ {
+ // This was taken from https://github.com/belliottsmith/jjoost/blob/0b40ae494af408dfecd4527ac9e9d1ec323315e3/jjoost-base/src/org/jjoost/util/order/IntOrder.java#L80
+ int i = fromIndex - 1;
+ int j = toIndex;
+
+ while (i < j - 1)
+ {
+
+ // { a[i] < v ^ a[j] >= v }
+
+ final int m = (i + j) >>> 1;
+ final long v = a[m];
+
+ if (v >= key) j = m;
+ else i = m;
+
+ // { a[m] >= v => a[j] >= v => a[i] < v ^ a[j] >= v }
+ // { a[m] < v => a[i] < v => a[i] < v ^ a[j] >= v }
+
+ }
+ return j;
+ }
+
+ private static int ceil(long[] array, long target)
+ {
+ return ceil(array, target, 0, array.length);
+ }
+
+ /**
+ * Yields the minimum index in the range <code>a[fromIndex, toIndex)</code> containing a value that is greater than or equal to the provided key.
+ * The method requires (but does not check) that the range is sorted in ascending order; a result of toIndex indicates no value greater than or
+ * equal to the key exists in the range
+ *
+ * @param a list to look in, where this.isOrdered(a) holds
+ * @param key key to find
+ * @param fromIndex first index to look in
+ * @param toIndex first index to exclude from search (i.e. exclusive upper bound)
+ * @return minimum index in the range containing a value that is greater than or equal to the provided key
+ */
+ private static int ceil(final long[] a, final long key, final int fromIndex, final int toIndex)
+ {
+ // This was taken from https://github.com/belliottsmith/jjoost/blob/0b40ae494af408dfecd4527ac9e9d1ec323315e3/jjoost-base/src/org/jjoost/util/order/IntOrder.java#L80
+ int i = fromIndex - 1;
+ int j = toIndex;
+
+ while (i < j - 1)
+ {
+
+ // { a[i] < v ^ a[j] >= v }
+
+ final int m = (i + j) >>> 1;
+ final long v = a[m];
+
+ if (v >= key) j = m;
+ else i = m;
+
+ // { a[m] >= v => a[j] >= v => a[i] < v ^ a[j] >= v }
+ // { a[m] < v => a[i] < v => a[i] < v ^ a[j] >= v }
+
+ }
+ return j;
}
}
diff --git a/accord-core/src/test/java/accord/utils/RandomTestRunner.java b/accord-core/src/test/java/accord/utils/RandomTestRunner.java
new file mode 100644
index 0000000..9a695f6
--- /dev/null
+++ b/accord-core/src/test/java/accord/utils/RandomTestRunner.java
@@ -0,0 +1,69 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package accord.utils;
+
+import java.util.function.Consumer;
+
+/**
+ * The main difference between this class and {@link Property} is that this class does not reference {@link Gen} and some
+ * authors wish to avoid that interface, but need to correctly work with randomness in a test that is reproducable when
+ * issues are found from CI.
+ *
+ * {@link Builder#check(Consumer)} is functinally the same as the following from {@link Property}
+ *
+ * {@code qt().withExamples(1).check(testcase); }
+ */
+public class RandomTestRunner
+{
+ public static Builder test()
+ {
+ return new Builder();
+ }
+
+ public static class Builder
+ {
+ private Long seed = null;
+
+ /**
+ * When a test failure is detected, set the seed for the test using this method to cause it to get repeated
+ */
+ @SuppressWarnings("unused")
+ public Builder withSeed(long seed)
+ {
+ this.seed = seed;
+ return this;
+ }
+
+ public void check(Consumer<RandomSource> fn)
+ {
+ RandomSource random = new DefaultRandom();
+ if (seed == null)
+ seed = random.nextLong();
+ random.setSeed(seed);
+ try
+ {
+ fn.accept(random);
+ }
+ catch (Throwable t)
+ {
+ throw new AssertionError("Unexpected error for seed " + seed, t);
+ }
+ }
+ }
+}
