GSoC 2018 results
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
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:
I wrote some comments here.
I used the great criterion to benchmark time and weigh for space usage.
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/.
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.
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
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.
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.
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
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.
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 :)
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.