Opened 9 years ago

Closed 9 years ago

#4279 closed proposal (fixed)

Proposal: Performance improvements for Data.IntMap

Reported by: dons Owned by:
Priority: normal Milestone:
Component: libraries/base Version: 6.12.3
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:


Following on from ticket #4277 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.

  1. Add a testsuite, with coverage data (currently 82% 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 relatively clear:

  • 13.3% faster on i7 / x86_64 / Linux
  • 9.95% faster on Mac OS X 10.5 / Xeon / 32 bit

No bugs were identified in the development of the comprehensive testsuite, which includes a large set of unit tests from Kazu Yamamoto


Unlike Data.Map (#4277) 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:

darcs get

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 (1)

_o2-_fregs_graph-is-a-uniform-10_-improvements-for-intmap.dpatch (88.1 KB) - added by dons 9 years ago.

Download all attachments as: .zip

Change History (2)

comment:1 Changed 9 years ago by milan

Resolution: fixed
Status: newclosed

Applied with INLINE => INLINABLE changes.

Note: See TracTickets for help on using tickets.