Proposal: Further performance improvements of Data.Set

[Milan Straka]

Hi,

> Hi,
> 
> 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.

Cheers,
Milan

> 
> 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
> http://www.haskell.org/mailman/listinfo/libraries
>