apache / apache/lucene

ENH: Optimize StateSet.equals to avoid array allocation and sorting in Operations.determinize()

Open
#16,413 0 comments 0 reactions 0 assignees View on GitHub
type:enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.