rajat315315 opened a new issue, #16413: URL: https://github.com/apache/lucene/issues/16413
### Description ### Description During automaton determinization (`Operations.determinize`), Lucene uses a hash map (`Map<IntSet, Integer> newstate`) to deduplicate sets of NFA states into single DFA states. For every transition interval point, `Operations.determinize` looks up the current active state set: ```java Integer q = newstate.get(statesSet); ``` #### Problem Previously, `StateSet` inherited `equals(Object o)` from `IntSet`. `IntSet.equals()` compares sets by invoking `getArray()` on both instances: ```java Arrays.equals(getArray(), 0, size(), that.getArray(), 0, that.size()); ``` In `StateSet`, `getArray()` checks `arrayUpdated`. Because `statesSet` is mutated (`incr`/`decr`) on every transition point, `arrayUpdated` is constantly reset to `false`. As a result, every `newstate.get(statesSet)` lookup match triggered: 1. `arrayCache = new int[inner.size()]` (allocating a new primitive array on the heap). 2. `Arrays.sort(arrayCache)` (sorting the primitive array in $O(K \log K)$ time). On complex automata (such as multi-term regex unions, wildcards, or fuzzy query rewrite automata), this generated substantial Garbage Collection pressure from primitive array allocations and wasted CPU cycles on redundant sorting during map lookups. #### Solution Override `.equals(Object o)` directly in `StateSet.java` to perform direct, order-independent containment checks on the internal `IntIntHashMap`: * Compare set sizes and pre-computed 64-bit hash codes (`longHashCode()`). * For `FrozenIntSet` targets, iterate through `frozen.values` and verify `inner.containsKey(val)` for each element. * Bypasses `getArray()`, completely eliminating array allocations and `Arrays.sort()` on lookup hits. --- ### 📊 Benchmark Results Evaluated on complex NFA determinization (unions of 1,000 multi-branch regular expressions with overlapping transition intervals): | Metric | Baseline | Optimized | Difference | | :--- | :--- | :--- | :--- | | **Average `determinize()` Time** | **33.25 ms** | **18.70 ms** | **~43.8% speedup (~1.78x faster)** | | **Heap Allocations on Lookup Hits** | $O(N \cdot K)$ primitive arrays | **0 allocations** | **100% eliminated** | | **Array Sorting Overhead (`Arrays.sort`)** | $O(N \cdot K \log K)$ sorting | **0 sorting calls** | **100% eliminated** | --- -- 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] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
