libfsm icon indicating copy to clipboard operation
libfsm copied to clipboard

Performance experiment: partitioning heuristic during DFA minimization

Open silentbicycle opened this issue 5 years ago • 0 comments

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.

silentbicycle avatar Oct 30 '20 19:10 silentbicycle