Haskell Optimization Handbook

Table of Contents

• 1. Preliminaries
  • 1.1. How to Use This Book
  • 1.2. The Programs of Consistent Lethargy
  • 1.3. Philosophies of Optimization
  • 1.4. References and Footnotes
  • 1.5. The Golden Rules of Performance-Oriented Haskell
  • 1.6. Setting up a Reproducible Test Environment
  • 1.7. How To Debug
• 2. Measurement, Profiling, and Observation
  • 2.1. Binary Profiling and Probing
    • 2.1.1. Reading Asm
    • 2.1.2. The Linux time command
    • 2.1.3. The Linux perf utility
    • 2.1.4. Dtrace
    • 2.1.5. Valgrind
    • 2.1.6. Using Cachegrind
  • 2.2. Thread Level Profiling
    • 2.2.1. ThreadScope
  • 2.3. Cmm Probes and Profiling
    • 2.3.1. Reading Cmm
  • 2.4. Stg and RTS Probes and Profiling
    • 2.4.1. Reading Stg
    • 2.4.2. GHC Flags
    • 2.4.3. GHC Debug
    • 2.4.4. -ddump-timings
    • 2.4.5. TickyTicky
    • 2.4.6. The Reduced Stack Method
  • 2.5. Core Probes and Profiling
    • 2.5.1. Reading Core
    • 2.5.2. Memory Footprints of Data Types
    • 2.5.3. Summary
    • 2.5.4. References
  • 2.6. Haskell Level Probing and Profiling
    • 2.6.1. GHC Flags
    • 2.6.2. Info-Table Profiling
    • 2.6.3. Eventlog
    • 2.6.4. Criterion, Gauge, and Tasty-Bench
    • 2.6.5. Flamegraphs
    • 2.6.6. Weigh
    • 2.6.7. Inspection Testing
    • 2.6.8. Nothunks
• 3. Optimizations
  • 3.1. GHC Flags
    • 3.1.1. GHC Flags
  • 3.2. GHC Optimizations
    • 3.2.1. Defunctionalization
    • 3.2.2. The Static Arguments Transformation
    • 3.2.3. Lambda Lifting
    • 3.2.4. Loopification
    • 3.2.5. Manual Worker/Wrapper
    • 3.2.6. Understanding Demand Analysis
  • 3.3. Library Based Changes
    • 3.3.1. Lower Impedance with Better Data Structures
  • 3.4. Library Agnostic Changes
    • 3.4.1. Ordering Data Constructors
    • 3.4.2. Wrangling Lazy Tuples
    • 3.4.3. Appropriate Folding
    • 3.4.4. Avoid Runtime Checks with Parse Don’t Validate:
    • 3.4.5. Data-Oriented Design
    • 3.4.6. Using GHC.Exts
    • 3.4.7. Inlining Pragma and Friends
    • 3.4.8. Specialization
    • 3.4.9. Fusion and Rules
    • 3.4.10. Unboxing
    • 3.4.11. Unpacked Product Types
    • 3.4.12. Avoiding Nested Monad Transformers
    • 3.4.13. Unroll Monad Transformer Stacks
    • 3.4.14. The OneShot Monad Trick
    • 3.4.15. Continuation Passing Style
    • 3.4.16. Using Levity Polymorphism
    • 3.4.17. Using Backpack to Unroll Data Structures
• 4. Case Studies
  • 4.1. Impact of Seq Removal on SBV’s Internal Cache
  • 4.2. SBV and the Bizarre GHC Regression
  • 4.3. Klister: A First Pass Performance Engineering
  • 4.4. Rearchitecting with Data-Oriented Design

Indices and tables

• Index

• Search Page

• Glossary

Bibliography

[1]

Chris Okasaki. Purely Functional Data Structures. Cambridge University Press, 1998. doi:10.1017/CBO9780511530104.

[2]

Simon Peyton Jones and Andre Santos. A transformation-based optimiser for haskell. Science of Computer Programming, October 1997. URL: https://www.microsoft.com/en-us/research/publication/a-transformation-based-optimiser-for-haskell/.

[3]

Simon Marlow and Simon Peyton Jones. Making a fast curry: push/enter vs. eval/apply for higher-order languages. In Proceedings of the Ninth ACM SIGPLAN International Conference on Functional Programming, ICFP '04, 4–15. New York, NY, USA, 2004. Association for Computing Machinery. URL: https://doi.org/10.1145/1016850.1016856, doi:10.1145/1016850.1016856.

[4]

Simon Marlow, Alexey Rodriguez Yakushev, and Simon Peyton Jones. Faster laziness using dynamic pointer tagging. SIGPLAN Not., 42(9):277–288, oct 2007. URL: https://doi.org/10.1145/1291220.1291194, doi:10.1145/1291220.1291194.

[5]

Peyton Jones, Simon L, and Simon Peyton Jones. Implementing lazy functional languages on stock hardware: the spineless tagless g-machine. Journal of Functional Programming, 2:127–202, July 1992. URL: https://www.microsoft.com/en-us/research/publication/implementing-lazy-functional-languages-on-stock-hardware-the-spineless-tagless-g-machine/.

[6]

Phil Bagwell. Ideal hash trees. Technical Report, Ecole polytechnique fédérale de Lausanne, 2001.

[7]

Thomas Johnsson. Lambda lifting: transforming programs to recursive equations. In Jean-Pierre Jouannaud, editor, Functional Programming Languages and Computer Architecture, 190–203. Berlin, Heidelberg, 1985. Springer Berlin Heidelberg.

[8]

Sebastian Graf and Simon Peyton Jones. Selective lambda lifting. 2019. URL: https://arxiv.org/abs/1910.11717, doi:10.48550/ARXIV.1910.11717.

[9]

Paul Hudak, John Hughes, Simon Peyton Jones, and Philip Wadler. A history of haskell: being lazy with class. In Proceedings of the Third ACM SIGPLAN Conference on History of Programming Languages, HOPL III, 12–1–12–55. New York, NY, USA, 2007. Association for Computing Machinery. URL: https://doi.org/10.1145/1238844.1238856, doi:10.1145/1238844.1238856.

[10]

Benjamin C. Pierce. Types and Programming Languages. The MIT Press, 1st edition, 2002. ISBN 0262162091.

[11]

Sebastian Graf. Call arity vs. demand analysis. August 2017.

[12]

Ilya Sergey, Dimitrios Vytiniotis, and Simon Peyton Jones. Modular, higher-order cardinality analysis in theory and practice. SIGPLAN Not., 49(1):335–347, jan 2014. URL: https://doi.org/10.1145/2578855.2535861, doi:10.1145/2578855.2535861.

[13]

Simon L. Peyton Jones and Jon Salkild. The spineless tagless g-machine. In Proceedings of the Fourth International Conference on Functional Programming Languages and Computer Architecture, FPCA '89, 184–201. New York, NY, USA, 1989. Association for Computing Machinery. URL: https://doi.org/10.1145/99370.99385, doi:10.1145/99370.99385.

[14]

Luke Maurer, Paul Downen, Zena M. Ariola, and Simon Peyton Jones. Compiling without continuations. In Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2017, 482–494. New York, NY, USA, 2017. Association for Computing Machinery. URL: https://doi.org/10.1145/3062341.3062380, doi:10.1145/3062341.3062380.

[15]

Richard A. Eisenberg and Simon Peyton Jones. Levity polymorphism. SIGPLAN Not., 52(6):525–539, jun 2017. URL: https://doi.org/10.1145/3140587.3062357, doi:10.1145/3140587.3062357.

[16]

WD Partain, A Santos, and Simon Peyton Jones. Let-floating: moving bindings to give faster programs. May 1996. ACM SIGPLAN International Conference on Functional Programming (ICFP'96). URL: https://www.microsoft.com/en-us/research/publication/let-floating-moving-bindings-to-give-faster-programs/.