Rename things, and move functions

[sayrer]

I added a bunch of tracking to nfa.go. That was good. Tim correctly suggested these were noisy (tough problem, and he was trying not to be a nitpicker on working code). I'll do the work, but not until #481 (nfa2dfa) is done. I am not sure if they'll just fall out anyway, and I can't predict it in advance of #481.

I loathe people that say they'll fix things later and don't. So, I'll put myself on the hook here.

[timbray]

The just-posted #485 will beautify and correct nfa2Dfa but not actually bring it into play. The next phase of work is going to have to enhance that function with memory trackers. If there are any improvements you want to suggest before that, go ahead.

[sayrer]

That one looks fine, but you said nfa.go looked kind of ugly, and I agree. Once you get nfa2dfa turned on, there should be some renames. It's not a big deal, but let's get the algorithm first (and these patches are better).

[sayrer]

The issue is that you said "I spend a lot of time looking at nfa.go". [so can you move some of this stuff]

The answer is yes, but the file needs to be renamed to automaton.go, and you have nfa2dfa there. Right there on the precipice. Don't get into renames when you're about to win.

[timbray]

Fair enough. I'm actually going to put a couple of days into looking at TestShellStyleBuildTime() which is currently the single biggest bleeding sore in Quamina in my mind. Its performance should have been greatly enhanced by #482 although I wasn't measuring systematically enough, and all the "spinner" stuff in nfa.go is there to try to work around the slowdown, and mostly fails. Should also do a quick 2.0.1 release to get the performance bump for people who like to use official releases.

[timbray]

It's the build time not the run time, although the run time is interesting too. Totally dominated by epsilon wrangling. Tl;dr: The NFA merge logic is doing too many "splice" merges and if you look at the FA, the first few states have like 200 epsilons each. Have a look at the memory profiler, blecch.

[sayrer]

Post a benchmark, I'll do my best to get it.

[timbray]

It's TestShellStyleBuildTime(), not set up with the go benchmark stuff but that doesn't get in the profiler's way.

[sayrer]

Ah, there still needs to be Lazy DFA - build DFA states on-demand during matching.

[sayrer]

Summary:                                                                               
  - Flattening: Reduces splices 998→2, helps NFA traversal by avoiding deep recursion    
  - nfa2Dfa: Still explodes because subset construction creates DFA states for each      
  combination of NFA states. With 900 epsilon targets, that's exponential                
                                                                                         
  To enable nfa2Dfa for shell-style patterns, a different approach is needed:            
  1. Lazy DFA - build DFA states on-demand during matching                               
  2. Better merge strategy - actually merge states instead of splicing (but my attempt   
  caused blowup during merge)                                                            
  3. Accept limitation - nfa2Dfa may not be practical for large merged wildcards         
                                                                                         
  The core issue: splicing avoids exponential blowup during merge, but shifts the problem
   to DFA conversion. Actually merging states avoids DFA blowup but causes merge blowup. 
  It's a fundamental tradeoff.             

[sayrer]

#486 has it, and the lazy DFA construction has been suggested before. I think this does not account for the RE2-style management, though.

[timbray]

I'm pretty sure I'm not going to do the lazy DFA construction. The whole point of Quamina is that once you've got the patterns loaded, the performance is predictable (and fast). So I was thinking of trying to do the DFA at AddPattern() time and either succeeding or failing depending on the user-controlled memory budget.

[sayrer]

I think the suggestion in #481 is right. It has to be lazy DFA, because the budget (memory is sensible) can depend on the input, not only the pattern. The issue being that perfectly reasonable patterns can blow up based on the input. So, you can have a really fast DFA that spins out on certain inputs. There, you should go with the NFA.

You can detect bad DFAs during pattern creation (and that will get some of them), but the input can influence the issue as well. That is a new insight to me, from reading the RE2 code, not my invention.

Essentially, the runtime fallback is only for troll input, and will never be hit during normal operation.

[timbray]

The issue being that perfectly reasonable patterns can blow up based on the input. So, you can have a really fast DFA that spins out on certain inputs. There, you should go with the NFA.

My belief at the moment is that explosions based on input are because of big epsilon closures. So if we make our budgeting decisions at AddPattern() time, callers of Quamina can rely on predictably acceptable-to-amazing performance. But, that belief might be challenged by experience, let's see.

[sayrer]

Yes, agree. What should happen after the new things like nfa2dfa are on is to write a fuzzer. That's the way to detect that stuff, but it's not reasonable to attempt until the in-flight things are done.

[sayrer]

I investigated this 5 different ways. This is the verbose explanation:

Lazy DFA is probably the most directly applicable idea. Instead of committing upfront to
NFA traversal for the entire automaton, you build DFA states on-demand during
search —  cache the (NFA state set → DFA state) mapping and reuse it across matches.
You get near-DFA speed on hot paths while avoiding the exponential blowup of full
DFA construction. 

Quamina already has the stateLists machinery in state_lists.go that maps sorted
pointer sets to DFA states — it's conceptually close but isn't used on the traversal hot path.