Worker/wrapper/makes it/faster

Hackett, Jennifer; Hutton, Graham

Abstract

Much research in program optimization has focused on formal approaches to correctness: proving that the meaning of programs is preserved by the optimisation. Paradoxically, there has been comparatively little work on formal approaches to efficiency: proving that the performance of optimized programs is actually improved. This paper addresses this problem for a general-purpose optimization technique, the worker/wrapper transformation. In particular, we use the call-by-need variant of improvement theory to establish conditions under which the worker/wrapper transformation is formally guaranteed to preserve or improve the time performance of programs in lazy languages such as Haskell.

Citation

Hackett, J., & Hutton, G. Worker/wrapper/makes it/faster. Presented at ACM SIGPLAN International Conference on Functional Programming (19th)

• Conference Name: ACM SIGPLAN International Conference on Functional Programming (19th)
• End Date: Sep 3, 2014
• Publication Date: Jan 1, 2014
• Deposit Date: Mar 18, 2015
• Publicly Available Date: Mar 18, 2015
• Peer Reviewed: Peer Reviewed
• Keywords: general recursion; improvement
• Public URL: https://nottingham-repository.worktribe.com/output/998635
• Publisher URL: http://dl.acm.org/citation.cfm?doid=2628136.2628142
• Additional Information: Published in: ICFP '14: proceedings of the 19th ACM SIGPLAN International Conference on Functional Programming. New York : ACM, 2014, ISBN: 978-1-4503-2873-9. pp. 95-107, doi: 10.1145/2628136.2628142