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 <[email protected]> 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@. -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@. -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 _______________________________________________ Cvs-libraries mailing list [email protected] http://www.haskell.org/mailman/listinfo/cvs-libraries
