#4279: Proposal: Performance improvements for Data.IntMap http://hackage.haskell.org/trac/ghc/ticket/4279 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 [http://code.haskell.org/~dons/tests/containers/intmap/hpc_index.html 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 [http://is.gd/eN7qN 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 http://i.imgur.com/RJ7dH.png No bugs were identified in the development of the comprehensive testsuite, which includes a large set of unit tests from Kazu Yamamoto. ''Discussion'' 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 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