Opened 9 years ago

Closed 9 years ago

#4312 closed task (fixed)

Proposal: Further performance improvements of Data.Set

Reported by: milan Owned by:
Priority: normal Milestone:
Component: libraries (other) Version: 6.12.3
Keywords: set, containers Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: #4280 Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

This proposal depends on #4280.

This proposal further improves the performance of Data.Set. It consists of five patches:

  1. making the set datatype to store the elements evaluated (by using a bang). This is in accordance with a poll on libraries@…, see point 1) of http://article.gmane.org/gmane.comp.lang.haskell.libraries/13273
  2. improvements to union and difference implementation (by eliminating high-order function)
  3. improvements to balance function which is used by nearly all methods modificating a set (making one monolithic function which allows perform only one pattern-match on the tree nodes)
  4. correction of the test (the Arbitrary instance could generate unbalanced trees, which the patch 3. discovered)
  5. added benchmark of union, difference and intersection methods

On i386 Intel Core2 and GHC 6.12.1, the improvements are

delete       13.46
deleteMax    13.58
deleteMin    15.93
difference   26.17
insert       12.20
intersection 2.21
member       9.52
union        27.59

The repository of the containers package with these patches (and also several others) is at http://fox.auryn.cz/darcs/containers/.

The patches are also attached (including #4280, which are not commited yet).

Attachments (2)

containers-set-improvements.patch (52.9 KB) - added by milan 9 years ago.
containers-set-improvements-2.patch (63.9 KB) - added by milan 9 years ago.

Download all attachments as: .zip

Change History (4)

Changed 9 years ago by milan

comment:1 Changed 9 years ago by milan

A new version of a patch, which beside others incorporates suggestion by Kazu Yamamoto.

The current improvements on I386, GHC 6.12.1 are:

delete       15.01%
deleteMax    19.18%
deleteMin    18.43%
difference   23.95%
insert       35.38%
intersection 4.52%
member       9.63%
union        27.25

These improvements are measured by benchmark in the repository, and are in % with respect to the version without the #4312 patch.

The repository has been updated, and new patch is also attached.

Changed 9 years ago by milan

comment:2 Changed 9 years ago by milan

Resolution: fixed
Status: newclosed

Applied.

Note: See TracTickets for help on using tickets.