Proposal: Further performance improvements of Data.Set
fox at ucw.cz
Tue Sep 14 12:36:43 EDT 2010
> see http://hackage.haskell.org/trac/ghc/ticket/4312.
> The following text is the description of ticket 4312:
> 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 modifying 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
As in Data.Map, the improvements are in % and were measured with the
benchmark, which is part of the patches.
> 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)
> Libraries mailing list
> Libraries at haskell.org
More information about the Libraries