This is an automated email from the ASF dual-hosted git repository.
krickert pushed a commit to branch OPENNLP-1903-NameFinder-Threading
in repository https://gitbox.apache.org/repos/asf/opennlp.git
The following commit(s) were added to
refs/heads/OPENNLP-1903-NameFinder-Threading by this push:
new b7dc4018f OPENNLP-1903: Tighten the BeamSearch chain-node change after
review pre-flight
b7dc4018f is described below
commit b7dc4018f706732c9a7662c5dcc2eb9b0c2e6034
Author: Kristian Rickert <[email protected]>
AuthorDate: Mon Aug 3 07:43:45 2026 -0400
OPENNLP-1903: Tighten the BeamSearch chain-node change after review
pre-flight
Simplify SearchNode by dropping the single-use outcome array cache, share
one seeded MaxentModel fixture between the equivalence test and the JMH
benchmark, convert the equivalence test matrices to parameterized tests,
and anchor benchmark/test documentation to the JIRA issue instead of
relative history. Attribute the real-model benchmark result to the
en-ner-person.bin model.
---
.../src/main/java/opennlp/tools/ml/BeamSearch.java | 51 ++-
opennlp-core/opennlp-runtime/BENCHMARKS.md | 18 +-
.../java/opennlp/tools/ml/BeamSearchBenchmark.java | 105 +----
.../tools/ml/BeamSearchEquivalenceTest.java | 495 ++++++++++-----------
.../java/opennlp/tools/ml/SeededMaxentModel.java | 120 +++++
5 files changed, 404 insertions(+), 385 deletions(-)
diff --git
a/opennlp-core/opennlp-ml/opennlp-ml-commons/src/main/java/opennlp/tools/ml/BeamSearch.java
b/opennlp-core/opennlp-ml/opennlp-ml-commons/src/main/java/opennlp/tools/ml/BeamSearch.java
index f698ec495..155d96da2 100644
---
a/opennlp-core/opennlp-ml/opennlp-ml-commons/src/main/java/opennlp/tools/ml/BeamSearch.java
+++
b/opennlp-core/opennlp-ml/opennlp-ml-commons/src/main/java/opennlp/tools/ml/BeamSearch.java
@@ -75,14 +75,14 @@ public class BeamSearch implements
SequenceClassificationModel, AutoCloseable {
}
/**
- * Immutable chain node used only inside
+ * Immutable node in a backward-linked chain of outcome candidates, used
only inside
* {@link #bestSequences(int, Object[], Object[], double,
BeamSearchContextGenerator, SequenceValidator)}.
- * Each child links to its parent instead of copying the parent's
outcome/probability lists,
- * so expanding a candidate is O(1); the outcome array is materialized
lazily and cached.
- * Score accumulation ({@code parent.score + StrictMath.log(prob)}) mirrors
- * {@link Sequence#Sequence(Sequence, String, double)} bit-for-bit, and
{@link #compareTo}
- * mirrors {@link Sequence#compareTo}, so the search is behavior-identical
to running the
- * queues over {@link Sequence} directly.
+ * A node stores its own outcome plus a parent link, so extending a
candidate is O(1);
+ * the full outcome array is materialized only when a candidate is expanded.
+ * Score accumulation ({@code parent.score + StrictMath.log(prob)}) and
+ * {@link #compareTo(SearchNode)} must stay in lockstep with
+ * {@link Sequence#Sequence(Sequence, String, double)} and {@link
Sequence#compareTo(Sequence)}
+ * to keep search results bit-identical to a search over {@link Sequence}
instances.
*/
private static final class SearchNode implements Comparable<SearchNode> {
private final SearchNode parent;
@@ -90,8 +90,10 @@ public class BeamSearch implements
SequenceClassificationModel, AutoCloseable {
private final double prob;
private final double score;
private final int size;
- private String[] outcomesCache; // lazily built; nodes are never mutated,
so the cache stays valid
+ /**
+ * Creates the root node: the empty candidate with score {@code 0}.
+ */
private SearchNode() {
this.parent = null;
this.outcome = null;
@@ -100,6 +102,13 @@ public class BeamSearch implements
SequenceClassificationModel, AutoCloseable {
this.size = 0;
}
+ /**
+ * Creates a candidate extending {@code parent} by one outcome.
+ *
+ * @param parent The candidate to extend. Must not be {@code null}.
+ * @param outcome The outcome to append.
+ * @param prob The probability of {@code outcome}.
+ */
private SearchNode(SearchNode parent, String outcome, double prob) {
this.parent = parent;
this.outcome = outcome;
@@ -108,20 +117,22 @@ public class BeamSearch implements
SequenceClassificationModel, AutoCloseable {
this.size = parent.size + 1;
}
+ /**
+ * @return The outcomes on the path from the root to this node, in
sequence order.
+ */
private String[] outcomes() {
- String[] cached = outcomesCache;
- if (cached == null) {
- cached = new String[size];
- SearchNode node = this;
- for (int i = size - 1; i >= 0; i--) {
- cached[i] = node.outcome;
- node = node.parent;
- }
- outcomesCache = cached;
+ final String[] outcomes = new String[size];
+ SearchNode node = this;
+ for (int i = size - 1; i >= 0; i--) {
+ outcomes[i] = node.outcome;
+ node = node.parent;
}
- return cached;
+ return outcomes;
}
+ /**
+ * Orders nodes by descending score, mirroring {@link
Sequence#compareTo(Sequence)}.
+ */
@Override
public int compareTo(SearchNode other) {
return Double.compare(other.score, this.score);
@@ -250,8 +261,8 @@ public class BeamSearch implements
SequenceClassificationModel, AutoCloseable {
probs[j] = node.prob;
node = node.parent;
}
- // Sequence.add accumulates score += StrictMath.log(p) in the same order
as the chain,
- // so the rebuilt Sequence is bit-identical to one built directly during
the search.
+ // Sequence.add accumulates score += StrictMath.log(p) per element, so
rebuilding in
+ // chain order yields a score bit-identical to the node's accumulated
score.
final Sequence seq = new Sequence();
for (int j = 0; j < outs.length; j++) {
seq.add(outs[j], probs[j]);
diff --git a/opennlp-core/opennlp-runtime/BENCHMARKS.md
b/opennlp-core/opennlp-runtime/BENCHMARKS.md
index 6e6f8aa9c..5ba39bc50 100644
--- a/opennlp-core/opennlp-runtime/BENCHMARKS.md
+++ b/opennlp-core/opennlp-runtime/BENCHMARKS.md
@@ -129,11 +129,12 @@ cache provides measurable benefit.
validator). One op = one `bestSequence` call; invocations rotate through a
pool of 64 seeded inputs. The `sequenceLength` param (8/64/256) is the key
axis: the O(n^2) per-candidate outcome-list copying that the chain-node
-refactor eliminated only shows up on long sequences (NER chunks run 200+
-tokens). The `cacheSize` param (0/64) toggles the contexts cache. To produce
-the pre-refactor baseline, swap the pre-refactor `opennlp-ml-commons` jar
-onto the classpath ahead of the freshly built classes — the benchmark only
-uses the unchanged public API — and rerun.
+refactor (OPENNLP-1903) eliminated only shows up on long sequences (NER
+chunks run 200+ tokens). The `cacheSize` param (0/64) toggles the contexts
+cache. To produce the pre-refactor baseline, place an `opennlp-ml-commons`
+jar built before OPENNLP-1903 on the classpath ahead of the freshly built
+classes and rerun; the benchmark only uses public API that predates the
+refactor.
Results (Linux, JDK 25, 24 pinned cores of a 32-core box, 2 forks x 10
iterations; ops/s = decoded sequences per second):
@@ -153,9 +154,9 @@ iterations; ops/s = decoded sequences per second):
| post-refactor | 64 | 64 | 34,818 ± 232 | 347,266 ± 942 | 10.0x |
| post-refactor | 256 | 64 | 4,308 ± 27 | 50,203 ± 230 | 11.7x |
-Two readings. First, the refactor's win grows with sequence length —
+Two readings. First, the refactor's win grows with sequence length:
~2x single-thread at every length, and at 24 threads 2.3x (len 8),
-4.4x (len 64), and 9.1x (len 256) — the signature of an O(n^2) copy
+4.4x (len 64), and 9.1x (len 256), the signature of an O(n^2) copy
cost being removed. Second, the pre-refactor scaling collapses as
sequences lengthen (6.2x down to 2.5x on 24 threads: memory-write
saturation from per-candidate list copying), while post-refactor
@@ -166,7 +167,8 @@ the sequence-mechanics cost the refactor targets; with a
real maxent
model the eval compute is shared by both versions and the relative
single-thread win is smaller (~1.3x on ARM, roughly neutral on x86),
while the concurrent scaling gap is preserved (measured 5.8x -> 13.3x
-at saturation on 24 pinned cores with a real NER model).
+at saturation on 24 pinned cores with the SourceForge-era 1.5 English
+`en-ner-person.bin` model).
## JUnit Correctness Test
diff --git
a/opennlp-core/opennlp-runtime/src/jmh/java/opennlp/tools/ml/BeamSearchBenchmark.java
b/opennlp-core/opennlp-runtime/src/jmh/java/opennlp/tools/ml/BeamSearchBenchmark.java
index 85d77fe8a..18e2f8212 100644
---
a/opennlp-core/opennlp-runtime/src/jmh/java/opennlp/tools/ml/BeamSearchBenchmark.java
+++
b/opennlp-core/opennlp-runtime/src/jmh/java/opennlp/tools/ml/BeamSearchBenchmark.java
@@ -41,7 +41,6 @@ import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
import org.openjdk.jmh.runner.options.TimeValue;
-import opennlp.tools.ml.model.MaxentModel;
import opennlp.tools.util.BeamSearchContextGenerator;
import opennlp.tools.util.SequenceValidator;
@@ -49,15 +48,15 @@ import opennlp.tools.util.SequenceValidator;
* JMH benchmark for {@link BeamSearch} on long input sequences.
* <p>
* One op = one {@code bestSequence} call on a synthetic token sequence of
- * {@code sequenceLength} tokens. Long sequences are what expose the O(n^2)
- * per-candidate outcome-list copying that the chain-node refactor eliminated;
- * the 5-10 token sentences used by the ME benchmarks would show nothing.
- * Only the pre-refactor public API is used
+ * {@code sequenceLength} tokens. Long sequences are what expose the quadratic
+ * per-candidate outcome-list copying removed with OPENNLP-1903; sentences of
+ * 5-10 tokens, as used by the ME benchmarks, show no measurable difference.
+ * Only public API that predates OPENNLP-1903 is used
* ({@code BeamSearch(int, MaxentModel, int)} and
* {@code bestSequence(T[], Object[], BeamSearchContextGenerator,
SequenceValidator)}),
- * so the same compiled class exercises both implementations: to produce the
- * baseline, swap the pre-refactor {@code opennlp-ml-commons} jar onto the
- * classpath ahead of the freshly built classes and rerun.
+ * so the same compiled class exercises both implementations: to produce a
+ * baseline, place an {@code opennlp-ml-commons} jar built before OPENNLP-1903
+ * on the classpath ahead of the freshly built classes and rerun.
*/
@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
@@ -69,7 +68,9 @@ public class BeamSearchBenchmark {
private static final int BEAM_SIZE = 3;
private static final int NUM_INPUTS = 64;
private static final int VOCAB_SIZE = 17;
- private static final long INPUT_SEED = 0x5eedL;
+ /** Seed for both the input generator and the {@link SeededMaxentModel}. */
+ private static final long SEED = 0x5eedL;
+ private static final String[] MODEL_OUTCOMES = {"start", "cont", "other"};
private static final SequenceValidator<String> ACCEPT_ALL =
(i, input, outcomes, outcome) -> true;
@@ -90,10 +91,11 @@ public class BeamSearchBenchmark {
@Setup(Level.Trial)
public void create() {
- beamSearch = new BeamSearch(BEAM_SIZE, new SeededModel(), cacheSize);
+ beamSearch = new BeamSearch(BEAM_SIZE,
+ new SeededMaxentModel(MODEL_OUTCOMES, SEED), cacheSize);
contextGenerator = new TokenContextGenerator();
inputs = new String[NUM_INPUTS][];
- Random rnd = new Random(INPUT_SEED);
+ Random rnd = new Random(SEED);
for (int n = 0; n < NUM_INPUTS; n++) {
String[] input = new String[sequenceLength];
for (int i = 0; i < sequenceLength; i++) {
@@ -110,87 +112,6 @@ public class BeamSearchBenchmark {
}
}
- /**
- * A deterministic pseudo-random {@link MaxentModel}: the probability for an
- * outcome is derived from a hash of the joined context strings with
- * splitmix64-style mixing, so repeated evals of the same context return
- * identical values in (0.01, 0.99]. Values are intentionally not normalized.
- * The buffer contract is honored: {@code eval(context, probs)} writes into
- * the passed array and returns that same array.
- */
- static final class SeededModel implements MaxentModel {
-
- private final String[] outcomes = {"start", "cont", "other"};
-
- private double prob(String[] context, int outcomeIndex) {
- long h = 0x5eedL;
- for (String c : context) {
- h = mix(h, c.hashCode());
- }
- h = mix(h, outcomeIndex);
- // splitmix64 finalizer for avalanche
- h ^= h >>> 30;
- h *= 0xBF58476D1CE4E5B9L;
- h ^= h >>> 27;
- h *= 0x94D049BB133111EBL;
- h ^= h >>> 31;
- double u = (h >>> 11) * (1.0 / (1L << 53)); // [0, 1)
- return 0.01 + 0.98 * u; // (0.01, 0.99]
- }
-
- private static long mix(long h, long v) {
- return (h ^ (v + 0x9E3779B97F4A7C15L)) * 0x100000001B3L;
- }
-
- @Override
- public double[] eval(String[] context) {
- return eval(context, new double[outcomes.length]);
- }
-
- @Override
- public double[] eval(String[] context, double[] probs) {
- for (int i = 0; i < outcomes.length; i++) {
- probs[i] = prob(context, i);
- }
- return probs; // buffer contract: write into the passed array AND return
it
- }
-
- @Override
- public double[] eval(String[] context, float[] values) {
- return eval(context);
- }
-
- @Override
- public String getOutcome(int i) {
- return outcomes[i];
- }
-
- @Override
- public int getNumOutcomes() {
- return outcomes.length;
- }
-
- @Override
- public String getAllOutcomes(double[] outcomes) {
- return null;
- }
-
- @Override
- public String getBestOutcome(double[] outcomes) {
- return null;
- }
-
- @Override
- public int getIndex(String outcome) {
- for (int i = 0; i < outcomes.length; i++) {
- if (outcomes[i].equals(outcome)) {
- return i;
- }
- }
- return -1;
- }
- }
-
/**
* Derives contexts from the current token and the previous outcome, interned
* so identical context content maps to the same {@code String[]} instance
diff --git
a/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/ml/BeamSearchEquivalenceTest.java
b/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/ml/BeamSearchEquivalenceTest.java
index 448f868f4..45efbc741 100644
---
a/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/ml/BeamSearchEquivalenceTest.java
+++
b/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/ml/BeamSearchEquivalenceTest.java
@@ -28,9 +28,14 @@ import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.atomic.AtomicInteger;
+import java.util.stream.IntStream;
+import java.util.stream.Stream;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
import opennlp.tools.ml.model.MaxentModel;
import opennlp.tools.util.BeamSearchContextGenerator;
@@ -39,123 +44,53 @@ import opennlp.tools.util.Sequence;
import opennlp.tools.util.SequenceValidator;
/**
- * Equivalence tests for the {@code BeamSearch.bestSequences} refactor that
replaced
- * per-candidate {@link Sequence} copies with internal chain nodes ({@code
SearchNode}).
+ * Equivalence tests for the {@code BeamSearch.bestSequences} chain-node
implementation
+ * introduced with OPENNLP-1903.
* <p>
* Every test runs the current {@link BeamSearch} side by side with
- * {@link #referenceBestSequences}, a faithful port of the pre-refactor
implementation
- * (as of {@code HEAD~1}), and demands identical output: same number of
sequences,
- * identical outcome lists (order-sensitive), and bit-identical scores and
- * per-position probabilities.
+ * {@link #referenceBestSequences}, a faithful port of the per-candidate
+ * {@link Sequence}-copying implementation that OPENNLP-1903 replaced, and
demands
+ * identical output: same number of sequences, identical outcome lists
+ * (order-sensitive), and bit-identical scores and per-position probabilities.
*/
public class BeamSearchEquivalenceTest {
/** Mirror of the private {@code BeamSearch.ZERO_LOG} default threshold. */
private static final double ZERO_LOG = -100000;
- private static final int NUM_OUTCOMES = 4;
+ private static final String[] OUTCOMES = {"o0", "o1", "o2", "o3"};
private static final long MODEL_SEED = 0x5eedL;
- private static final int[] BEAM_SIZES = {1, 2, 3, 5, 10}; // 10 >
NUM_OUTCOMES on purpose
+ private static final int[] BEAM_SIZES = {1, 2, 3, 5, 10}; // 10 >
OUTCOMES.length on purpose
private static final int[] INPUT_LENGTHS = {0, 1, 2, 7, 33, 128};
private static final int[] CACHE_SIZES = {0, 64};
private static final SequenceValidator<String> ACCEPT_ALL =
(i, input, outcomes, outcome) -> true;
- //
---------------------------------------------------------------------------
- // Seeded pseudo-random model
- //
---------------------------------------------------------------------------
-
- /**
- * A {@link MaxentModel} whose probabilities are a deterministic
pseudo-random
- * function of the joined context strings and the outcome index. Repeated
evals of
- * the same context therefore return identical values. Values lie in (0, 1]
and are
- * intentionally not normalized. The {@code eval(context, probs)} buffer
contract is
- * honored: values are written into the passed array and that same array is
returned.
- */
- static final class SeededModel implements MaxentModel {
-
- private final String[] outcomes;
- private final long seed;
-
- SeededModel(int numOutcomes, long seed) {
- this.outcomes = new String[numOutcomes];
- for (int i = 0; i < numOutcomes; i++) {
- this.outcomes[i] = "o" + i;
- }
- this.seed = seed;
- }
-
- private double prob(String[] context, int outcomeIndex) {
- long h = seed;
- for (String c : context) {
- h = mix(h, c.hashCode());
- }
- h = mix(h, outcomeIndex);
- // splitmix64 finalizer for avalanche
- h ^= h >>> 30;
- h *= 0xBF58476D1CE4E5B9L;
- h ^= h >>> 27;
- h *= 0x94D049BB133111EBL;
- h ^= h >>> 31;
- double u = (h >>> 11) * (1.0 / (1L << 53)); // [0, 1)
- return 0.01 + 0.98 * u; // (0.01, 0.99]
- }
-
- private static long mix(long h, long v) {
- return (h ^ (v + 0x9E3779B97F4A7C15L)) * 0x100000001B3L;
- }
-
- @Override
- public double[] eval(String[] context) {
- return eval(context, new double[outcomes.length]);
- }
-
- @Override
- public double[] eval(String[] context, double[] probs) {
- for (int i = 0; i < outcomes.length; i++) {
- probs[i] = prob(context, i);
- }
- return probs; // buffer contract: write into the passed array AND return
it
- }
-
- @Override
- public double[] eval(String[] context, float[] values) {
- return eval(context);
- }
-
- @Override
- public String getOutcome(int i) {
- return outcomes[i];
- }
-
+ /** A {@link SequenceValidator} paired with a stable name for test display.
*/
+ record NamedValidator(String name, SequenceValidator<String> validator) {
@Override
- public int getNumOutcomes() {
- return outcomes.length;
- }
-
- @Override
- public String getAllOutcomes(double[] outcomes) {
- return null;
- }
-
- @Override
- public String getBestOutcome(double[] outcomes) {
- return null;
- }
-
- @Override
- public int getIndex(String outcome) {
- for (int i = 0; i < outcomes.length; i++) {
- if (outcomes[i].equals(outcome)) {
- return i;
- }
- }
- return -1;
+ public String toString() {
+ return name;
}
}
+ private static final List<NamedValidator> VALIDATORS = List.of(
+ new NamedValidator("rejectOneOutcome",
+ (i, input, outcomes, outcome) -> !"o2".equals(outcome)),
+ // Rejects every outcome at position 2: at that position the threshold
loop adds
+ // nothing, so the next.isEmpty() fallback runs (and also rejects
everything,
+ // killing the search for inputs longer than 2).
+ new NamedValidator("rejectAllAtPosition2",
+ (i, input, outcomes, outcome) -> i != 2),
+ // Rejects everything except "o3" at position 2: the fallback actually
populates
+ // next with the sub-threshold "o3" candidate whenever "o3" fell below
the min.
+ new NamedValidator("onlyO3AtPosition2",
+ (i, input, outcomes, outcome) -> i != 2 || "o3".equals(outcome)),
+ new NamedValidator("rejectEverything",
+ (i, input, outcomes, outcome) -> false));
+
//
---------------------------------------------------------------------------
// Context generator
//
---------------------------------------------------------------------------
@@ -184,23 +119,27 @@ public class BeamSearchEquivalenceTest {
return existing != null ? existing : ctx;
}
+ /**
+ * @return The number of {@link #getContext} invocations so far.
+ */
int callCount() {
return callCount.get();
}
}
//
---------------------------------------------------------------------------
- // Reference implementation: faithful port of the pre-refactor bestSequences
- // (git show HEAD~1:.../opennlp/tools/ml/BeamSearch.java)
+ // Reference implementation: faithful port of the bestSequences
implementation
+ // prior to OPENNLP-1903
//
---------------------------------------------------------------------------
/**
- * Port of the OLD {@code BeamSearch.bestSequences} control flow:
PriorityQueue over
- * {@link Sequence}, per-candidate {@code new Sequence(top, out, scores[p])}
copies,
- * tempScores sort/min, the {@code next.isEmpty()} advance-all-valid
fallback, the
- * queue swap, and the winner removal order. The cache path (a
- * {@code Cache<String[], double[]>} exactly like the old per-thread one) is
used
- * when {@code cacheSize > 0}; otherwise the uncached eval path is taken.
+ * Port of the {@code BeamSearch.bestSequences} control flow prior to
OPENNLP-1903:
+ * PriorityQueue over {@link Sequence}, per-candidate
+ * {@code new Sequence(top, out, scores[p])} copies, tempScores sort/min, the
+ * {@code next.isEmpty()} advance-all-valid fallback, the queue swap, and
the winner
+ * removal order. The cache path (a {@code Cache<String[], double[]>}
exactly like the
+ * per-thread one in {@link BeamSearch}) is used when {@code cacheSize > 0};
otherwise
+ * the uncached eval path is taken.
*/
static <T> Sequence[] referenceBestSequences(
final int numSequences, final T[] sequence, final Object[]
additionalContext,
@@ -208,7 +147,7 @@ public class BeamSearchEquivalenceTest {
final SequenceValidator<T> validator, final MaxentModel model,
final int beamSize, final int cacheSize) {
- // Local equivalents of the old per-thread CacheState.
+ // Local equivalents of the per-thread CacheState in BeamSearch.
final double[] probs = new double[model.getNumOutcomes()];
final double[] tempScores = new double[model.getNumOutcomes()];
final Cache<String[], double[]> cache = cacheSize > 0 ? new
Cache<>(cacheSize) : null;
@@ -303,6 +242,16 @@ public class BeamSearchEquivalenceTest {
// Helpers
//
---------------------------------------------------------------------------
+ /**
+ * @return A new model over {@link #OUTCOMES} seeded with {@link
#MODEL_SEED}.
+ */
+ private static MaxentModel model() {
+ return new SeededMaxentModel(OUTCOMES, MODEL_SEED);
+ }
+
+ /**
+ * @return A seeded pseudo-random token sequence of {@code length} tokens.
+ */
private static String[] randomInput(int length, long seed) {
Random rnd = new Random(seed);
String[] input = new String[length];
@@ -349,72 +298,120 @@ public class BeamSearchEquivalenceTest {
}
//
---------------------------------------------------------------------------
- // 1. Equivalence matrix: beam sizes x input lengths x cache sizes,
- // default (ZERO_LOG) threshold via the two-arg overload, accept-all
validator
+ // Parameter sources
//
---------------------------------------------------------------------------
- @Test
- void equivalenceAcrossBeamSizesLengthsAndCaches() {
- MaxentModel model = new SeededModel(NUM_OUTCOMES, MODEL_SEED);
+ /**
+ * @return The cartesian product of {@link #BEAM_SIZES}, {@link
#INPUT_LENGTHS}
+ * and {@link #CACHE_SIZES}.
+ */
+ static Stream<Arguments> beamLengthCacheMatrix() {
+ Stream.Builder<Arguments> cases = Stream.builder();
for (int beam : BEAM_SIZES) {
for (int length : INPUT_LENGTHS) {
- String[] input = randomInput(length, 1000L + length);
for (int cache : CACHE_SIZES) {
- String desc = caseDesc("matrix", beam, length, cache);
- SeededContextGenerator cg = new SeededContextGenerator();
-
- Sequence[] expected = referenceBestSequences(1, input, null, cg,
ACCEPT_ALL,
- model, beam, cache);
- Sequence[] actual = new BeamSearch(beam, model, cache)
- .bestSequences(1, input, null, cg, ACCEPT_ALL);
-
- assertSequencesEqual(expected, actual, desc);
- if (length == 0) {
- Assertions.assertEquals(0, cg.callCount(),
- desc + ": context generator must not be called for empty
input");
+ cases.add(Arguments.of(beam, length, cache));
+ }
+ }
+ }
+ return cases.build();
+ }
+
+ /**
+ * @return The cartesian product of {@link #VALIDATORS}, {@link #BEAM_SIZES},
+ * {@link #INPUT_LENGTHS} and {@link #CACHE_SIZES}.
+ */
+ static Stream<Arguments> validatorBeamLengthCacheMatrix() {
+ Stream.Builder<Arguments> cases = Stream.builder();
+ for (NamedValidator nv : VALIDATORS) {
+ for (int beam : BEAM_SIZES) {
+ for (int length : INPUT_LENGTHS) {
+ for (int cache : CACHE_SIZES) {
+ cases.add(Arguments.of(nv, beam, length, cache));
}
}
}
}
+ return cases.build();
+ }
+
+ /**
+ * @return The cartesian product of {@link #INPUT_LENGTHS} and {@link
#CACHE_SIZES}.
+ */
+ static Stream<Arguments> lengthCacheMatrix() {
+ Stream.Builder<Arguments> cases = Stream.builder();
+ for (int length : INPUT_LENGTHS) {
+ for (int cache : CACHE_SIZES) {
+ cases.add(Arguments.of(length, cache));
+ }
+ }
+ return cases.build();
+ }
+
+ /**
+ * @return All values of {@link #CACHE_SIZES}.
+ */
+ static IntStream cacheSizes() {
+ return IntStream.of(CACHE_SIZES);
}
//
---------------------------------------------------------------------------
- // 2. Equivalence with a tight minSequenceScore that actually filters
candidates
+ // 1. Equivalence matrix: beam sizes x input lengths x cache sizes,
+ // default (ZERO_LOG) threshold via the two-arg overload, accept-all
validator
//
---------------------------------------------------------------------------
- @Test
- void equivalenceWithTightMinSequenceScore() {
- MaxentModel model = new SeededModel(NUM_OUTCOMES, MODEL_SEED);
- for (int beam : BEAM_SIZES) {
- for (int length : INPUT_LENGTHS) {
- String[] input = randomInput(length, 2000L + length);
- for (int cache : CACHE_SIZES) {
- String desc = caseDesc("threshold", beam, length, cache);
-
- // Derive a threshold that bites: run uncapped, then cut between the
best
- // and worst candidate scores (or just above the best when only one
exists).
- Sequence[] uncapped = referenceBestSequences(beam, input, null,
- new SeededContextGenerator(), ACCEPT_ALL, model, beam, cache);
- final double threshold;
- if (uncapped.length == 0) {
- threshold = 0;
- } else {
- double best = uncapped[0].getScore();
- double worst = uncapped[uncapped.length - 1].getScore();
- threshold = (uncapped.length > 1 && worst < best)
- ? (best + worst) / 2.0 : best + 0.5;
- }
+ @ParameterizedTest(name = "beam={0}, len={1}, cache={2}")
+ @MethodSource("beamLengthCacheMatrix")
+ void equivalenceAcrossBeamSizesLengthsAndCaches(int beam, int length, int
cache) {
+ MaxentModel model = model();
+ String[] input = randomInput(length, 1000L + length);
+ String desc = caseDesc("matrix", beam, length, cache);
+ SeededContextGenerator cg = new SeededContextGenerator();
- Sequence[] expected = referenceBestSequences(1, input, null,
threshold,
- new SeededContextGenerator(), ACCEPT_ALL, model, beam, cache);
- Sequence[] actual = new BeamSearch(beam, model, cache)
- .bestSequences(1, input, null, threshold, new
SeededContextGenerator(),
- ACCEPT_ALL);
+ Sequence[] expected = referenceBestSequences(1, input, null, cg,
ACCEPT_ALL,
+ model, beam, cache);
+ Sequence[] actual = new BeamSearch(beam, model, cache)
+ .bestSequences(1, input, null, cg, ACCEPT_ALL);
- assertSequencesEqual(expected, actual, desc + ", threshold=" +
threshold);
- }
- }
+ assertSequencesEqual(expected, actual, desc);
+ if (length == 0) {
+ Assertions.assertEquals(0, cg.callCount(),
+ desc + ": context generator must not be called for empty input");
+ }
+ }
+
+ //
---------------------------------------------------------------------------
+ // 2. Equivalence with a tight minSequenceScore that actually filters
candidates
+ //
---------------------------------------------------------------------------
+
+ @ParameterizedTest(name = "beam={0}, len={1}, cache={2}")
+ @MethodSource("beamLengthCacheMatrix")
+ void equivalenceWithTightMinSequenceScore(int beam, int length, int cache) {
+ MaxentModel model = model();
+ String[] input = randomInput(length, 2000L + length);
+ String desc = caseDesc("threshold", beam, length, cache);
+
+ // Derive a threshold that bites: run uncapped, then cut between the best
+ // and worst candidate scores (or just above the best when only one
exists).
+ Sequence[] uncapped = referenceBestSequences(beam, input, null,
+ new SeededContextGenerator(), ACCEPT_ALL, model, beam, cache);
+ final double threshold;
+ if (uncapped.length == 0) {
+ threshold = 0;
+ } else {
+ double best = uncapped[0].getScore();
+ double worst = uncapped[uncapped.length - 1].getScore();
+ threshold = (uncapped.length > 1 && worst < best)
+ ? (best + worst) / 2.0 : best + 0.5;
}
+
+ Sequence[] expected = referenceBestSequences(1, input, null, threshold,
+ new SeededContextGenerator(), ACCEPT_ALL, model, beam, cache);
+ Sequence[] actual = new BeamSearch(beam, model, cache)
+ .bestSequences(1, input, null, threshold, new SeededContextGenerator(),
+ ACCEPT_ALL);
+
+ assertSequencesEqual(expected, actual, desc + ", threshold=" + threshold);
}
//
---------------------------------------------------------------------------
@@ -422,54 +419,26 @@ public class BeamSearchEquivalenceTest {
// advance-all-valid fallback and the reject-everything empty-result path
//
---------------------------------------------------------------------------
- @Test
- void equivalenceWithRestrictiveValidators() {
- MaxentModel model = new SeededModel(NUM_OUTCOMES, MODEL_SEED);
-
- SequenceValidator<String> rejectOneOutcome =
- (i, input, outcomes, outcome) -> !"o2".equals(outcome);
- // Rejects every outcome at position 2: at that position the threshold
loop adds
- // nothing, so the next.isEmpty() fallback runs (and also rejects
everything,
- // killing the search for inputs longer than 2).
- SequenceValidator<String> rejectAllAtPosition2 =
- (i, input, outcomes, outcome) -> i != 2;
- // Rejects everything except "o3" at position 2: the fallback actually
populates
- // next with the sub-threshold "o3" candidate whenever "o3" fell below the
min.
- SequenceValidator<String> onlyO3AtPosition2 =
- (i, input, outcomes, outcome) -> i != 2 || "o3".equals(outcome);
- SequenceValidator<String> rejectEverything =
- (i, input, outcomes, outcome) -> false;
-
- record NamedValidator(String name, SequenceValidator<String> validator) {}
- List<NamedValidator> validators = List.of(
- new NamedValidator("rejectOneOutcome", rejectOneOutcome),
- new NamedValidator("rejectAllAtPosition2", rejectAllAtPosition2),
- new NamedValidator("onlyO3AtPosition2", onlyO3AtPosition2),
- new NamedValidator("rejectEverything", rejectEverything));
-
- for (NamedValidator nv : validators) {
- for (int beam : BEAM_SIZES) {
- for (int length : INPUT_LENGTHS) {
- String[] input = randomInput(length, 3000L + length);
- for (int cache : CACHE_SIZES) {
- String desc = caseDesc("validator-" + nv.name(), beam, length,
cache);
-
- Sequence[] expected = referenceBestSequences(1, input, null,
- new SeededContextGenerator(), nv.validator(), model, beam,
cache);
- Sequence[] actual = new BeamSearch(beam, model, cache)
- .bestSequences(1, input, null, new SeededContextGenerator(),
- nv.validator());
-
- assertSequencesEqual(expected, actual, desc);
- if ("rejectEverything".equals(nv.name()) && length > 0) {
- Assertions.assertEquals(0, actual.length,
- desc + ": reject-everything must yield an empty (non-null)
array");
- Assertions.assertEquals(0, expected.length,
- desc + ": reference reject-everything must also be empty");
- }
- }
- }
- }
+ @ParameterizedTest(name = "{0}, beam={1}, len={2}, cache={3}")
+ @MethodSource("validatorBeamLengthCacheMatrix")
+ void equivalenceWithRestrictiveValidators(NamedValidator nv, int beam, int
length,
+ int cache) {
+ MaxentModel model = model();
+ String[] input = randomInput(length, 3000L + length);
+ String desc = caseDesc("validator-" + nv.name(), beam, length, cache);
+
+ Sequence[] expected = referenceBestSequences(1, input, null,
+ new SeededContextGenerator(), nv.validator(), model, beam, cache);
+ Sequence[] actual = new BeamSearch(beam, model, cache)
+ .bestSequences(1, input, null, new SeededContextGenerator(),
+ nv.validator());
+
+ assertSequencesEqual(expected, actual, desc);
+ if ("rejectEverything".equals(nv.name()) && length > 0) {
+ Assertions.assertEquals(0, actual.length,
+ desc + ": reject-everything must yield an empty (non-null) array");
+ Assertions.assertEquals(0, expected.length,
+ desc + ": reference reject-everything must also be empty");
}
}
@@ -477,34 +446,31 @@ public class BeamSearchEquivalenceTest {
// 4. numSequences > 1: winner order and scores match the reference exactly
//
---------------------------------------------------------------------------
- @Test
- void multiWinnerOrderingMatchesReference() {
- MaxentModel model = new SeededModel(NUM_OUTCOMES, MODEL_SEED);
+ @ParameterizedTest(name = "len={0}, cache={1}")
+ @MethodSource("lengthCacheMatrix")
+ void multiWinnerOrderingMatchesReference(int length, int cache) {
+ MaxentModel model = model();
int beam = 5;
int numSequences = 3;
Object[] additionalContext = {"ac-ctx"};
- for (int length : INPUT_LENGTHS) {
- String[] input = randomInput(length, 4000L + length);
- for (int cache : CACHE_SIZES) {
- String desc = caseDesc("multiWinner[k=3]", beam, length, cache);
-
- Sequence[] expected = referenceBestSequences(numSequences, input,
- additionalContext, new SeededContextGenerator(), ACCEPT_ALL,
- model, beam, cache);
- Sequence[] actual = new BeamSearch(beam, model, cache)
- .bestSequences(numSequences, input, additionalContext,
- new SeededContextGenerator(), ACCEPT_ALL);
-
- assertSequencesEqual(expected, actual, desc);
- if (length > 0) {
- Assertions.assertEquals(numSequences, actual.length,
- desc + ": expected a full k-best list");
- // Winners must come out in non-increasing score order.
- for (int s = 1; s < actual.length; s++) {
- Assertions.assertTrue(actual[s - 1].getScore() >=
actual[s].getScore(),
- desc + ": winner order not non-increasing at index " + s);
- }
- }
+ String[] input = randomInput(length, 4000L + length);
+ String desc = caseDesc("multiWinner[k=3]", beam, length, cache);
+
+ Sequence[] expected = referenceBestSequences(numSequences, input,
+ additionalContext, new SeededContextGenerator(), ACCEPT_ALL,
+ model, beam, cache);
+ Sequence[] actual = new BeamSearch(beam, model, cache)
+ .bestSequences(numSequences, input, additionalContext,
+ new SeededContextGenerator(), ACCEPT_ALL);
+
+ assertSequencesEqual(expected, actual, desc);
+ if (length > 0) {
+ Assertions.assertEquals(numSequences, actual.length,
+ desc + ": expected a full k-best list");
+ // Winners must come out in non-increasing score order.
+ for (int s = 1; s < actual.length; s++) {
+ Assertions.assertTrue(actual[s - 1].getScore() >= actual[s].getScore(),
+ desc + ": winner order not non-increasing at index " + s);
}
}
}
@@ -521,7 +487,7 @@ public class BeamSearchEquivalenceTest {
final int beam = 3;
final int cache = 64;
- MaxentModel model = new SeededModel(NUM_OUTCOMES, MODEL_SEED);
+ MaxentModel model = model();
BeamSearch shared = new BeamSearch(beam, model, cache);
String[][] inputs = new String[numInputs][];
@@ -603,45 +569,44 @@ public class BeamSearchEquivalenceTest {
// winning Sequence are consistent with the model's eval outputs
//
---------------------------------------------------------------------------
- @Test
- void winnerMaterializationMatchesModelOutputs() {
- MaxentModel model = new SeededModel(NUM_OUTCOMES, MODEL_SEED);
+ @ParameterizedTest(name = "cache={0}")
+ @MethodSource("cacheSizes")
+ void winnerMaterializationMatchesModelOutputs(int cache) {
+ MaxentModel model = model();
String[] input = randomInput(7, 6000L);
int beam = 3;
- for (int cache : CACHE_SIZES) {
- String desc = "materialization[cache=" + cache + "]";
- BeamSearch bs = new BeamSearch(beam, model, cache);
- Sequence winner = bs.bestSequence(input, null, new
SeededContextGenerator(),
- ACCEPT_ALL);
- Assertions.assertNotNull(winner, desc);
- Assertions.assertEquals(input.length, winner.getSize(), desc + ": size");
-
- // The winner must equal the reference winner.
- Sequence refWinner = referenceBestSequences(1, input, null,
- new SeededContextGenerator(), ACCEPT_ALL, model, beam, cache)[0];
- Assertions.assertEquals(refWinner.getOutcomes(), winner.getOutcomes(),
- desc + ": outcomes vs reference");
-
- // Walk the winning path and recompute the expected probs/score
independently.
- List<String> outcomes = winner.getOutcomes();
- double[] probs = winner.getProbs();
- double expectedScore = 0d;
- SeededContextGenerator cg = new SeededContextGenerator();
- for (int i = 0; i < outcomes.size(); i++) {
- String[] prefix = outcomes.subList(0, i).toArray(new String[0]);
- String[] contexts = cg.getContext(i, input, prefix, new Object[0]);
- double[] eval = model.eval(contexts);
- int outcomeIndex = model.getIndex(outcomes.get(i));
- Assertions.assertTrue(outcomeIndex >= 0, desc + ": outcome known to
model");
- double expectedProb = eval[outcomeIndex];
-
- assertBitIdentical(expectedProb, probs[i], desc + ": getProbs()[" + i
+ "]");
- assertBitIdentical(expectedProb, winner.getProb(i),
- desc + ": getProb(" + i + ")");
- expectedScore += StrictMath.log(expectedProb);
- }
- assertBitIdentical(expectedScore, winner.getScore(), desc + ": score");
+ String desc = "materialization[cache=" + cache + "]";
+ BeamSearch bs = new BeamSearch(beam, model, cache);
+ Sequence winner = bs.bestSequence(input, null, new
SeededContextGenerator(),
+ ACCEPT_ALL);
+ Assertions.assertNotNull(winner, desc);
+ Assertions.assertEquals(input.length, winner.getSize(), desc + ": size");
+
+ // The winner must equal the reference winner.
+ Sequence refWinner = referenceBestSequences(1, input, null,
+ new SeededContextGenerator(), ACCEPT_ALL, model, beam, cache)[0];
+ Assertions.assertEquals(refWinner.getOutcomes(), winner.getOutcomes(),
+ desc + ": outcomes vs reference");
+
+ // Walk the winning path and recompute the expected probs/score
independently.
+ List<String> outcomes = winner.getOutcomes();
+ double[] probs = winner.getProbs();
+ double expectedScore = 0d;
+ SeededContextGenerator cg = new SeededContextGenerator();
+ for (int i = 0; i < outcomes.size(); i++) {
+ String[] prefix = outcomes.subList(0, i).toArray(new String[0]);
+ String[] contexts = cg.getContext(i, input, prefix, new Object[0]);
+ double[] eval = model.eval(contexts);
+ int outcomeIndex = model.getIndex(outcomes.get(i));
+ Assertions.assertTrue(outcomeIndex >= 0, desc + ": outcome known to
model");
+ double expectedProb = eval[outcomeIndex];
+
+ assertBitIdentical(expectedProb, probs[i], desc + ": getProbs()[" + i +
"]");
+ assertBitIdentical(expectedProb, winner.getProb(i),
+ desc + ": getProb(" + i + ")");
+ expectedScore += StrictMath.log(expectedProb);
}
+ assertBitIdentical(expectedScore, winner.getScore(), desc + ": score");
}
}
diff --git
a/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/ml/SeededMaxentModel.java
b/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/ml/SeededMaxentModel.java
new file mode 100644
index 000000000..1d2ddb6b2
--- /dev/null
+++
b/opennlp-core/opennlp-runtime/src/test/java/opennlp/tools/ml/SeededMaxentModel.java
@@ -0,0 +1,120 @@
+/*
+ * 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 opennlp.tools.ml;
+
+import opennlp.tools.ml.model.MaxentModel;
+
+/**
+ * A deterministic pseudo-random {@link MaxentModel} test fixture. The
probability of an
+ * outcome is derived from a hash of the joined context strings, the outcome
index and a
+ * fixed seed with splitmix64-style mixing, so repeated evals of the same
context return
+ * identical values in (0.01, 0.99]. Values are intentionally not normalized.
The
+ * {@code eval(context, probs)} buffer contract is honored: values are written
into the
+ * passed array and that same array is returned. Stateless and therefore
thread-safe.
+ */
+class SeededMaxentModel implements MaxentModel {
+
+ private final String[] outcomes;
+ private final long seed;
+
+ /**
+ * Initializes a {@link SeededMaxentModel} instance.
+ *
+ * @param outcomes The outcome labels; the outcome index is the array index.
+ * @param seed The seed all probabilities are derived from.
+ */
+ SeededMaxentModel(String[] outcomes, long seed) {
+ this.outcomes = outcomes;
+ this.seed = seed;
+ }
+
+ /**
+ * @return A pseudo-random probability in (0.01, 0.99], a pure function
+ * of {@code context}, {@code outcomeIndex} and the seed.
+ */
+ private double prob(String[] context, int outcomeIndex) {
+ long h = seed;
+ for (String c : context) {
+ h = mix(h, c.hashCode());
+ }
+ h = mix(h, outcomeIndex);
+ // splitmix64 finalizer for avalanche
+ h ^= h >>> 30;
+ h *= 0xBF58476D1CE4E5B9L;
+ h ^= h >>> 27;
+ h *= 0x94D049BB133111EBL;
+ h ^= h >>> 31;
+ double u = (h >>> 11) * (1.0 / (1L << 53)); // [0, 1)
+ return 0.01 + 0.98 * u; // (0.01, 0.99]
+ }
+
+ /**
+ * @return {@code h} combined with {@code v} FNV-style.
+ */
+ private static long mix(long h, long v) {
+ return (h ^ (v + 0x9E3779B97F4A7C15L)) * 0x100000001B3L;
+ }
+
+ @Override
+ public double[] eval(String[] context) {
+ return eval(context, new double[outcomes.length]);
+ }
+
+ @Override
+ public double[] eval(String[] context, double[] probs) {
+ for (int i = 0; i < outcomes.length; i++) {
+ probs[i] = prob(context, i);
+ }
+ return probs; // buffer contract: write into the passed array AND return it
+ }
+
+ @Override
+ public double[] eval(String[] context, float[] values) {
+ return eval(context);
+ }
+
+ @Override
+ public String getOutcome(int i) {
+ return outcomes[i];
+ }
+
+ @Override
+ public int getNumOutcomes() {
+ return outcomes.length;
+ }
+
+ @Override
+ public String getAllOutcomes(double[] outcomes) {
+ return null;
+ }
+
+ @Override
+ public String getBestOutcome(double[] outcomes) {
+ return null;
+ }
+
+ @Override
+ public int getIndex(String outcome) {
+ for (int i = 0; i < outcomes.length; i++) {
+ if (outcomes[i].equals(outcome)) {
+ return i;
+ }
+ }
+ return -1;
+ }
+}
