Opened 4 years ago

Closed 4 years ago

Last modified 4 years ago

#4277 closed proposal (fixed)

Proposal: Significant performance improvements for Data.Map

Reported by: dons Owned by: dons
Priority: normal Milestone:
Component: libraries (other) Version: 6.12.3
Keywords: map, containers Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Difficulty:
Test Case: Blocked By:
Blocking: #4278, #4311 Related Tickets:

Description

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:

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).

http://i.imgur.com/05BWe.png

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.

Attachments (2)

add-a-comprehensive-testsuite-for-data_map.dpatch (110.9 KB) - added by dons 4 years ago.
add-a-comprehensive-testsuite-for-data_map.2.dpatch (112.1 KB) - added by dons 4 years ago.
With original failure behavior for updateAt

Download all attachments as: .zip

Change History (7)

comment:1 Changed 4 years ago by tibbe

  • Blocking 4278 added

Changed 4 years ago by dons

With original failure behavior for updateAt

comment:2 Changed 4 years ago by 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.

comment:3 Changed 4 years ago by milan

  • Blocking 4311 added

comment:4 Changed 4 years ago by milan

  • Resolution set to fixed
  • Status changed from new to closed

Applied with INLINE => INLINABLE changes.

comment:5 Changed 4 years ago by 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?

Note: See TracTickets for help on using tickets.