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 often 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. Essentially, it is a partial evaluation that takes advantage of domain-specific knowledge about the structure of SYB. It optimizes SYB-style traversals to be as fast as handwritten, non-generic code, and benchmarks show that this optimization improves the speed of SYB-style code by an order of magnitude or more.
optimization; partial evaluation; datatype-generic programming; Haskell; Scrap Your Boilerplate (SYB); performance
, , and . Optimizing SYB is easy! In Proceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation, PEPM ’14. ACM, New York, NY, USA, 2014. ISBN 978-1-4503-2619-3. doi: 10.1145/2543728.2543730.
@inproceedings{adams2013sybopt,
author = {Adams, Michael D. and Farmer, Andrew and Magalh{\~a}es, Jos{\'e} Pedro},
title = {Optimizing {SYB} is Easy!},
booktitle = {Proceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation},
year = {2014},
series = {PEPM~'14},
address = {New York, NY, USA},
publisher = {ACM},
isbn = {978-1-4503-2619-3},
doi = {10.1145/2543728.2543730},
}