#4279: Proposal: Performance improvements for Data.IntMap
---------------------------------+------------------------------------------
Reporter: dons | Owner:
Type: proposal | Status: new
Priority: normal | Component: libraries/base
Version: 6.12.3 | Keywords:
Testcase: | Blockedby:
Os: Unknown/Multiple | Blocking:
Architecture: Unknown/Multiple | Failure: Runtime performance bug
---------------------------------+------------------------------------------
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
[[Image(http://i.imgur.com/RJ7dH.png,400px)]]
No bugs were identified in the development of the comprehensive testsuite,
which includes a large set of unit tests from
[http://twitter.com/kazu_yamamoto/status/22351727559 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
and Don Stewart.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4279>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
