Optimizing Pattern Matching

Abstract: We present improvements to the backtracking technique of pattern-matching compilation. Several optimizations are introduced, such as commutation of patterns, use of exhaustiveness information, and control flow optimization through the use of labeled static exceptions and context information. These optimizations have been integrated in the Objective-Caml compiler. They have shown good results in increasing the speed of pattern-matching intensive programs, without increasing final code size.

• 1  Introduction
• 2  Basics
  • 2.1  Patterns and Values
  • 2.2  Pattern Matching in ML
• 3  Compilation
  • 3.1  Output of the match compiler
  • 3.2  Initial state
  • 3.3  Classical scheme
• 4  Optimizations
  • 4.1  Optimizing the mixture rule
  • 4.2  Using exhaustiveness information
  • 4.3  Optimizing exits
  • 4.4  Aggressive control flow optimization
• 5  Compiling or-patterns
• 6  Our Compilation Scheme
  • 6.1  Operations on contexts
  • 6.2  Compilation scheme
• 7  Experimental results
• 8  Related Work
  • 8.1  Decision Trees vs Backtracking
  • 8.2  Compiling or-patterns
  • 8.3  Optimizations
• 9  Conclusion
• References

This document was translated from L^AT_EX by H^EV^EA.