[commit: containers] master: Reordering data constructors of IntSet and IntMap. (73d073d)

[Ian Lynagh]

Repository : ssh://darcs.haskell.org//srv/darcs/packages/containers

On branch  : master

http://hackage.haskell.org/trac/ghc/changeset/73d073d8594acf3a355d040569677fef35f2cf21

>---------------------------------------------------------------

commit 73d073d8594acf3a355d040569677fef35f2cf21
Author: Milan Straka <fox at ucw.cz>
Date:   Tue Jul 12 14:22:17 2011 +0200

    Reordering data constructors of IntSet and IntMap.
    
    The order of constructors of IntSet and IntMap matters when considering
    performance.  Currently in GHC 7.0, when type has 3 constructors, they
    are matched from the first to the last -- the best performance is
    achieved when the constructors are ordered by frequency.
    
    On GHC 7.0, reordering constructors from Nil | Tip | Bin to Bin | Tip | Nil
    improves the containers_benchmark
    - by 9.5% on x86 and by 8% on x86_64 for IntMap
    - by 11% on x86 and by 9% on x86_64 for IntSet
    The performance should never decrease for any architecture.

>---------------------------------------------------------------

 Data/IntMap.hs |   12 ++++++++++--
 Data/IntSet.hs |   12 ++++++++++--
 2 files changed, 20 insertions(+), 4 deletions(-)

diff --git a/Data/IntMap.hs b/Data/IntMap.hs
index fe0b353..9016b37 100644
--- a/Data/IntMap.hs
+++ b/Data/IntMap.hs
@@ -250,10 +250,18 @@ m1 \\ m2 = difference m1 m2
 {--------------------------------------------------------------------
   Types  
 --------------------------------------------------------------------}
+
+-- The order of constructors of IntMap matters when considering performance.
+-- Currently in GHC 7.0, when type has 3 constructors, they are matched from
+-- the first to the last -- the best performance is achieved when the
+-- constructors are ordered by frequency.
+-- On GHC 7.0, reordering constructors from Nil | Tip | Bin to Bin | Tip | Nil
+-- improves the containers_benchmark by 9.5% on x86 and by 8% on x86_64.
+
 -- | A map of integers to values @a at .
-data IntMap a = Nil
+data IntMap a = Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask !(IntMap a) !(IntMap a)
               | Tip {-# UNPACK #-} !Key a
-              | Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask !(IntMap a) !(IntMap a) 
+              | Nil
 
 type Prefix = Int
 type Mask   = Int
diff --git a/Data/IntSet.hs b/Data/IntSet.hs
index bcc5104..d513a1a 100644
--- a/Data/IntSet.hs
+++ b/Data/IntSet.hs
@@ -174,10 +174,18 @@ m1 \\ m2 = difference m1 m2
 {--------------------------------------------------------------------
   Types  
 --------------------------------------------------------------------}
+
+-- The order of constructors of IntSet matters when considering performance.
+-- Currently in GHC 7.0, when type has 3 constructors, they are matched from
+-- the first to the last -- the best performance is achieved when the
+-- constructors are ordered by frequency.
+-- On GHC 7.0, reordering constructors from Nil | Tip | Bin to Bin | Tip | Nil
+-- improves the containers_benchmark by 11% on x86 and by 9% on x86_64.
+
 -- | A set of integers.
-data IntSet = Nil
+data IntSet = Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask !IntSet !IntSet
             | Tip {-# UNPACK #-} !Int
-            | Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask !IntSet !IntSet
+            | Nil
 -- Invariant: Nil is never found as a child of Bin.
 -- Invariant: The Mask is a power of 2.  It is the largest bit position at which
 --            two elements of the set differ.