More Web Proxy on the site http://driver.im/

research-article

Optimizing generics is easy!

Authors:

José Pedro Magalhães,

Stefan Holdermans,

Andres LöhAuthors Info & Claims

PEPM '10: Proceedings of the 2010 ACM SIGPLAN workshop on Partial evaluation and program manipulation

Pages 33 - 42

https://doi.org/10.1145/1706356.1706366

Published: 18 January 2010 Publication History

Abstract

Datatype-generic programming increases program reliability by reducing code duplication and enhancing reusability and modularity. Several generic programming libraries for Haskell have been developed in the past few years. These libraries have been compared in detail with respect to expressiveness, extensibility, typing issues, etc., but performance comparisons have been brief, limited, and preliminary. It is widely believed that generic programs run slower than hand-written code. In this paper we present an extensive benchmark suite for generic functions and analyze the potential for automatic code optimization at compilation time. Our benchmark confirms that generic programs, when compiled with the standard optimization flags of the Glasgow Haskell Compiler (GHC), are substantially slower than their hand-written counterparts. However, we also find that more advanced optimization capabilities of GHC can be used to further optimize generic functions, sometimes achieving the same efficiency as hand-written code.

References

[1]

Artem Alimarine and Sjaak Smetsers. Optimizing generic functions. In MPC'04, volume 3125 of LNCS, pages 16--31. Springer, 2004.

[2]

Roland Backhouse, Patrik Jansson, Johan Jeuring, and Lambert Meertens. Generic programming--an introduction. In AFP'98, volume 1608 of LNCS, pages 28--115. Springer, 1999.

[3]

Neil C.C. Brown and Adam T. Sampson. Alloy: Fast generic transformations for Haskell. In Haskell'09, pages 105--116. ACM, 2009.

Digital Library

[4]

Manuel M.T. Chakravarty, Gabriel C. Ditu, and Roman Leshchinskiy. Instant generics: Fast and easy, 2009. Draft version.

[5]

Jeremy Gibbons. Datatype-generic programming. In Spring School on Datatype-Generic Programming, volume 4719 of LNCS. Springer, 2007.

Digital Library

[6]

Ralf Hinze. Generics for the masses. Journal of Functional Programming, 16(4-5):451--483, 2006.

Digital Library

[7]

Ralf Hinze, Andres Löh, and Bruno C.d.S. Oliveira. "Scrap Your Boiler-plate" reloaded. In FLOPS'06, volume 3945 of LNCS. Springer, 2006.

Digital Library

[8]

Ralf Hinze, Johan Jeuring, and Andres Löh. Comparing approaches to generic programming in Haskell. In Datatype-Generic Programming, volume 4719 of LNCS, pages 72--149. Springer, 2007.

Digital Library

[9]

Stefan Holdermans, Johan Jeuring, Andres Löh, and Alexey Rodriguez Yakushev. Generic views on data types. In MPC'06, volume 4014 of LNCS, pages 209--234. Springer, 2006.

Digital Library

[10]

Johan Jeuring, Sean Leather, José Pedro Magalhães, and Alexey Rodriguez Yakushev. Libraries for generic programming in Haskell. In AFP'08, volume 5832 of LNCS, pages 165--229. Springer, 2009.

Digital Library

[11]

Ralf Lämmel and Simon Peyton Jones. Scrap your boilerplate: a practical approach to generic programming. In TLDI'03, pages 26--37, 2003.

Digital Library

[12]

Ralf Lämmel and Simon Peyton Jones. Scrap more boilerplate: reflection, zips, and generalised casts. In ICFP'04, pages 244--255. ACM, 2004.

Digital Library

[13]

Neil Mitchell and Colin Runciman. Uniform boilerplate and list processing. In Haskell'07, pages 49--60. ACM, 2007.

Digital Library

[14]

Thomas van Noort, Alexey Rodriguez Yakushev, Stefan Holdermans, Johan Jeuring, and Bastiaan Heeren. A lightweight approach to datatype-generic rewriting. In WGP'08, pages 13--24. ACM, 2008.

Digital Library

[15]

Bruno C.d.S. Oliveira, Ralf Hinze, and Andres Löh. Extensible and modular generics for the masses. In TFP'06, pages 199--216. Intellect, 2007.

[16]

Will Partain. The nofib benchmark suite of Haskell programs. In Proceedings of the 1992 Glasgow Workshop on Functional Programming, pages 195--202. Springer, 1993.

Digital Library

[17]

Simon Peyton Jones and Simon Marlow. Secrets of the glasgow haskell compiler inliner. Journal of Functional Programming, 12(4&5):393--433, 2002.

Digital Library

[18]

Simon Peyton Jones, Andrew Tolmach, and Tony Hoare. Playing by the rules: Rewriting as a practical optimisation technique in GHC. In Haskell'01, page 203, 2001.

[19]

Simon Peyton Jones et al. Haskell 98, Language and Libraries. The Revised Report. Cambridge University Press, 2003. A special issue of JFP.

[20]

Alexey Rodriguez Yakushev. Towards Getting Generic Programming Ready for Prime Time. PhD thesis, Utrecht University, 2009.

[21]

Alexey Rodriguez Yakushev, Johan Jeuring, Patrik Jansson, Alex Gerdes, Oleg Kiselyov, and Bruno C.d.S. Oliveira. Comparing libraries for generic programming in Haskell. In Haskell'08, pages 111--122. ACM, 2008.

Digital Library

[22]

Alexey Rodriguez Yakushev, Stefan Holdermans, Andres Löh, and Johan Jeuring. Generic programming with fixed points for mutually recursive datatypes. In ICFP'09, pages 233--244. ACM, 2009.

Digital Library

[23]

Tom Schrijvers, Simon Peyton Jones, Manuel M.T. Chakravarty, and Martin Sulzmann. Type checking with open type functions. In ICFP'08, pages 51--62. ACM, 2008.

Digital Library

[24]

Tim Sheard and Simon Peyton Jones. Template metaprogramming for Haskell. In Haskell'02, pages 1--16. ACM, 2002.

Digital Library

Cited By

Scott RNewton REisenberg R(2019)Generic and flexible defaults for verified, law-abiding type-class instancesProceedings of the 12th ACM SIGPLAN International Symposium on Haskell10.1145/3331545.3342591(15-29)Online publication date: 8-Aug-2019
https://dl.acm.org/doi/10.1145/3331545.3342591
Adams MFarmer AMagalhães JChin WHage J(2014)Optimizing SYB is easy!Proceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation10.1145/2543728.2543730(71-82)Online publication date: 11-Jan-2014
https://dl.acm.org/doi/10.1145/2543728.2543730
Burmako E(2013)Scala macros: let our powers combine!Proceedings of the 4th Workshop on Scala10.1145/2489837.2489840(1-10)Online publication date: 2-Jul-2013
https://dl.acm.org/doi/10.1145/2489837.2489840
Show More Cited By

Index Terms

Optimizing generics is easy!
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Functional languages

Recommendations

Optimizing SYB traversals is easy!

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 ...
Binders unbound
ICFP '11: Proceedings of the 16th ACM SIGPLAN international conference on Functional programming

Implementors of compilers, program refactorers, theorem provers, proof checkers, and other systems that manipulate syntax know that dealing with name binding is difficult to do well. Operations such as α-equivalence and capture-avoiding substitution ...
Binders unbound
ICFP '11

Implementors of compilers, program refactorers, theorem provers, proof checkers, and other systems that manipulate syntax know that dealing with name binding is difficult to do well. Operations such as α-equivalence and capture-avoiding substitution ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PEPM '10: Proceedings of the 2010 ACM SIGPLAN workshop on Partial evaluation and program manipulation

January 2010

168 pages

ISBN:9781605587271

DOI:10.1145/1706356

Program Chairs:
John Gallagher
Roskilde University, Denmark, and IMDEA Software, Spain
,
Janis Voigtländer
University of Bonn, Germany

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 January 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PEPM '10

Sponsor:

SIGPLAN

PEPM '10: Partial Evaluation and Program Manipulation

January 18 - 19, 2010

Madrid, Spain

Acceptance Rates

Overall Acceptance Rate 66 of 120 submissions, 55%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
261
Total Downloads

Downloads (Last 12 months)9
Downloads (Last 6 weeks)1

Reflects downloads up to 30 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Scott RNewton REisenberg R(2019)Generic and flexible defaults for verified, law-abiding type-class instancesProceedings of the 12th ACM SIGPLAN International Symposium on Haskell10.1145/3331545.3342591(15-29)Online publication date: 8-Aug-2019
https://dl.acm.org/doi/10.1145/3331545.3342591
Adams MFarmer AMagalhães JChin WHage J(2014)Optimizing SYB is easy!Proceedings of the ACM SIGPLAN 2014 Workshop on Partial Evaluation and Program Manipulation10.1145/2543728.2543730(71-82)Online publication date: 11-Jan-2014
https://dl.acm.org/doi/10.1145/2543728.2543730
Burmako E(2013)Scala macros: let our powers combine!Proceedings of the 4th Workshop on Scala10.1145/2489837.2489840(1-10)Online publication date: 2-Jul-2013
https://dl.acm.org/doi/10.1145/2489837.2489840
Magalhães J(2013)Optimisation of Generic Programs Through InliningImplementation and Application of Functional Languages10.1007/978-3-642-41582-1_7(104-121)Online publication date: 16-Nov-2013
https://doi.org/10.1007/978-3-642-41582-1_7
Magalhães JLöh A(2012)A Formal Comparison of Approaches to Datatype-Generic ProgrammingElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.76.676(50-67)Online publication date: 11-Feb-2012
https://doi.org/10.4204/EPTCS.76.6
Adams MDuBuisson T(2012)Template your boilerplateACM SIGPLAN Notices10.1145/2430532.236450947:12(13-24)Online publication date: 13-Sep-2012
https://dl.acm.org/doi/10.1145/2430532.2364509
Adams MDuBuisson TVoigtländer J(2012)Template your boilerplateProceedings of the 2012 Haskell Symposium10.1145/2364506.2364509(13-24)Online publication date: 13-Sep-2012
https://dl.acm.org/doi/10.1145/2364506.2364509
Magalhães JLöh AGarcia R(2012)The right kind of generic programmingProceedings of the 8th ACM SIGPLAN workshop on Generic programming10.1145/2364394.2364397(13-24)Online publication date: 12-Sep-2012
https://dl.acm.org/doi/10.1145/2364394.2364397
Magalhães Jde Haas WChakravarty MHu ZDanvy O(2011)Functional modelling of musical harmonyProceedings of the 16th ACM SIGPLAN international conference on Functional programming10.1145/2034773.2034797(156-162)Online publication date: 19-Sep-2011
https://dl.acm.org/doi/10.1145/2034773.2034797
Magalhães Jde Haas W(2011)Functional modelling of musical harmonyACM SIGPLAN Notices10.1145/2034574.203479746:9(156-162)Online publication date: 19-Sep-2011
https://dl.acm.org/doi/10.1145/2034574.2034797
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten