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