Better performance of bottomupNoBridges by avoiding the triggering of ClassCastException

[bgaidioz]

Hello.

We have been profiling our application, which utilizes Kiama, and have observed large amounts of ClassCastException errors when it processes fairly large trees. These errors originate from strategies with the following (common) shape:

everywhere(rule[Exp] { case BinaryExp(...) => ... ; case UnaryExp(...) => ... })

We understand the presence of ClassCastException is part of the design as it is explicitly handled in several places as an indication that a strategy didn't apply. Nevertheless, the performance of the tree processing code significantly improved after rewriting these strategies against the Any type, since this doesn't trigger a ClassCastException when passing through nodes that aren't Exp.

// now use Any
everywhere(rule[Any] { case BinaryExp(...) => ... ; ...})

In our current profiling info, the next couple of places where the exception is thrown are bottomupNoBridges and Cloner.deepclone.

If patching bottomupNoBridges like in this PR, there's again a significant speedup. I can provide some numbers, but if there's any benchmark you'd prefer us to run, please let us know.

Flagging a strategy with the Any type isn't a pattern one sees in Kiama's examples, but it appears to be an effective way to improve performance. We're curious to get your comments/feedback on that.

Many thanks.

[inkytonik]

Thanks for the question. (And I'm very glad to hear from a Kiama user :-)

Since I haven't been actively working on Kiama for quite a while, I will need to get my head back into the code to properly answer your questions. I do recall that there were some subtle issues that led to the current design, but maybe the change(s) you suggest will be possible. I should have more time on the weekend, so I'll try to take a proper look then.