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.

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

Performance experiment: partitioning heuristic during DFA minimization #277

Open
silentbicycle opened this issue Oct 30, 2020 · 0 comments

Comments

@silentbicycle
Copy link
Collaborator

Inside minimise.c's try_partition, we split an equivalence class in place, but it's arbitrarily committing to keeping whichever states lead to the same EC as the first state in the EC list. While the non-determinism doesn't affect correctness (since it will run to a fixpoint either way), using the counts to decide which to modify in place and which to separate out may improve performance.

The change would appear in update_after_parittion -- if both the src and dst ECs have more than one state and the src EC has less (or more) than the dst EC, swap them, so the larger EC always appears earlier (or later). The special case for one state is so that ECs with only 1 state end up in the "done" region at the end.

I suspect always breaking out the smaller EC should perform better, but it needs benchmarking.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant