#4277: Proposal: Significant performance improvements for Data.Map
---------------------------------+------------------------------------------
Reporter: dons | Owner: dons
Type: proposal | Status: new
Priority: normal | Component: libraries (other)
Version: 6.12.3 | Keywords: map, containers
Testcase: | Blockedby:
Os: Unknown/Multiple | Blocking:
Architecture: Unknown/Multiple | Failure: Runtime performance bug
---------------------------------+------------------------------------------
Milan Straka's recent
[http://research.microsoft.com/~simonpj/papers/containers/containers.pdf
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 [http://is.gd/eJHIE dramatically
improves performance] across the API. Three standard techniques are
applied to the code:
* [http://www.workerwrapper.com/ Worker/Wrapper transformations] of
recursive functions with constant arguments (aka. the
[http://hackage.haskell.org/trac/ghc/ticket/888 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,
[http://code.haskell.org/~dons/tests/containers/hpc_index.html with
coverage data] (currently ''91%'' of top level functions, and all core
functions).
2. Add a micro-benchmark suite based on
[http://hackage.haskell.org/package/criterion 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/eJHIE 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).
[[Image(http://i.imgur.com/05BWe.png, 500px)]]
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]
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/4277>
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
