Opened 4 years ago

Closed 4 years ago

#4311 closed proposal (fixed)

Proposal: Further performance improvements of Data.Map

Reported by: milan Owned by:
Priority: normal Milestone:
Component: libraries (other) Version: 6.12.3
Keywords: map, containers Cc: johan.tibell@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Difficulty:
Test Case: Blocked By: #4277
Blocking: Related Tickets:

Description

This proposal depends on #4277 and #4278.

This proposal further improves the performance of Data.Map. It consists of four patches:

  1. improvements to union and difference implementation( by eliminating high-order function)
  2. improvements to balance function which is used by nearly all methods modificating a map (making one monolithic function which allows perform only one pattern-match on the tree nodes)
  3. correction of the test (the Arbitrary instance could generate unbalanced trees, which the patch 2. discovered)
  4. added benchmark of union, difference and intersection methods

On i386 Intel Core2 and GHC 6.12.1, the improvements are

alter                       5.61
delete                      10.80
difference                  20.33
insert                      8.09
intersection                7.69
union                       21.74
update                      7.96

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.

Attachments (2)

containers-map-improvements.patch (31.0 KB) - added by milan 4 years ago.
containers-map-improvements-2.patch (45.9 KB) - added by milan 4 years ago.

Download all attachments as: .zip

Change History (10)

Changed 4 years ago by milan

comment:1 follow-up: Changed 4 years ago by tibbe

+1

Please also list the API changes you made; I see you added some functions.

comment:2 Changed 4 years ago by tibbe

  • Cc johan.tibell@… added

comment:3 in reply to: ↑ 1 Changed 4 years ago by milan

Replying to tibbe:

Please also list the API changes you made; I see you added some functions.

I did not do any API changes. The only visible effect is a speedup :)

comment:4 follow-up: Changed 4 years ago by tibbe

I did a diff on your whole repo and I saw some foldl' and foldr functions being added. Perhaps those changes aren't part of this proposal.

comment:5 in reply to: ↑ 4 Changed 4 years ago by milan

Replying to tibbe:

I did a diff on your whole repo and I saw some foldl' and foldr functions being added. Perhaps those changes aren't part of this proposal.

The repo contains patches for #4311, #4312 and #4313. Sorry for confusion :)

comment:6 Changed 4 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:

alter                       1.43%
delete                      11.11%
difference                  20.28%
insert                      32.69%
intersection                11.12%
union                       18.82%
update                      11.68%

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

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

Changed 4 years ago by milan

comment:7 Changed 4 years ago by milan

  • Blocked By 4278 removed

This patch is no longer blocked by #4278.

comment:8 Changed 4 years ago by milan

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

Applied.

Note: See TracTickets for help on using tickets.