M. D. Adams, A. Farmer, and J. P. Magalhães, “Optimizing SYB Is Easy!,” in Proceedings of the 2014 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation, PEPM ’14, ACM, 2014. Won Best Paper Award.

Links

• http://www.ittc.ku.edu/csdl/fpg/files/Adams-14-OSIE.pdf

Abstract

The most widely used generic-programming system in the Haskell community, Scrap Your Boilerplate (SYB), also happens to be one of the slowest. Generic traversals in SYB are about an order of magnitude slower than equivalent handwritten, non-generic traversals. Thus while SYB allows the concise expression of many traversals, its use incurs a significant runtime cost. Existing techniques for optimizing other generic-programming systems are not able to eliminate this overhead.

This paper presents an optimization that completely eliminates this cost. The optimization takes advantage of domain-specific knowledge about the structure of SYB and in so doing can optimize SYB-style traversals to be as fast as handwritten, non-generic code.

This paper presents both the formal structure of the optimization and the results of benchmarking the optimized SYB code against both unoptimized SYB code and handwritten, non-generic code. In these benchmarks, the optimized SYB code matches the performance of handwritten code even when the unoptimized SYB code is an order of magnitude or more slower.

BibTeX

@inproceedings{Adams:14:OSIE,
  author = {Michael D. Adams and Andrew Farmer and Jos\'{e} Pedro {Magalh\~{a}es}},
  title = {Optimizing {SYB} {Is} {Easy}!},
  booktitle = {Proceedings of the 2014 ACM SIGPLAN Workshop on Partial Evaluation and Program Manipulation},
  series = {PEPM '14},
  publisher = {ACM},
  location = {San Diego, California, USA},
  year = {2014},
  note = {Won Best Paper Award},
}