Proposal: Further performance improvements of Data.Map

This proposal depends on #4277 (closed) and #4278 (closed).

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.

Trac metadata

Trac field	Value
Version	6.12.3
Type	Bug
TypeOfFailure	OtherFailure
Priority	normal
Resolution	Unresolved
Component	libraries (other)
Test case
Differential revisions
BlockedBy	#4277 (closed), #4278 (closed)
Related
Blocking
CC
Operating system
Architecture