mozart/mozart2 — pull request #207 by kennytm (2014-07-11 20:53:36+00:00)
Title: Improve pattern matching performance for common cases

This commit adds several special cases to `patternMatch()`, so that for most common patterns we can return without needing to go into `fullPatternMatch()`.

Performance change of test cases after applying this patch (on my machine):

* /bench/compiler.oz: **1.15 sec → 0.71 sec** (60% faster)
* /bench/diff.oz: **8.37 sec → 1.14 sec** (600% faster)
* Speed of other tests are roughly the same.
* Total time spent: **14.35 sec → 6.17 sec** (130% faster)

----

This is created because `diff.oz` takes too long to run :smiley:

I used Instruments to profile ozemulator, and found that over 80% of execution time is spent in `patternMatch()`. So improving the speed of `patternMatch()` should improve the overall execution time. Most of the time in `patternMatch()` is spent in `StructuralEquatable::equals()`, which mainly involves Tuples pushing its elements and labels to the WalkStack. So it's likely we can speed things up by avoiding the WalkStack.

Checking the inputs to `patternMatch()`, I find that the patterns are almost always like `X#Y#...`, `H|T`, `X#Y|T`, `const|T` or constants. So I have added special cases for the above forms. And indeed the running speed for the compiler and `diff.oz` dramatically increases, as they both use pattern matching extensively.