Proposal: Significant performance improvements for Data.Map

[Don Stewart]

http://hackage.haskell.org/trac/ghc/ticket/4277

Proposal: Significant performance improvements for Data.Map

Description

   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.

  52. http://research.microsoft.com/~simonpj/papers/containers/containers.pdf

   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.

  53. http://is.gd/eJHIE
  54. http://www.workerwrapper.com/
  55. http://hackage.haskell.org/trac/ghc/ticket/888


   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.

  56. http://code.haskell.org/~dons/tests/containers/hpc_index.html
  57. http://hackage.haskell.org/package/criterion

   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).

   http://i.imgur.com/05BWe.png

  58. http://is.gd/eJHIE

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

  60. http://twitter.com/kazu_yamamoto/status/22351727559

   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 http://code.haskell.org/~dons/code/containers/

   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.