krickert opened a new pull request, #1205: URL: https://github.com/apache/opennlp/pull/1205
## Problem `BeamSearch.bestSequences` allocates O(beamSize × numOutcomes × n²) transient objects per document: 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 materialized lazily, once per node, and cached. - 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, so `PriorityQueue` behavior is unchanged. 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. - 384 concurrent decode verifications (8 threads, shared instance) vs serial reference. - Existing suites green: `BeamSearchTest`, namefind / postag / chunker / lemmatizer (112 tests). - Independent real-world check: span output of `NameFinderME` (en-ner-person) bit-identical serial vs concurrent over ~10k real documents (~215 tokens each), on x86 and aarch64. ## 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 → 2.5x); post-refactor scaling grows (7.0x → 11.5x). Real-model measurements (`NameFinderME`, en-ner-person, shared instance, 1.3 KB docs): - 24 pinned x86 cores: saturation throughput 5,609 → 12,304 docs/s (+119%); plateau knee moves from ~12 threads to ~20+. - 8 pinned x86 cores: 8-thread scaling 4.69x → 7.05x. - 4-core ARM (Pi 5): allocation per document −59%, saturated throughput ~2x (435 → 864 docs/s). - Single-thread is roughly neutral on x86 (−2…−4%) and ~+27% on ARM. Full methodology and the JMH table are in `opennlp-core/opennlp-runtime/BENCHMARKS.md`. ## Notes for reviewers - The per-thread `CacheState` (contexts cache, score buffers) is untouched; thread-safety contract from OPENNLP-1816 is preserved. - `Sequence` is deliberately not modified; the chain exists only inside the search. - Marked DRAFT pending any discussion on the approach; happy to adjust naming/placement of `SearchNode` or add it to the changelog entry wherever that's tracked these days. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
