Proposal: Significant performance improvements for Data.Map

[dons]

Milan Straka's recent  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  dramatically improves performance across the API. Three standard techniques are applied to the code:

•  Worker/Wrapper transformations of recursive functions with constant arguments (aka. the  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,  with coverage data (currently 91% 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 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).

No bugs were identified in the development of the comprehensive testsuite, which includes a large set of unit tests from  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.

[dons]

With original failure behavior for updateAt

[simonmar]

I pushed the patches, perhaps a bit hastily (didn't notice there was a consideration period). If there are objections we can always roll back.

[milan]

Applied with INLINE => INLINABLE changes.

[dons]

This didn't follow the libraries process at all, and I've not actually seen the final patch.

I understand the release deadlines are coming up, but clobbering the workflow like this is frustrating.

Where is the final patch for review? Did Milan decide for us?