[commit: containers] master: Reorder the data constructors of Map and Set. (03a0620)

[Paolo Capriotti]

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

On branch  : master

http://hackage.haskell.org/trac/ghc/changeset/03a0620f8eaf0ad5af4d1f314d5e34842c3b23c3

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

commit 03a0620f8eaf0ad5af4d1f314d5e34842c3b23c3
Author: Milan Straka <fox at ucw.cz>
Date:   Fri Apr 20 18:04:54 2012 +0200

    Reorder the data constructors of Map and Set.
    
    The order of constructors has clearly no effect on corectness.
    
    Inspired by the change in order of constructors of IntMap and IntSet,
    the benchmark shows slight improvement when changing the data
    constructors from Tip | Bin to Bin | Tip.
    
    Also, we now consistently use the same order of constructors in all
    these structures: Map, Set, IntMap, IntSet.

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

 Data/Map/Base.hs |   15 +++++++++++++--
 Data/Set.hs      |   15 +++++++++++++--
 2 files changed, 26 insertions(+), 4 deletions(-)

diff --git a/Data/Map/Base.hs b/Data/Map/Base.hs
index 0185179..bfb24e0 100644
--- a/Data/Map/Base.hs
+++ b/Data/Map/Base.hs
@@ -63,6 +63,15 @@
 -- the Ord dictionary is not passed to 'go' and it is heap-allocated at the
 -- entry of the outer method.
 
+-- [Note: Order of constructors]
+-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+-- The order of constructors of Map matters when considering performance.
+-- Currently in GHC 7.0, when type has 2 constructors, a forward conditional
+-- jump is made when successfully matching second constructor. Successful match
+-- of first constructor results in the forward jump not taken.
+-- On GHC 7.0, reordering constructors from Tip | Bin to Bin | Tip
+-- improves the benchmark by up to 10% on x86.
+
 module Data.Map.Base (
             -- * Map type
               Map(..)          -- instance Eq,Show,Read
@@ -276,8 +285,10 @@ m1 \\ m2 = difference m1 m2
   Size balanced trees.
 --------------------------------------------------------------------}
 -- | A Map from keys @k@ to values @a at .
-data Map k a  = Tip
-              | Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a)
+
+-- See Note: Order of constructors
+data Map k a  = Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a)
+              | Tip
 
 type Size     = Int
 
diff --git a/Data/Set.hs b/Data/Set.hs
index 866e398..d3b89e5 100644
--- a/Data/Set.hs
+++ b/Data/Set.hs
@@ -61,6 +61,15 @@
 -- the Ord dictionary is not passed to 'go' and it is heap-allocated at the
 -- entry of the outer method.
 
+-- [Note: Order of constructors]
+-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+-- The order of constructors of Set matters when considering performance.
+-- Currently in GHC 7.0, when type has 2 constructors, a forward conditional
+-- jump is made when successfully matching second constructor. Successful match
+-- of first constructor results in the forward jump not taken.
+-- On GHC 7.0, reordering constructors from Tip | Bin to Bin | Tip
+-- improves the benchmark by up to 10% on x86.
+
 module Data.Set (
             -- * Strictness properties
             -- $strictness
@@ -196,8 +205,10 @@ m1 \\ m2 = difference m1 m2
   Sets are size balanced trees
 --------------------------------------------------------------------}
 -- | A set of values @a at .
-data Set a    = Tip
-              | Bin {-# UNPACK #-} !Size !a !(Set a) !(Set a)
+
+-- See Note: Order of constructors
+data Set a    = Bin {-# UNPACK #-} !Size !a !(Set a) !(Set a)
+              | Tip
 
 type Size     = Int