Proposal: Further performance improvements of Data.Map
fox at ucw.cz
Tue Sep 14 12:28:58 EDT 2010
The following text is the description of ticket 4311:
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 modifying 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
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.
More information about the Libraries