The project

The goal of this summer of code project was dual:

  • Write and use a benchmarking-suite for standard graphs libraries in Haskell.
  • Improve Alga’s performances.

The summary of the project can be found at https://summerofcode.withgoogle.com/projects/#5856533557018624

The beginning

During the community bonding period, I sent some patches to hash-graph and FGL while starting the benchmarking-suite. I also looked at some issues in Alga’s repository.

The community was very warm and helped me even with my newcomer questions, which is always pleasant!

The benchmarking suite

The suite is currently benchmarking 4 libraries:

With 18 functions.

Results can be found at: https://github.com/haskell-perf/graphs/tree/master/results.

The main chart:

svg

I wrote some comments here.

I used the great criterion to benchmark time and weigh for space usage.

Functionalities

Using different parameters you can (at run-time):

  • Choose on which standard graphs (and their size) functions will be benchmarked.
  • Choose if you want to include the graph-creation time.
  • Choose specifically libraries/functions to be benchmarked.

It features different renderers:

  • In plain text
  • In markdown

And different analysis tools:

  • A summary that displays the fastest functions.
  • An abstract calculating a ratio between the largest benchmarks.
  • A quick comparison, when benchmarking two libraries, to say at a glance which one was faster.

Full usage instructions can be found in https://github.com/haskell-perf/graphs/.

Flags

The suite is easily configurable at build-time. You can disable a library (and thus not depend on it) or a functionality using cabal flags.

Chart

As requested by a reddit user, I have implemented a chart renderer using the great Chart library.

It was a hard time, because of the little error bars which are not implemented by default in the Chart library.

Alga

Tutorial

I wrote a little tutorial for newcomers to Alga. It can be found here: https://nobrakal.github.io/alga-tutorial/

Written in LaTex and converted to HTML using the great (haskell-powered) pandoc. It means that one can easily produce a PDF file out of the code or modify the text quickly without dealing with HTML.

Agda

I have made a little incursion in the proofs of the algebra of Alga formalized in agda. I didn’t know this language and I learned a lot! I only proved a little axiom and failed to prove a bigger theorem, the full story is here.

Optimizations

A big part of optimizations was made using GHC techniques like rewrite rules, specialization and inlining. I have made a summary of what I have learned here to help others. This work was mainly made in the Algebra.Graph module.

Regression suite

I have made a little script that change the benchmarking-suite into a regression suite specialized for Alga. It compares two states of the Alga repository (like master and another branch being under a pull request). It is highly tricky (in fact it is a suite of sed commands) but very useful. It can be done for any other graph library. Feel free to ask!

What is left

As always, there is some work left. Mainly I have opened some issues on Alga that I was not able to close yet. There is also some code cleanup to do in the benchmarking suite as well as in the regression suite for Alga.

If you find any missing features, don’t hesitate to tell me, I will be glad to help.

Feelings

After this list, I want to say that I had a very good time doing this Google Summer of Code. I think I learned more about functional programming during these three months than during two years in a bachelor of computer science. Moreover, the Haskell community (which I observed through reddit) is extraordinary kind.

I will be happy to continue the work started here, as I became a maintainer of alga :)

Thanks

I want to really thank Andrey Mokhov for his active and very useful mentorship! All of this project would not be what it is without his support and wise pieces of advice.

Also, thanks to the entire Haskell community for its encouragements and critics.