Proposal: Significant performance improvements for Data.Map

Don Stewart dons at
Sun Aug 29 09:15:45 EDT 2010

Proposal: Significant performance improvements for Data.Map


   Milan Straka's recent [52] Haskell Symposium paper (PDF) shed light on
   the containers:Data.Map library, indicating there were both algorithmic
   and stylistic performance improvements to be made.


   This proposal provides a patch that [53] dramatically improves
   performance across the API. Three standard techniques are applied to
   the code:

     * [54] Worker/Wrapper transformations of recursive functions with
       constant arguments (aka. the [55] static argument transformation).

     * Explicit inlining of wrapper functions.

     * Explicit strictness of keys to functions.


   Three complementary, but orthogonal patches are provided.

    1. Add a testsuite, [56] with coverage data (currently 91% of top
       level functions, and all core functions).

    2. Add a micro-benchmark suite based on [57] Criterion, for empirical
       evidence of improvements to each function.

    3. The optimization patch itself.

   All 3 patches should be applied, under this proposal.


   The [58] benchmark results are very strong:

     * An average speedup across the core api of 47% (on intel i7 / linux
       64 bit), and;

     * 36% on Mac / intel core 2 duo 32 bit).


   No bugs were identified in the development of the comprehensive
   testsuite, which includes a large set of unit tests from [60] Kazu


   A fork of the containers package, with the 3 patches (and a version
   bump to make it easier to test out) is available:

     darcs get

   Separately, the patches are attached to this ticket.

   The consideration period is 3 weeks (before ICFP).


   Work carried out over 28/29th August, 2010 in Utrecht, NL, by Johan
   Tibell and Don Stewart.

More information about the Libraries mailing list