Haskell High Performance Programming

Haskell High Performance Programming

by Samuli Thomasson
Released September 2016
Publisher(s): Packt Publishing
ISBN: 9781786464217

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Boost the performance of your Haskell applications using optimization, concurrency, and parallel programming

About This Book

  • Explore the benefits of lazy evaluation, compiler features, and tools and libraries designed for high performance
  • Write fast programs at extremely high levels of abstraction
  • Work through practical examples that will help you address the challenges of writing efficient code

Who This Book Is For

To get the most out of this book, you need to have a working knowledge of reading and writing basic Haskell. No knowledge of performance, optimization, or concurrency is required.

What You Will Learn

  • Program idiomatic Haskell that's also surprisingly efficient
  • Improve performance of your code with data parallelism, inlining, and strictness annotations
  • Profile your programs to identify space leaks and missed opportunities for optimization
  • Find out how to choose the most efficient data and control structures
  • Optimize the Glasgow Haskell Compiler and runtime system for specific programs
  • See how to smoothly drop to lower abstractions wherever necessary
  • Execute programming for the GPU with Accelerate
  • Implement programming to easily scale to the cloud with Cloud Haskell

In Detail

Haskell, with its power to optimize the code and its high performance, is a natural candidate for high performance programming. It is especially well suited to stacking abstractions high with a relatively low performance cost. This book addresses the challenges of writing efficient code with lazy evaluation and techniques often used to optimize the performance of Haskell programs.

We open with an in-depth look at the evaluation of Haskell expressions and discuss optimization and benchmarking. You will learn to use parallelism and we'll explore the concept of streaming. We'll demonstrate the benefits of running multithreaded and concurrent applications. Next we'll guide you through various profiling tools that will help you identify performance issues in your program. We'll end our journey by looking at GPGPU, Cloud and Functional Reactive Programming in Haskell. At the very end there is a catalogue of robust library recommendations with code samples.

By the end of the book, you will be able to boost the performance of any app and prepare it to stand up to real-world punishment.

Style and approach

This easy-to-follow guide teaches new practices and techniques to optimize your code, and then moves towards more advanced ways to effectively write efficient Haskell code. Small and simple practical examples will help you test the concepts yourself, and you will be able to easily adapt them for any application.

Table of contents

  1. Haskell High Performance Programming
    1. Table of Contents
    2. Haskell High Performance Programming
    3. Credits
    4. About the Author
    5. About the Reviewer
    6. www.PacktPub.com
      1. eBooks, discount offers, and more
        1. Why subscribe?
    7. Preface
      1. What this book covers
      2. What you need for this book
      3. Who this book is for
      4. Conventions
      5. Reader feedback
      6. Customer support
        1. Downloading the example code
        2. Downloading the color images of this book
        3. Errata
        4. Piracy
        5. Questions
    8. 1. Identifying Bottlenecks
      1. Meeting lazy evaluation
        1. Writing sum correctly
        2. Weak head normal form
        3. Folding correctly
      2. Memoization and CAFs
        1. Constant applicative form
      3. Recursion and accumulators
        1. The worker/wrapper idiom
        2. Guarded recursion
        3. Accumulator parameters
      4. Inspecting time and space usage
        1. Increasing sharing and minimizing allocation
      5. Compiler code optimizations
        1. Inlining and stream fusion
        2. Polymorphism performance
        3. Partial functions
      6. Summary
    9. 2. Choosing the Correct Data Structures
      1. Annotating strictness and unpacking datatype fields
        1. Unbox with UNPACK
          1. Using anonymous tuples
        2. Performance of GADTs and branching
      2. Handling numerical data
      3. Handling binary and textual data
        1. Representing bit arrays
        2. Handling bytes and blobs of bytes
        3. Working with characters and strings
          1. Using the text library
        4. Builders for iterative construction
          1. Builders for strings
      4. Handling sequential data
        1. Using difference lists
          1. Difference list performance
          2. Difference list with the Writer monad
        2. Using zippers
          1. Accessing both ends fast with Seq
      5. Handling tabular data
        1. Using the vector package
      6. Handling sparse data
        1. Using the containers package
        2. Using the unordered-containers package
      7. Ephemeral data structures
        1. Mutable references are slow
        2. Using mutable arrays
        3. Using mutable vectors
          1. Bubble sort with vectors
      8. Working with monads and monad stacks
        1. The list monad and its transformer
        2. Free monads
        3. Working with monad transformers
        4. Speedup via continuation-passing style
      9. Summary
    10. 3. Profile and Benchmark to Your Heart's Content
      1. Profiling time and allocations
        1. Setting cost centres manually
        2. Setting cost centres automatically
        3. Installing libraries with profiling
        4. Debugging unexpected crashes with profiler
      2. Heap profiling
        1. Cost centre-based heap profiling
        2. Objects outside the heap
        3. Retainer profiling
        4. Biographical profiling
      3. Benchmarking using the criterion library
      4. Profile and monitor in real time
        1. Monitoring over HTTP with ekg
      5. Summary
    11. 4. The Devil's in the Detail
      1. The anatomy of a Haskell project
        1. Useful fields and flags in cabal files
        2. Test suites and benchmarks
        3. Using the stack tool
        4. Multi-package projects
      2. Erroring and handling exceptions
        1. Handling synchronous errors
        2. The exception hierarchy
        3. Handling asynchronous errors
        4. Throw and catch in other monads besides IO
      3. Writing tests for Haskell
        1. Property checks
        2. Unit testing with HUnit
        3. Test frameworks
      4. Trivia at term-level
        1. Coding in GHC PrimOps
        2. Control inlining
          1. Using rewrite rules
          2. Specializing definitions
          3. Phase control
      5. Trivia at type-level
        1. Phantom types
        2. Functional dependencies
        3. Type families and associated types
      6. Useful GHC extensions
        1. Monomorphism Restriction
        2. Extensions for patterns and guards
        3. Strict-by-default Haskell
      7. Summary
    12. 5. Parallelize for Performance
      1. Primitive parallelism and the Runtime System
        1. Spark away
        2. Subtle evaluation – pseq
        3. When in doubt, use the force
      2. The Eval monad and strategies
        1. Composing strategies
        2. Fine-tune granularity with chunking and buffering
      3. The Par monad and schedules
        1. spawn for futures and promises
        2. Non-deterministic parallelism with ParIO
      4. Diagnosing parallelism – ThreadScope
      5. Data parallel programming – Repa
        1. Playing with Repa in GHCi
          1. Mapping and delayed arrays
          2. Reduction via folding
        2. Manifest representations
        3. Delayed representation and fusion
        4. Indices, slicing, and extending arrays
        5. Convolution with stencils
        6. Cursored and partitioned arrays
        7. Writing fast Repa code
        8. Additional libraries
        9. Example from image processing
          1. Loading the image from file
          2. Identifying letters with convolution
          3. Extracting strings from an image
          4. Testing and evaluating performance
      6. Summary
    13. 6. I/O and Streaming
      1. Reading, writing, and handling resources
        1. Traps of lazy I/O
        2. File handles, buffering, and encoding
        3. Binary I/O
        4. Textual I/O
        5. I/O performance with filesystem objects
        6. Sockets and networking
          1. Acting as a TCP/IP client
          2. Acting as a TCP server (Unix domain sockets)
          3. Raw UDP traffic
          4. Networking above the transport layer
        7. Managing resources with ResourceT
      2. Streaming with side-effects
        1. Choosing a streaming library
        2. Simple streaming using io-streams
          1. Creating input streams
          2. Using combinators and output streams
          3. Handling exceptions and resources in streams
          4. An example of parsing using io-streams and attoparsec
        3. Streaming using pipes
          1. Composing and executing pipes
          2. For loops and category theory in pipes
          3. Handling exceptions in pipes
          4. Strengths and weaknesses of pipes
        4. Streaming using conduits
          1. Handling resources and exceptions in conduits
          2. Resuming conduits
      3. Logging in Haskell
        1. Logging with FastLogger
          1. More abstract loggers
        2. Timed log messages
        3. Monadic logging
          1. Customizing monadic loggers
      4. Summary
    14. 7. Concurrency and Performance
      1. Threads and concurrency primitives
        1. Threads and mutable references
          1. Avoid accumulating thunks
          2. Atomic operations with IORefs
        2. MVar
          1. MVars are fair
          2. MVar as a building block
        3. Broadcasting with Chan
      2. Software Transactional Memory
        1. STM example – Bank accounts
        2. Alternative transactions
        3. Exceptions in STM
      3. Runtime System and threads
        1. Masking asynchronous exceptions
      4. Asynchronous processing
        1. Using the Async API
          1. Async example – Timeouts
        2. Composing with Concurrently
      5. Lifting up from I/O
        1. Top-level mutable references
        2. Lifting from a base monad
        3. Lifting base with exception handling
      6. Summary
    15. 8. Tweaking the Compiler and Runtime System (GHC)
      1. Using GHC like a pro
        1. Operating GHC
          1. Circular dependencies
        2. Adjusting optimizations and transformations
          1. The state hack
          2. Floating lets in and out
          3. Eliminating common subexpressions
          4. Liberate-case duplicates code
        3. Compiling via the LLVM route
        4. Linking and building shared libraries
        5. Preprocessing Haskell source code
        6. Enforcing type-safety using Safe Haskell
      2. Tuning GHC's Runtime System
        1. Scheduler and green threads
          1. Sparks and spark pool
          2. Bounded threads and affinity
          3. Indefinite blocking and weak references
        2. Heap, stack, and memory management
          1. Evaluation stack in Haskell
        3. Tuning the garbage collector
          1. Parallel GC
        4. Profiling and tracing options
          1. Tracing using eventlog
          2. Options for profiling and debugging
      3. Summary of useful GHC options
        1. Basic usage
        2. The LLVM backend
        3. Turn optimizations on and off
        4. Configuring the Runtime System (compile-time)
        5. Safe Haskell
      4. Summary of useful RTS options
        1. Scheduler flags
        2. Memory management
        3. Garbage collection
        4. Runtime System statistics
        5. Profiling and debugging
      5. Summary
    16. 9. GHC Internals and Code Generation
      1. Interpreting GHC's internal representations
        1. Reading GHC Core
        2. Spineless tagless G-machine
      2. Primitive GHC-specific features
        1. Kinds encode type representation
      3. Datatype generic programming
        1. Working example – A generic sum
      4. Generating Haskell with Haskell
        1. Splicing with $(…)
        2. Names in templates
        3. Smart template constructors
        4. The constN function
        5. Lifting Haskell code to Q with quotation brackets
        6. Launching missiles during compilation
        7. Reifying Haskell data into template objects
        8. Deriving setters with Template Haskell
        9. Quasi-quoting for DSLs
      5. Summary
    17. 10. Foreign Function Interface
      1. From Haskell to C and C to Haskell
        1. Common types in Haskell and C
        2. Importing static functions and addresses
        3. Exporting Haskell functions
        4. Compiling a shared library
        5. Function pointers and wrappers
          1. Haskell callbacks from C
      2. Data marshal and stable pointers
        1. Allocating memory outside the heap
        2. Pointing to objects in the heap
        3. Marshalling abstract datatypes
        4. Marshalling in standard libraries
      3. Summary
    18. 11. Programming for the GPU with Accelerate
      1. Writing Accelerate programs
        1. Kernels – The motivation behind explicit use and run
        2. Working with elements and scalars
        3. Rudimentary array computations
        4. Example – Matrix multiplication
        5. Flow control and conditional execution
        6. Inspecting generated code
      2. Running with the CUDA backend
        1. Debugging CUDA programs
      3. More Accelerate concepts
        1. Working with tuples
        2. Folding, reducing, and segmenting
        3. Accelerated stencils
        4. Permutations in Accelerate
        5. Using the backend foreign function interface
      4. Summary
    19. 12. Scaling to the Cloud with Cloud Haskell
      1. Processes and message-passing
        1. Creating a message type
        2. Creating a Process
        3. Spawning and closures
        4. Running with the SimpleLocalNet backend
        5. Using channels
        6. Establishing bidirectional channels
        7. Calling a remote process
      2. Handling failure
        1. Firing up monitors
        2. Matching on the message queue
        3. Linking processes together
        4. Message-passing performance
      3. Nodes and networking
      4. Summary
    20. 13. Functional Reactive Programming
      1. The tiny discrete-time Elerea
        1. Mutually recursive signals
          1. Signalling side-effects
          2. Dynamically changing signal networks
          3. Performance and limitations in Elerea
      2. Events and signal functions with Yampa
        1. Adding state to signal functions
        2. Working with time
        3. Switching and discrete-time events
        4. Integrating to the real world
      3. Reactive-banana – Safe and simple semantics
        1. Example – First GUI application
        2. Graphical display with wxWidgets
      4. Combining events and behaviors
        1. Switching events and behaviors
        2. Observing moments on demand
        3. Recursion and semantics
        4. Adding input and output
          1. Input via polling or handlers
          2. Reactimate output
          3. Input and output dynamically
      5. Summary
    21. 14. Library Recommendations
      1. Representing data
      2. Functional graphs
      3. Numeric data for special use
      4. Encoding and serialization
        1. Binary serialization of Haskell values
        2. Encoding to and from other formats
        3. CSV input and output
      5. Persistent storage, SQL, and NoSQL
        1. acid-state and safecopy
        2. persistent and esqueleto
        3. HDBC and add-ons
      6. Networking and HTTP
        1. HTTP clients and servers
        2. Supplementary HTTP libraries
        3. JSON remote procedure calls
        4. Using WebSockets
        5. Programming a REST API
      7. Cryptography
      8. Web technologies
      9. Parsing and pretty-printing
        1. Regular expressions in Haskell
        2. Parsing XML
      10. Pretty-printing and text formatting
      11. Control and utility libraries
        1. Using lenses
        2. Easily converting between types (convertible)
        3. Using a custom Prelude
      12. Working with monads and transformers
        1. Monad morphisms – monad-unlift
      13. Handling exceptions
      14. Random number generators
      15. Parallel and concurrent programming
      16. Functional Reactive Programming
      17. Mathematics, statistics, and science
      18. Tools for research and sketching
      19. The HaskellR project
      20. Creating charts and diagrams
      21. Scripting and CLI applications
      22. Testing and benchmarking
      23. Summary
    22. Index

Product information

  • Title: Haskell High Performance Programming
  • Author(s): Samuli Thomasson
  • Release date: September 2016
  • Publisher(s): Packt Publishing
  • ISBN: 9781786464217