The key sig map lookup (the most expensive addition) is only performed for user-added key sigs, and not for instances for key sigs generated by the program (at the beginning of staves or elsewhere) which are the great majority.

The alternative is to add in several locations (when a key sig is added, removed or changed) two of such lookups, one to get the delta from previous key sig and one to find the next key sig and 'alert' it of the preceding change. Each of those locations should be maintained, should the logic change.

The rest of the changes, while dealing with more special cases of naturals (going to no accidentals, changing between sharps and flats versus reducing sharps or flats) are actually faster; for instance the loops on naturals are executed only if there are naturals (I noticed that conditions can be improved, though).