MAF just got a lot faster

When building large automatic structures MAF should now work much quicker. I have taken a look at the algorithm used for FSA minimisation and have been able to make some significant improvements.
There are two main ideas:
1) Automata built by MAF have a significant number of states that are identical post trimming. These states are bound to remain merged, so there is no point inserting them into the hash multiple times.
Therefore the minimisation now does several passes that look for states that are identical. After the first pass more states may well have become identical. For the word acceptor and multiplier this process often reduces the number of states that need to be considered by minimisation by a factor of 5 or 10, so that the actual minimisation runs much quicker.
The second idea is to note that when a state category that is being refined during the minimisation has only one member, no significant further changes are possible for it (the number assigned may change in later passes, but that is all). For such states there is no need to examine the transition table and include it in the hash key.
A category also reaches a steady “decided” state if all its transitions are to “decided” states.
These two observations allow us to reduce the amount of key data in the hash. Although the saving is initially small it will become significant in later passes of minimisation, especially in the case where minimisation is not very effective. This will help to improve cache utilisation and reduce page faulting, especially when the FSA being minimised is very large.

Leave a Reply