Cache Epsilon Closures to Reduce Runtime Computation #12

New issue

Closed

opened 2026-03-11 18:09:30 +03:00 by NiXTheDev · 0 comments

NiXTheDev commented

2026-03-11 18:09:30 +03:00

(Migrated from github.com)

Goal: Reduce the overhead of repeatedly computing epsilon closures during matching.

In engine.rs, epsilon_closure is called frequently (every step). It traverses the NFA graph to find all states reachable via epsilon transitions. This can be expensive for large NFAs.

Proposed Solution:
During NFA construction (nfa.rs), precompute the epsilon closure for each state and store it as a Vec<StateId>. Then, at matching time, simply use the precomputed list instead of recomputing.

Implementation Steps:

In Nfa, add a field epsilon_closures: Vec<Vec<StateId>> where epsilon_closures[state_id] is the list of states reachable via epsilon (including itself?).
After building the NFA, run a BFS/DFS from each state to compute its epsilon closure. Store the result.
In epsilon_closure, use &self.nfa.epsilon_closures[state_id] to get the closure, then filter/combine as needed (maybe you need to handle group start/end transitions separately? Those are epsilon transitions but have side effects; they must be processed individually, not cached).
- You might need two caches: one for pure epsilon (no side effects) and one for transitions with actions.

Alternative: Use the "PikeVM" approach where epsilon transitions are handled on-the-fly with a frontier set; caching may still help.

Benchmark:

Measure performance on patterns with many epsilon transitions (e.g., nested groups).

**Goal**: Reduce the overhead of repeatedly computing epsilon closures during matching. In `engine.rs`, `epsilon_closure` is called frequently (every step). It traverses the NFA graph to find all states reachable via epsilon transitions. This can be expensive for large NFAs. **Proposed Solution**: During NFA construction (`nfa.rs`), precompute the epsilon closure for each state and store it as a `Vec<StateId>`. Then, at matching time, simply use the precomputed list instead of recomputing. **Implementation Steps**: 1. In `Nfa`, add a field `epsilon_closures: Vec<Vec<StateId>>` where `epsilon_closures[state_id]` is the list of states reachable via epsilon (including itself?). 2. After building the NFA, run a BFS/DFS from each state to compute its epsilon closure. Store the result. 3. In `epsilon_closure`, use `&self.nfa.epsilon_closures[state_id]` to get the closure, then filter/combine as needed (maybe you need to handle group start/end transitions separately? Those are epsilon transitions but have side effects; they must be processed individually, not cached). - You might need two caches: one for pure epsilon (no side effects) and one for transitions with actions. **Alternative**: Use the "PikeVM" approach where epsilon transitions are handled on-the-fly with a frontier set; caching may still help. **Benchmark**: - Measure performance on patterns with many epsilon transitions (e.g., nested groups).