ENH: Optimize StateSet.equals to avoid array allocation and sorting in Operations.determinize()
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
### Description
During automaton determinization (`Operations.determinize`), Lucene uses a hash map (`Map 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 & GC Allocation Metrics
Evaluated using `ThreadMXBean.getThreadAllocatedBytes()` and `GarbageCollectorMXBean` across 30 determinization runs on complex NFA union automata (1,000 regex terms with overlapping state sets):
| GC / Memory Metric | Baseline (Before Optimization) | Optimized (Option C) | Improvement / Reduction |
| :--- | :--- | :--- | :--- |
| **Total Heap Memory Allocated (30 runs)** | **548.72 MB** | **100.42 MB** | **81.7% reduction (~448.3 MB saved!)** |
| **Avg Heap Allocated per `determinize()`** | **18.29 MB** (19,179,268 bytes) | **3.35 MB** (3,510,065 bytes) | **Saved ~14.94 MB of garbage per call!** |
| **GC Collection Cycles** | **11 GC cycles** | **2 GC cycles** | **81.8% reduction in GC pauses** |
| **Total GC Pause Time** | **142 ms** | **25 ms** | **82.4% reduction in GC pause duration** |
| **Average Execution Time** | **140.43 ms** | **76.30 ms** | **~1.84x faster execution speed** |
Contributor guide
Research direction
Start at Operations.determinize(), focusing on the newstate.get(statesSet) lookup, then inspect StateSet.java and its inherited IntSet.equals() and getArray() behavior. Implement and validate the StateSet equality optimization described in the issue, ensuring set equality remains correct without array allocation or sorting; compare determinization performance and allocation metrics against the reported baseline.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- search
- Issue type
- Refactor
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Quiet
- Clarity
- Clearly specified
- Newbie friendliness
- 68/100