This is an automated email from the ASF dual-hosted git repository. dcapwell pushed a commit to branch CASSANDRA-18804 in repository https://gitbox.apache.org/repos/asf/cassandra-accord.git
commit d68c82a71e5c8bee8ee7f7ba9b7e0fb0995e14ce Author: David Capwell <[email protected]> AuthorDate: Mon Nov 27 14:03:27 2023 -0800 Fixed flakey test from RandomSourceTest as the binary search needed a ceil to find the first match in the list. Fixed a bug where the seed can get clost or put into the wrong test --- .../test/java/accord/utils/RandomSourceTest.java | 122 +++++++++++++++++---- .../test/java/accord/utils/RandomTestRunner.java | 69 ++++++++++++ 2 files changed, 168 insertions(+), 23 deletions(-) diff --git a/accord-core/src/test/java/accord/utils/RandomSourceTest.java b/accord-core/src/test/java/accord/utils/RandomSourceTest.java index 3d5aaa10..00b7eff7 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 @@ public class RandomSourceTest @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 @@ public class RandomSourceTest 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 @@ public class RandomSourceTest results[i] = random.nextBiasedInt(min, median, max); Arrays.sort(results); - int i = Arrays.binarySearch(results, median); + int i = firstBinarySearch(results, median); if (i < 0) i = -1 - i; - int j = Arrays.binarySearch(results, median + 1); + int j = firstBinarySearch(results, median + 1); if (j < 0) j = -2 - j; else --j; i -= results.length/2; @@ -74,18 +71,14 @@ public class RandomSourceTest // 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 @@ public class RandomSourceTest 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,101 @@ public class RandomSourceTest results[i] = random.nextBiasedInt(min, median, max); Arrays.sort(results); - int i = Arrays.binarySearch(results, median); + int i = firstBinarySearch(results, median); if (i < 0) i = -1 - i; - int j = Arrays.binarySearch(results, median + 1); + int j = firstBinarySearch(results, median + 1); if (j < 0) j = -2 - j; else --j; - i -= results.length/2; - j -= results.length/2; + i -= Math.abs(results.length/2); + j -= Math.abs(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 firstBinarySearch(int[] array, int target) + { + int i = Arrays.binarySearch(array, target); + return i > 0 ? ceil(array, target, 0, i) : i; + } + + private static int firstBinarySearch(long[] array, long target) + { + int i = Arrays.binarySearch(array, target); + return i > 0 ? ceil(array, target, 0, i) : i; + } + + /** + * 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; + } + + /** + * 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 00000000..9a695f6b --- /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); + } + } + } +} --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
