Proposal: Performance improvements for Data.IntMap

Don Stewart dons at
Tue Aug 31 06:09:34 EDT 2010

#4279: Proposal: Performance improvements for Data.IntMap

 Following on from ticket #4277 here is a similar patch for Data.IntMap.

 This proposal provides a patch that improves performance for many parts of
 the API. Two standard techniques are applied to the code:

  * worker/wrapper transformations of functions with multiple static arguments
  * inlining of non-recursive wrappers

Three complementary, but orthogonal patches are provided.

  1. Add a testsuite, with
         [ coverage data]
         (currently 82% of top level functions, and all core functions).
  2. Add a micro-benchmark suite based on Criterion, for empirical evidence
         of improvements to each function.
  3. The optimization patch itself.

All 3 patches should be applied, under this proposal.

 The [ benchmark results] are relatively clear:

  * 13.3% faster on i7 / x86_64 / Linux
  * 9.95% faster on Mac OS X 10.5 / Xeon / 32 bit

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


 Unlike Data.Map (#4277) the performance results are less significant for
 Data.IntMap. There is one main reasons:

  * Data.IntMap already has strict keys

 So the strict key improvements seen there are less impressive here.
 Similarly, worker/wrapper to float out a single Int key has less of an
 impact  than floating out more complex structures used as keys.

 Hence, a number of functions are unchanged (modulo inlining), including
 lookup and delete. insert is slightly improved (due to inlining).


 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

More information about the Libraries mailing list