Engineering Large Projects in a Functional Language

I had the opportunity to speak at DevNation on July 10th in Portland, and gave the following talk, an updated version of Galois’ collective experiences developing Haskell projects over the past decade. You can download the .pdf.

Abstract

Galois has been building software systems in Haskell for the past decade. This talk describes some of what we’ve learned about in-the-large, commercial Haskell programming in that time. I’ll look at when and where we use Haskell. At correctness, productivity, scalabilty, maintainability, and what language features we like: types, purity, types, abstractions, types, concurrency, types!

We’ll also look at the Haskell toolchain: FFI, HPC, Cabal, compiler, libraries, build systems, etc, and being a commercial entity in a largely open source community.

ghc-gc-tune: Tuning Haskell GC settings for fun and profit

Inspired by a comment by Simon Marlow on Stack Overflow, about the time and space tradeoffs we make with garbage collection, particularly with a generational GCs, I wrote a small program, ghc-gc-tune, to traverse the garbage collector variable space, to see the relationship between settings and program performance. Given a program, it will show you an (optionally interactive) graph of how -A and -H flags to the garbage collector affect performance.

Previously I’ve had good success exploring multi-variable spaces for optimizations with GAs in Haskell, to find strictness flags and LLVM flag settings, so I was keen to see what the GC space looked like. In this initial GC search, however, I don’t use a GA, instead just measuring time as two variables change over the entire space.

Here’s an example for the binary-trees language shootout benchmark, where the GHC default settings are known to be suboptimal (the benchmark disallows changes to the default runtime GC settings):

Running time of the binary-trees benchmark as -A and -H vary

The flags we use are:

  • -A, the size of the initial thread allocation area for the youngest generation.
  • -H, the suggested overall heap size

ghc-gc-tune, in the style of ghc-core, wraps a compiled Haskell program, and runs it with varying values of -A and -H, recording various statistics about the program. The output can be rendered interactively, or to png, pdf or svg. It would augment use of heap profiling, ThreadScope and ghc-core for analyzing and improving Haskell program behavior.

In this case, ghc-gc-tune recommends the somewhat surprising -A64k -H32M, and binary-trees runs in 1.12s at N=16, while for the default GC settings it completes in 1.56s. So ghc-gc-tune found settings that improved performance by 28%.  Nice.

I already knew that a large -A setting helped this program (corresponding to the broad plateau for large -A values in the above graph), however, I was surprised to see the best result was with a very small -A setting, and medium sized -H setting, resulting in only 5% of time spent in GC, and 36M total allocated — the narrow valley on the far side of the graph. Very interesting! And is that my L2 cache in the square at x= 2M, y = 2M? Sure looks like it.

Here’s a video of the same graph in the tool’s interactive mode (without any -t flag):

Currently, the sampling is vary simplistic, with a fixed set of logscale values taken. A clever sampling algorithm would measure the heap used in the default case, and compute a range based on that, possibly with cutoffs for very pessimistic GC flags.

Another example: pidigits, with what I would consider far more typical behavior. Though again, a surprisingly small -A setting does well, and there’s an interesting pathological result with extremely large -H and very small -A settings.

PiDigiits GC space

You can get ghc-gc-tune from Hackage, via cabal, and note that it requires gnuplot installed. Let me know if you find it useful, and I welcome patches!

Future work will be to graph the Z axis as space, instead of time (so we can find GC settings that minimize the footprint), as well as adding other variables (such as parallel GC settings, and varying the number of generations).

Popular Haskell Packages: Q2 2010 report

Here is some data on downloads of Haskell libraries and apps on Hackage, for the first half of 2010.

The Hackage dependency graph

Hackage is the central repository of open source Haskell libraries and tools. Once they install the Haskell Platform, users get more libraries from Hackage, via “cabal install”.

Headlines

May was the most popular month for Hackage ever, breaking 150k downloads in a single month for the first time.

The 2000th Haskell package was released on April 16.

Total downloads on Hackage since 2006 have passed 2.4 million, with 780 thousand downloads in 2010 so far (double the total from the same time in 2009).

Totals

Total cabal packages: 2182. (+ 208 in Q2).

Total contributing developers: 575 (42 new developers in Q2)

90 day moving average: 12 packages per day uploaded.

Total downloads from Hackage 2007-present: 2.42 million

Average monthly downloads in 2010: 130 thousand.

Top of the Pops

The top 15 most popular libraries in the first half of 2010 were:

  1. HTTP
  2. parsec (+1)
  3. zlib (-1)
  4. binary (+1)
  5. network (+2)
  6. utf8-string (-2)
  7. Cabal (+1)
  8. QuickCheck (-2)
  9. mtl (+1)
  10. haskell-src-exts (-1)
  11. regex-base
  12. deepseq (+6)
  13. ghc-paths (+2)
  14. hslogger (+6)
  15. regex-posix (-2)

Top 15 most popular applications in the first half of 2010:

  1. cabal-install
  2. xmonad
  3. haddock (+1)
  4. cpphs (-1)
  5. happy
  6. darcs (+1)
  7. alex (+1)
  8. hscolour (-2)
  9. pandoc
  10. hlint
  11. leksah
  12. xmobar
  13. yi
  14. hint
  15. agda

Honorable Mentions

  • The Galois xml library was more popular in the first half of 2010 than HaXml, dethroning HaXml for the first time.
  • text has made it into the top 30 libraries
  • HDBC continues to be the most popular database library
  • vector has almost surpassed array in downloads (array is part of the Haskell Platform though)
  • wxHaskell is still more popular than gtk2hs on Hackage,  though gtk2hs has almost caught up.

You can read all the 2010 data for your favorite packages, and ranked by 2010 popularity.

Top Libraries by Category

  • Networking: HTTP, network, network-bytestring, curl
  • Parsing: parsec, polyparse, attoparsec
  • Compression: zlib, zip-archive
  • Binary formats: binary, cereal
  • Text formats: utf8-string, text, dataenc
  • Markup: pandoc, xhtml, tagsoup, html
  • JSON: json
  • Atom/RSS: feed
  • XML: xml, HaXml, hexpat
  • Web services:  happstack, snap
  • GUIs: wxHaskell, gtk2hs
  • Graphics: SDL, cairo, gd
  • Templates: HStringTemplate
  • Testing: QuickCheck, HUnit, testpack, hpc
  • Control: mtl, transformers, monads-fd
  • Languages: haskell-src-exts, haskell-src, HJavaScript
  • Regexes: regex-{base,posix,compat,tdfa}, pcre-light
  • Logging: hslogger
  • Generics: uniplate, syb-with-class, syb
  • 3D: OpenGL
  • Edit history: haskeline
  • Concurrency and parallelism: parallel, stm
  • Databases: HDBC
  • Arrays: array, vector, hmatrix
  • Hashing: pureMD5, SHA
  • Data structures: containers, fingertree, dlist
  • Science:  statistics
  • Benchmarking: criterion
  • Storage: hs3

Is there anything else you see in the data?

Open Source Bridge Talk: Multicore Haskell Now

In June I had the opportunity to talk about approaches to parallel programming in Haskell at Open Source Bridge: “a new conference for developers working with open source technologies and for people interested in learning the open source way.”

Here are the slides (::PDF), and the source that accompanied the tutorial:

The abstract for  the session:

Haskell is a functional language built for parallel and concurrent programming. You can take an off-the-shelf copy of GHC and write high performance parallel programs right now. This tutorial will teach you how to exploit parallelism through Haskell on your commodity multicore machine, to make your code faster. We will introduce key parallel programming models, as implemented in Haskell, including:

  • semi-explicit parallelism via sparks
  • explicit parallelism via threads and shared memory
  • software transactional memory

and look at how to build faster programs using these abstractions. We will also look at the engineering considerations when writing parallel programs, and the tools Haskell provides for debugging and reasoning about parallel programs.

This is a hands on tutorial session: bring your laptops, there will be code!

There are a hell of a lot of Haskell libraries now. What are we going to do about it?

The Haskell community has reached a bit of a milestone: there are now more than 2000 open source libraries for Haskell on Hackage! However, with this also comes a problem: how do you work out which library to use? (Without learning one Haskell library a day for the next 6 years?) Which ones are robust, and supported, and which ones aren’t? This isn’t a new problem in open source: the Perl community has faced it with CPAN for a decade or more. Now Haskell is in the same situation.

In fact, it’s kind of startling to look back: in 2006, there were only a handful of open source Haskell libraries for developers to use in their projects (just HDBC, zlib, libxml, Crypto…). Today, there are 2121 (more by the time you read this) libraries for Haskell, available as source on http://hackage.haskell.org (only a “cabal install” away), and often 100s of Haskell libraries in binary form on your favorite distro. You can even follow the package flood on Twitter.

Here’s what the growth in available Haskell libraries over the last 4 years looks like:

We passed 1000 libraries in early 2009, and doubled that a year later.

So this is great for the Haskell dev community. In some areas, like database interfacing, we’ve gone from a single option (HDBC) to a full range, including new stuff like, uh, well, Cassandra, CouchDB, Amazon SimpleDB, MongoDB, Tokyo Cabinet, and pure Haskell libs like TCache, or safe, high level libs like HaskellDB.

We’re rapidly running into CPAN-like problems of just managing the weight of so much Haskell code. How do you know which one to use? Should you use, say, Galois’ xml library, or Lemmih’s xml library? . Someone recently said “It is bewildering trying to figure out which ones are actively supported and which ones are zombie projects that stopped working years ago.”

So what are we doing about it?

There are four efforts underway to help Haskellers manage this work, and you can contribute!

  1. The Haskell Platform – a easy, one-click installer for the core system, including a blessed set of libraries, with a commercially friendly BSD license (like most of Hackage). At the moment, this means just these libraries, and we need developers to propose new additions to the blessed set.
  2. Google Summer of Code: Hackage 2.0 – we have Matt Gruen working this summer to finish the implementation of Hackage 2.0 – an improved Hackage that will allow for many new features to help sort out the wheat from the chaff in Haskell packages: build reports, wiki commenting, and social voting.
  3. Google Summer of Code: Cabal Test: we also have Thomas Tuegel working on “cabal test”  — to allow automated testing and reporting of cabalized (and thus, all of Hackage). This is the second plank in the solidifying the quality assurance story for Hackage.
  4. Regular regression testing of Hackage: having all that code is great – it means we can do regular regression testing of compilers and tools on a multi-million line Haskell codebase. For the 6.10 GHC release, for example, we were able to narrow breakages of all known open source Haskell to just 5% of Hackage, and post detailed instructions on how to address those changes. This gives us significant stability.

So, the HP to make it simpler to install Haskell and get started with a good set of libraries (several hundred thousand downloads of the installers so far!), a better Hackage to help us rate and rank packages, regression testing against Hackage to keep things stable, and in particular, test reporting support to make it easier to do quality assurance estimates.

How would you like to see changed in the Haskell library world? What libraries do you love? What do you hate? How do you find the packages you need?

And you don’t have to wait for others to solve this. Write tools to pick the best libs. Do your own quality ratings and share them. Write reviews of packages, and compare them, then let everyone know.

This is open source – it is up to you to help make things happen.

The 7 Haskell projects in the Google Summer of Code

Congratulations to the 7 successful applications to do Haskell projects for the Google Summer of Code 2010. The quality of proposals was extremely high this year, and we look forward to more such excellent proposals next year.

The students who will be working on projects for Haskell.org this summer are:

  1. Thomas Tuegel, Improvements to Cabal’s test support
  2. Matthew Gruen, Infrastructure for a more social Hackage 2.0
  3. Jasper Van der Jeugt, A high performance HTML generation library
  4. Alp Mestanogullari, Improvements to the GHC LLVM backend
  5. Marco Silva, Implementing the Immix Garbage Collection Algorithm
  6. Matthew Arsenault, GObject-Introspection based bindings for gtk2hs
  7. Alexey Levan, Improving Darcs’ network performance

Well done all! And you can cheer on and support these students this summer — keep track of their progress on the Haskell Reddit, check out their code, and help with feedback and support.

And thank you to Google for sponsoring Haskell.org projects for the 5th year!

Popular Haskell Packages: Q1 2010 report

Here is some data on downloads of Haskell libraries and apps on Hackage, for the first quarter of 2010.

The Hackage dependency graph

Hackage is the central repository of open source Haskell libraries and tools. Once they install the Haskell Platform, users get more libraries from Hackage, via “cabal install”.

Headlines

March was the most popular month for Hackage ever. And we’re closing in on 2000 packages, and 2 million “cabal installs” in the next month or so.

Totals

Total cabal packages: 1976. (+ 256 in Q1).

Total contributing developers: 533

90 day moving average: 11.5 packages per day uploaded (up from 10.5).

Total downloads from Hackage 2007-present: 1.88 million (up 350k in Q1)

Downloads in March 2010: 145,752 (new monthly record)

Top of the Pops

The top 15 most popular libraries in the first quarter were:

  1. HTTP
  2. zlib
  3. parsec
  4. utf8-string
  5. binary
  6. QuickCheck
  7. network
  8. Cabal
  9. haskell-src-exts
  10. mtl
  11. regex-base
  12. uniplate
  13. regex-posix
  14. X11
  15. ghc-paths

Top 15 most popular applications in Q1:

  1. cabal-install
  2. xmonad
  3. cpphs
  4. haddock
  5. happy
  6. hscolour
  7. darcs
  8. alex
  9. pandoc
  10. hlint
  11. leksah
  12. yi
  13. agda
  14. texmath
  15. gitit

Honorable Mentions

  • The deepseq is in the top 20 packages of the year.
  • HaXml and HDBC remain the most popular xml and database libraries (though xml-light is closing in)
  • wxHaskell is rising up, as the only cabal-installable major gui library
  • vector and text are quickly rising as the preferred arrays and unicode libraries

You can read all the Q1 data for your favorite packages, and ranked by Q1 popularity.

And for non-Haskellers, how does your favourite open source community compare?

Follow

Get every new post delivered to your Inbox.

Join 59 other followers