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

[rajat315315]

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:

Integer q = newstate.get(statesSet);

Problem

Previously, StateSet inherited equals(Object o) from IntSet. IntSet.equals() compares sets by invoking getArray() on both instances:

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