Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

fix: state-machine size explosion on wildcards #188

Closed
timbray opened this issue Jan 27, 2023 · 2 comments · Fixed by #308
Closed

fix: state-machine size explosion on wildcards #188

timbray opened this issue Jan 27, 2023 · 2 comments · Fixed by #308

Comments

@timbray
Copy link
Owner

timbray commented Jan 27, 2023

Certain combinations of shellstyle patterns cause an explosion in the size of the state machine along the lines of O(2**N). The effect is that AddPattern() can take seconds to execute and burn memory. We know this is not inevitable because AWS Event Ruler can build this kind of machine quickly and economically.

Initial thoughts:

  1. Characterize the problem properly
  2. Make nice String() on smallTable and related types
  3. Replace list_maker with something much better thought through - it's a hack
  4. Fix the problem
@timbray timbray mentioned this issue May 25, 2024
Merged
@timbray
Copy link
Owner Author

timbray commented Jun 6, 2024

Oops, we fixed the DFA/NFA mess, but the state explosion is still an issue. Re-opening.

@timbray timbray reopened this Jun 6, 2024
timbray added a commit that referenced this issue Jun 9, 2024
@timbray
addresses issue #188
8eb41db 
prevent state explosions with epsilon transitions

Signed-off-by: Tim Bray <[email protected]>
@timbray timbray mentioned this issue Jun 9, 2024
Merged
timbray added a commit that referenced this issue Jun 17, 2024
@timbray
addresses issue #188 (#314)
21b3414 
* addresses issue #188

prevent state explosions with epsilon transitions

Signed-off-by: Tim Bray <[email protected]>

* correct race condition from final optimization

Signed-off-by: Tim Bray <[email protected]>

* bring performance back up to about 80% of current

Signed-off-by: Tim Bray <[email protected]>

* update README to remove warnings about memory explosion

Signed-off-by: Tim Bray <[email protected]>

---------

Signed-off-by: Tim Bray <[email protected]>
@timbray
Copy link
Owner Author

timbray commented Jun 17, 2024

Fixed in #314

@timbray timbray closed this as completed Jun 17, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

kaizen: clean up state finite automata timbray/quamina
1 participant
@timbray