Proposal: Performance improvements for Data.IntMap
Following on from ticket #4277 (closed) 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.
- Add a testsuite, with coverage data (currently 82% of top level functions, and all core functions).
- Add a micro-benchmark suite based on Criterion, for empirical evidence of improvements to each function.
- 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
[[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 Kazu Yamamoto
Discussion
Unlike Data.Map (#4277 (closed)) 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:
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.
Trac metadata
Trac field | Value |
---|---|
Version | 6.12.3 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | libraries/base |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | |
Architecture |