This is an automated email from the ASF dual-hosted git repository.
asf-gitbox-commits pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-statistics.git
The following commit(s) were added to refs/heads/master by this push:
new 325a9b04 STATISTICS-99: Configurable allocation size for the exact p
computation
325a9b04 is described below
commit 325a9b044cb9e0998aabd3cf81e999998cfeeb85
Author: Alex Herbert <[email protected]>
AuthorDate: Sat Aug 29 19:55:24 2026 +0100
STATISTICS-99: Configurable allocation size for the exact p computation
---
.../statistics/inference/MannWhitneyUTest.java | 55 +++++++++++++++++++++-
.../statistics/inference/MannWhitneyUTestTest.java | 28 ++++++++++-
src/changes/changes.xml | 7 ++-
3 files changed, 87 insertions(+), 3 deletions(-)
diff --git
a/commons-statistics-inference/src/main/java/org/apache/commons/statistics/inference/MannWhitneyUTest.java
b/commons-statistics-inference/src/main/java/org/apache/commons/statistics/inference/MannWhitneyUTest.java
index 8807a80c..e7f32458 100644
---
a/commons-statistics-inference/src/main/java/org/apache/commons/statistics/inference/MannWhitneyUTest.java
+++
b/commons-statistics-inference/src/main/java/org/apache/commons/statistics/inference/MannWhitneyUTest.java
@@ -51,6 +51,12 @@ public final class MannWhitneyUTest {
* modified when holding the lock. When the storage is determined to be
the correct
* size it can be returned for read/write to the array when not holding
the lock. */
private static SoftReference<double[][][]> cacheF = new
SoftReference<>(null); // @GuardedBy("LOCK")
+ /** Limit on the tabulation byte allocation size for the exact
+ * p-value computation. The default 2^29, or 512 MiB, is larger than any
+ * tabulation created using the limits configured for the
+ * {@linkplain PValueMethod#AUTO auto} p-value mode. */
+ private static final long MAX_BYTES = Long.getLong(
+ "org.apache.commons.statistics.inference.MannWhitneyUTest.maxBytes",
1L << 29);
/** Default instance. */
private static final MannWhitneyUTest DEFAULT = new MannWhitneyUTest(
AlternativeHypothesis.TWO_SIDED, PValueMethod.AUTO, true, 0);
@@ -157,6 +163,11 @@ public final class MannWhitneyUTest {
/**
* Return an instance with the configured p-value method.
*
+ * <p><strong>Note:</strong> Use of the {@link PValueMethod#EXACT} method
may require
+ * a large memory allocation for the computation tables. This is limited
to 512 MiB
+ * but can be increased using a system property. See the
+ * {@link #test(double[], double[])} documentation for details.
+ *
* @param v Value.
* @return an instance
* @throws IllegalArgumentException if the value is not in the allowed
options or is null
@@ -259,7 +270,12 @@ public final class MannWhitneyUTest {
* or {@code min(n, m) <= 37} for any {@code max(n, m)}.
* An {@link OutOfMemoryError} is not expected using the
* limits configured for the {@linkplain PValueMethod#AUTO auto} p-value
computation
- * as the maximum required memory is approximately 23 MiB.
+ * as the maximum required memory is approximately 2.9 MiB.
+ * To avoid memory errors the tabulation size is limited to {@code 2^29}
bytes
+ * (512 MiB); a <em>user-requested</em> exact computation that would
+ * exceed this limit reverts to the asymptotic approximation. The limit is
+ * configurable using the system property
+ * {@code
org.apache.commons.statistics.inference.MannWhitneyUTest.maxBytes}.
*
* @param x First sample values.
* @param y Second sample values.
@@ -409,6 +425,12 @@ public final class MannWhitneyUTest {
final int n1 = Math.min(m, n);
final int n2 = Math.max(m, n);
+ // Limit the size of the tabulation storage.
+ // Note: the CDF is computed using k <= min(u1, u2).
+ if (isOversizedAllocation(Math.min(u1, u2) + 1.0, n1 + 1.0, n2 + 1.0))
{
+ return -1;
+ }
+
// Return the correct side:
if (alternative == AlternativeHypothesis.GREATER_THAN) {
// sf(u1 - 1)
@@ -546,6 +568,22 @@ public final class MannWhitneyUTest {
// and copying all old values.
final int sn = Math.max(n1, n + 1);
final int sk = Math.max(k1, k + 1);
+ // Growing combines the dimensions of the previous and
requested
+ // storage; this can exceed the table size limit even when each
+ // individual request is below it. In that case discard the
previous
+ // computation and allocate the requested size (which has been
checked
+ // against the limit by the caller). Any other thread using the
+ // previous storage is not affected.
+ if (isOversizedAllocation(Math.max(m1, m + 1.0), sn, sk)) {
+ f = new double[m + 1][n + 1][k + 1];
+ for (final double[][] a : f) {
+ for (final double[] b : a) {
+ initialize(b);
+ }
+ }
+ cacheF = new SoftReference<>(f);
+ return f;
+ }
if (growM) {
// Entirely new region
f = Arrays.copyOf(f, m + 1);
@@ -587,6 +625,21 @@ public final class MannWhitneyUTest {
}
}
+ /**
+ * Test an allocation of an array of size [x][y][z] against the
+ * the configured maximum number of bytes.
+ *
+ * <p>Uses floating-point arguments to avoid overflow.
+ *
+ * @param x Size x (assumed to be positive)
+ * @param y Size y (assumed to be positive)
+ * @param z Size z (assumed to be positive)
+ * @return true if the byte size is too large
+ */
+ private static boolean isOversizedAllocation(double x, double y, double z)
{
+ return x * y * z * Double.BYTES > MAX_BYTES;
+ }
+
/**
* Initialize the array for f(m, n, x).
* Set value to 1 for x=0; otherwise {@link #UNSET}.
diff --git
a/commons-statistics-inference/src/test/java/org/apache/commons/statistics/inference/MannWhitneyUTestTest.java
b/commons-statistics-inference/src/test/java/org/apache/commons/statistics/inference/MannWhitneyUTestTest.java
index f43b5189..28cf5c3f 100644
---
a/commons-statistics-inference/src/test/java/org/apache/commons/statistics/inference/MannWhitneyUTestTest.java
+++
b/commons-statistics-inference/src/test/java/org/apache/commons/statistics/inference/MannWhitneyUTestTest.java
@@ -350,6 +350,18 @@ class MannWhitneyUTestTest {
Assertions.assertEquals(-1, MannWhitneyUTest.calculateExactPValue(1L
<< 32, m, n, AlternativeHypothesis.TWO_SIDED));
}
+ @Test
+ void testCalculateExactPValueTableSizeLimit() {
+ // The tabulation of f, of size (n1+1)*(n2+1)*(min(u1, u2)+1), is
limited to a
+ // maximum size (2^26 values by default).
+ // Larger user-requested exact computations cannot be computed exactly
and
+ // revert to the asymptotic approximation. binom(m + n, m) is finite
for both.
+ Assertions.assertEquals(-1,
+ MannWhitneyUTest.calculateExactPValue(1234, 37, 1000000,
AlternativeHypothesis.TWO_SIDED));
+ Assertions.assertEquals(-1,
+ MannWhitneyUTest.calculateExactPValue(125000, 500, 500,
AlternativeHypothesis.TWO_SIDED));
+ }
+
/**
* Test the exact CDF computation.
* This hits all edge cases for expanding the cache of f.
@@ -361,7 +373,7 @@ class MannWhitneyUTestTest {
@Order(1)
void testCDF(int u, int m, int n, double p) {
// Use 'less than' to compute the wilcox distribution CDF(u)
- TestUtils.assertProbability(p,
MannWhitneyUTest.calculateExactPValue(u, m, n,
AlternativeHypothesis.LESS_THAN), 1e-14, "p-value");
+ TestUtils.assertProbability(p,
MannWhitneyUTest.calculateExactPValue(u, m, n,
AlternativeHypothesis.LESS_THAN), 5e-14, "p-value");
}
static Stream<Arguments> testCDF() {
@@ -407,6 +419,20 @@ class MannWhitneyUTestTest {
builder.add(Arguments.of(7890, 100, 100, 0.99999999999990418775));
// 22.447 sec
builder.add(Arguments.of(8901, 100, 100, 1.0));
+
+ // Coverage test for discarding the current f(m, n, k) table.
+ //
+ // Create an allowed allocation that in combination with
+ // the existing table size exceeds the max byte limit.
+ // Max size = 2^26 values = 67,108,864
+ // 601 * 331 * 331 = 65,846,161 (0.981184259)
+ // 601 * 341 * 321 = 65,786,061 (0.980288699)
+ // Combined size is too large:
+ // 601 * 341 * 331 = 67,835,471 (1.010827288)
+ // Expected results from R computed within milliseconds.
+ // These results have the highest relative error of the test cases.
+ builder.add(Arguments.of(600, 330, 330, 6.1399257003662415563e-173));
// rel.error 1.36e-14
+ builder.add(Arguments.of(600, 340, 320, 8.3097576360262207539e-173));
// rel.error 4.98e-14
return builder.build();
}
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index ef612916..fc14f6d5 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -53,12 +53,17 @@ If the output is not quite correct, check for invisible
trailing spaces!
</properties>
<body>
<release version="1.4" date="TBD" description="Adds new features (requires
Java 8).">
+ <action dev="aherbert" type="fix" due-to="Security scan, Alex Herbert"
issue="STATISTICS-99">
+ "MannWhitneyUTest": Limit the allocation size for the exact p-value
+ computation. The maximum byte allocation can be configured using a
system
+ property. Behaviour using the default AUTO p-value computation is
unchanged.
+ </action>
<action dev="aherbert" type="update" due-to="Security scan, Alex
Herbert">
"KolmogorovSmirnovTest": Bound the maximum number of terms allowed
during
the exact p-value computation for the two-sample two-sided statistic
with
unequal sample sizes. The caller will fall-back to the aysymptotic
computation to avoid an impractical computation. Behaviour using the
- default AUTO limit is unchanged.
+ default AUTO p-value computation is unchanged.
</action>
<action dev="aherbert" type="update" due-to="Security scan, Alex
Herbert">
"ZipfDistribution": Update documentation on possible long runtimes when
