You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@opennlp.apache.org by "krickert (via GitHub)" <gi...@apache.org> on 2026/09/01 02:59:10 UTC
[PR] [2.x] OPENNLP-1903: Replace per-candidate Sequence copies with chain nodes in BeamSearch (opennlp)
krickert opened a new pull request, #1262:
URL: https://github.com/apache/opennlp/pull/1262
Backport of #1205 (OPENNLP-1903) to opennlp-2.x.
## Problem
`BeamSearch.bestSequences` performs O(beamSize × numOutcomes × n²) element copies per document (object count is O(beam × numOutcomes × n)):
1. Every candidate expansion (`new Sequence(top, out, p)`) copies the parent's entire `outcomes` and `probs` lists (`Sequence.java`).
2. Every pop copies them again via `Sequence.getOutcomes()` (`List.copyOf`, added in OPENNLP-1340) followed by `toArray()`.
For a 215-token chunk with beam 3 and 3 outcomes that is ~550k element copies per document per model. This churn is invisible single-threaded but saturates memory write bandwidth under concurrency: throughput plateaus at ~5.8x on a 24-core run regardless of offered concurrency (12 vs 32 threads yield the same docs/s), and splitting work across independent processes degrades per-core efficiency by ~55%, the contended resource is below the process (the memory bus), not any lock (lock profiling shows zero contention; GC pauses are ~2 ms).
The copying dates to the original 2010 beam-search import; OPENNLP-1340 (2023) added the `List.copyOf` on top. It only becomes a *scaling* ceiling now that OPENNLP-1816 makes shared ME instances across threads practical.
## Fix
Replace the per-candidate `Sequence` copies with a private immutable `SearchNode` chain inside `bestSequences`:
- Child expansion becomes O(1) (parent link + outcome + prob instead of copying two lists).
- The outcome array for context generation is built from the chain when needed; `outcomes()` allocates a fresh array on each call.
- Only the winning sequences are converted to public `Sequence` objects, via `Sequence.add` which accumulates `score += StrictMath.log(p)` in the same order, bit-identical scores.
- `compareTo` mirrors `Sequence.compareTo` exactly (score only), so `PriorityQueue` behavior is unchanged, ties included.
No public API changes; one file changed in production code (`BeamSearch.java`, +80/−13).
## Correctness evidence
`BeamSearchEquivalenceTest` ports the pre-refactor algorithm inline as a reference and asserts bit-identical behavior (outcome order, scores, per-position probs via `doubleToRawLongBits`):
- 372 seeded combinations: 5 beam sizes × 6 input lengths × 2 cache settings, tight `minSequenceScore` thresholds, restrictive validators (including the `next.isEmpty()` fallback and reject-everything), k-best winner ordering.
- Existing suites green: `BeamSearchTest`, namefind / postag / chunker / lemmatizer (112 tests).
## Performance evidence
`BeamSearchBenchmark` (JMH, synthetic deterministic model, isolates the sequence mechanics; only public API, so the same class runs against both implementations, baseline = pre-refactor jar):
| sequenceLength | pre 24T | post 24T | ratio |
|---------------:|--------:|---------:|------:|
| 8 | 1.40M ops/s | 3.16M ops/s | 2.3x |
| 64 | 67.5k ops/s | 297k ops/s | 4.4x |
| 256 | 5,491 ops/s | 50,176 ops/s | 9.1x |
Pre-refactor scaling on 24 threads collapses with sequence length (6.2x to 2.5x); post-refactor scaling grows (7.0x to 11.5x).
Real-model measurements (`NameFinderME`, en-ner-person, shared instance, 1.3 KB docs):
- 24 pinned x86 cores: saturation throughput 5,609 to 12,304 docs/s (+119%); plateau knee moves from ~12 threads to ~20+.
- 8 pinned x86 cores: 8-thread scaling 4.69x to 7.05x.
- 4-core ARM (Pi 5): allocation per document −59%, saturated throughput ~2x (435 to 864 docs/s).
- Single-thread is roughly neutral on x86 (−2…−4%) and ~+27% on ARM.
Full methodology and the JMH table are in #1205; the numbers there were taken on main.
## Backport notes
- 2.x has no per-call search state (OPENNLP-1816 is 3.0 only), so `BeamSearch` stays as thread-unsafe as before and the concurrent equivalence test is not carried over. The cache now stores copies of the eval scores instead of the shared `probs` buffer, as on main.
- On main, `SearchNode.compareTo` breaks exact score ties by outcome chain. On 2.x it orders by score alone, exactly as `Sequence.compareTo` did: `NameFinderMETest` has a real exact tie where the canonical order changes the returned span, and a patch release should not change output. The tie-break test stays on main.
- Two tests added for the 2.x-specific parts: `exactTiesKeepTheReferenceOrder` and `partialTiesKeepTheReferenceOrder` run the equivalence matrix with constant-distribution models, so tied candidates are checked against the `Sequence`-based reference, and `testCachedScoresSurviveLaterEvaluations` pins the cache copy (it fails on `opennlp-2.x` before this change with `[a, b, b]`).
- Full `opennlp-tools` suite: 1,854 tests, 0 failures.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@opennlp.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [2.x] OPENNLP-1903: Replace per-candidate Sequence copies with chain nodes in BeamSearch (opennlp)
Posted by "mawiesne (via GitHub)" <gi...@apache.org>.
mawiesne commented on PR #1262:
URL: https://github.com/apache/opennlp/pull/1262#issuecomment-5489043237
@dependabot rebase
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@opennlp.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [2.x] OPENNLP-1903: Replace per-candidate Sequence copies with chain nodes in BeamSearch (opennlp)
Posted by "mawiesne (via GitHub)" <gi...@apache.org>.
mawiesne merged PR #1262:
URL: https://github.com/apache/opennlp/pull/1262
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@opennlp.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org