Hai Liu
Abstract
The Glasgow Haskell Compiler (GHC) is a well supported optimizing compiler for the Haskell programming language, along with its own extensions to the language and libraries. Haskell's lazy semantics imposes a runtime model which is in general difficult to implement efficiently. GHC achieves good performance across a wide variety of programs via aggressive optimization taking advantage of the lack of side effects, and by targeting a carefully tuned virtual machine. The Intel Labs Haskell Research Compiler uses GHC as a frontend, but provides a new whole-program optimizing backend by compiling the GHC intermediate representation to a relatively generic functional language compilation platform. We found that GHC's external Core language was relatively easy to use, but reusing GHC's libraries and achieving full compatibility were harder. For certain classes of programs, our platform provides substantial performance benefits over GHC alone, performing 2x faster than GHC with the LLVM backend on selected modern performance-oriented benchmarks; for other classes of programs, the benefits of GHC's tuned virtual machine continue to outweigh the benefits of more aggressive whole program optimization. Overall we achieve parity with GHC with the LLVM backend. In this paper, we describe our Haskell compiler stack, its implementation and optimization approach, and present benchmark results comparing it to GHC.
- T. A. Anderson. Optimizations in a private nursery-based garbage collector. In ISMM, pages 21--30. ACM, 2010. Google Scholar
Digital Library
- T. A. Anderson, N. Glew, P. Guo, B. T. Lewis, W. Liu, Z. Liu, L. Petersen, M. Rajagopalan, J. M. Stichnoth, G. Wu, and D. Zhang. Pillar: A parallel implementation language. In LCPC, volume 5234 of LNCS, pages 141--155. Springer-Verlag, 2007.Google Scholar
- A. Appel and T. Jim. Shrinking lambda expressions in linear time. JFP, 7(5), Sept. 1997. Google ScholarDigital Library
- N. Benton, A. Kennedy, S. Lindley, and C. Russo. Shrinking reductions in SML.NET. In IFL 2004, volume 3474 of LNCS, pages 142--159. Springer-Verlag, 2005. Google ScholarDigital Library
- L. Bergstrom and J. Reppy. Arity raising in Manticore. In IFL 2009, volume 6041 of LNCS, pages 90--106. Springer-Verlag, 2010. Google ScholarDigital Library
- M. C. Bolingbroke and S. L. Peyton Jones. Types are calling conventions. In Haskell Symposium, pages 1--12. ACM, Sept. 2009. Google ScholarDigital Library
- A. Dijkstra, J. Fokker, and S. D. Swierstra. The architecture of the Utrecht Haskell compiler. In Haskell Symposium, pages 93--104. ACM, Sept. 2009. Google ScholarDigital Library
- C. Flanagan, A. Sabry, B. F. Duba, and M. Felleisen. The essence of compiling with continuations. In PLDI, pages 237--247. ACM, June 1993. Google ScholarDigital Library
- M. Fluet and S. Weeks. Contification using dominators. In ICFP, pages 2--13. ACM, Sept. 2001. Google ScholarDigital Library
- N. Glew and L. Petersen. Type-preserving flow analysis and interprocedural unboxing (extended version), Mar. 2012. arXiv: 1203.1986 {cs.PL}, http://arXiv.org/.Google Scholar
- N. Glew, T. Sweeney, and L. Petersen. A multivalued language with a dependent type system. In Dependently Typed Programming. ACM, Sept. 2013. Google ScholarDigital Library
- K. Jensen, P. Hjresen, and M. Rosendahl. Efficient strictness analysis of Haskell. In Static Analysis, volume 864 of LNCS, pages 346--362. Springer-Verlag, 1994.Google ScholarCross Ref
- G. Keller, M. M. Chakravarty, R. Leshchinskiy, S. Peyton Jones, and B. Lippmeier. Regular, shape-polymorphic, parallel arrays in Haskell. ACM Sigplan Notices, 45(9):261--272, 2010. Google ScholarDigital Library
- S. Marlow and S. Peyton Jones. The new GHC/Hugs runtime system. URL http://research.microsoft.com/apps/pubs/default.aspx?id=68449. Jan. 1998.Google Scholar
- S. Marlow and S. Peyton Jones. Making a fast curry: Push/enter vs. eval/apply for higher-order languages. JFP, 16(4-5):415--449, July 2006. Google ScholarDigital Library
- S. Marlow and S. L. Peyton Jones. Multicore garbage collection with local heaps. In ISMM, pages 21--32. ACM, June 2011. Google ScholarDigital Library
- J. Meacham. JHC: John's Haskell compiler, 2007. URL http://repetae.net/computer/jhc/.Google Scholar
- W. Partain. The nofib benchmark suite of Haskell programs. In Functional Programming, Glasgow 1992, Workshops in Computing, pages 195--202. Springer-Verlag, 1993. Google ScholarDigital Library
- L. Petersen and N. Glew. GC-safe interprocedural unboxing. In CC, volume 7210 of LNCS, pages 165--184. Springer-Verlag, Apr. 2012. Google ScholarDigital Library
- L. Petersen, T. A. Anderson, H. Liu, and N. Glew. Measuring the Haskell gap. Manuscript available from the authors, June 2013.Google Scholar
- L. Petersen, D. Orchard, and N. Glew. Automatic SIMD vectorization for Haskell. In ICFP. ACM, Sept. 2013. Google ScholarDigital Library
- S. Peyton Jones and W. Partain. Measuring the effectiveness of a simple strictness analyser. In Functional Programming, Glasgow 1993, Workshops in Computing, pages 201--221. Springer-Verlag, 1 994.Google Scholar
- S. Peyton Jones, N. Ramsey, and F. Reig. C--: A portable assembly language that supports garbage collection. In PPDP, volume 1702 of LNCS, pages 1--28. Springer-Verlag, Oct. 1999. Google ScholarDigital Library
- S. Peyton Jones, A. Reid, F. Henderson, T. Hoare, and S. Marlow. A semantics for imprecise exceptions. In PLDI, pages 25--36. ACM, May 1999. Google ScholarDigital Library
- S. L. Peyton Jones. Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine. JFP, 2(2):127--202, Apr. 1992.Google Scholar
- J. C. Reynolds. Definitional interpreters for higher-order programming languages. In ACM Annual Conference, pages 717--740. ACM, 1972. Google ScholarDigital Library
- M. Sulzmann, M. M. T. Chakravarty, S. Peyton Jones, and K. Donnelly. System F with type equality coercions. In TLDI, pages 53--66. ACM, Jan. 2007. Google ScholarDigital Library
- D. A. Terei and M. M. Chakravarty. An LLVM backend for GHC. ACM Sigplan Notices, 45(11):109--120, 2010. Google ScholarDigital Library
- A. Tolmach. An external representation for the GHC Core language. URL http://www.haskell.org/ghc/docs/papers/core.ps.gz. Sept. 2001.Google Scholar
- S. Weeks. Whole-program compilation in MLton. In ML Workshop, pages 1--1. ACM, Sept. 2006. Google ScholarDigital Library
- Y. Wu and J. R. Larus. Static branch frequency and program profile analysis. In MICRO, pages 1--11. IEEE, Nov. 1994. Google ScholarDigital Library
Index Terms
- The Intel labs Haskell research compiler
Recommendations
Automatic SIMD vectorization for Haskell
ICFP '13Expressing algorithms using immutable arrays greatly simplifies the challenges of automatic SIMD vectorization, since several important classes of dependency violations cannot occur. The Haskell programming language provides libraries for programming ...
The Intel labs Haskell research compiler
Haskell '13: Proceedings of the 2013 ACM SIGPLAN symposium on HaskellThe Glasgow Haskell Compiler (GHC) is a well supported optimizing compiler for the Haskell programming language, along with its own extensions to the language and libraries. Haskell's lazy semantics imposes a runtime model which is in general difficult ...
Automatic SIMD vectorization for Haskell
ICFP '13: Proceedings of the 18th ACM SIGPLAN international conference on Functional programmingExpressing algorithms using immutable arrays greatly simplifies the challenges of automatic SIMD vectorization, since several important classes of dependency violations cannot occur. The Haskell programming language provides libraries for programming ...
Comments