#4311: Proposal: Further performance improvements of Data.Map
---------------------------------+------------------------------------------
Reporter: milan | Owner:
Type: proposal | Status: new
Priority: normal | Component: libraries (other)
Version: 6.12.3 | Keywords: map, containers
Testcase: | Blockedby: 4277, 4278
Os: Unknown/Multiple | Blocking:
Architecture: Unknown/Multiple | Failure: None/Unknown
---------------------------------+------------------------------------------
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.
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4311>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
