Proposal: Performance improvements for Data.Set

[Johan Tibell]

Ticket: http://hackage.haskell.org/trac/ghc/ticket/4280

Proposal: Performance improvements for Data.Set

Following on from ticket #4277 here is a similar patch for Data.Set.

This proposal provides a patch that improves performance for many parts of
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.

 * Add a testsuite, with  coverage data (currently 51% 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:

32% faster on OS X 10.5.8 on 2 GHz Core 2 Duo

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/libraries/attachments/20100831/e943d778/attachment.html