Improve programming documentation.
authorMilan Straka <fox@ucw.cz>
Fri, 20 Apr 2012 15:57:35 +0000 (17:57 +0200)
committerMilan Straka <fox@ucw.cz>
Fri, 20 Apr 2012 16:16:39 +0000 (18:16 +0200)
Move important programming comments to the beginning of the source file,
give them names and refer to the from the source code where necessarry.

Data/IntMap/Base.hs
Data/IntMap/Strict.hs
Data/IntSet.hs
Data/Map/Base.hs
Data/Map/Strict.hs
Data/Set.hs

index bf0fa0e..6f30a7d 100644 (file)
 -- on representations.
 -----------------------------------------------------------------------------
 
+-- [Note: INLINE bit fiddling]
+-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^
 -- It is essential that the bit fiddling functions like mask, zero, branchMask
 -- etc are inlined. If they do not, the memory allocation skyrockets. The GHC
 -- usually gets it right, but it is disastrous if it does not. Therefore we
 -- explicitly mark these functions INLINE.
 
+-- [Note: Local 'go' functions and capturing]
+-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+-- Care must be taken when using 'go' function which captures an argument.
+-- Sometimes (for example when the argument is passed to a data constructor,
+-- as in insert), GHC heap-allocates more than necessary. Therefore C-- code
+-- must be checked for increased allocation when creating and modifying such
+-- functions.
+
+-- [Note: Order of constructors]
+-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+-- 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 benchmark by circa 10%.
+
 module Data.IntMap.Base (
             -- * Map type
               IntMap(..), Key          -- instance Eq,Show
@@ -239,14 +258,10 @@ shiftRL x i   = shiftR x i
   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@.
+
+-- See Note: Order of constructors
 data IntMap a = Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask !(IntMap a) !(IntMap a)
               | Tip {-# UNPACK #-} !Key a
               | Nil
@@ -790,7 +805,7 @@ intersectionWithKey f m1 m2
 --   the output is added to the result.
 --
 -- The @only1@ and @only2@ methods /must return a map with a subset (possibly empty) of the keys of the given map/.
--- The values can be modified arbitrarily.  Most common variants of @only1@ and
+-- The values can be modified arbitrarily. Most common variants of @only1@ and
 -- @only2@ are 'id' and @'const' 'empty'@, but for example @'map' f@ or
 -- @'filterWithKey' f@ could be used for any @f@.
 
index 144e20b..901d769 100644 (file)
@@ -53,6 +53,8 @@
 -- on strict maps, the resulting maps will be lazy.
 -----------------------------------------------------------------------------
 
+-- See the notes at the beginning of Data.IntMap.Base.
+
 module Data.IntMap.Strict (
             -- * Strictness properties
             -- $strictness
index 5596e1b..486353a 100644 (file)
 -- (32 or 64).
 -----------------------------------------------------------------------------
 
+-- [Note: INLINE bit fiddling]
+-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^
 -- It is essential that the bit fiddling functions like mask, zero, branchMask
 -- etc are inlined. If they do not, the memory allocation skyrockets. The GHC
 -- usually gets it right, but it is disastrous if it does not. Therefore we
 -- explicitly mark these functions INLINE.
 
+-- [Note: Local 'go' functions and capturing]
+-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+-- Care must be taken when using 'go' function which captures an argument.
+-- Sometimes (for example when the argument is passed to a data constructor,
+-- as in insert), GHC heap-allocates more than necessary. Therefore C-- code
+-- must be checked for increased allocation when creating and modifying such
+-- functions.
+
+-- [Note: Order of constructors]
+-- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+-- 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 benchmark by circa 10%.
+
 module Data.IntSet (
             -- * Strictness properties
             -- $strictness
@@ -219,14 +238,9 @@ 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.
+
+-- See Note: Order of constructors
 data IntSet = Bin {-# UNPACK #-} !Prefix {-# UNPACK #-} !Mask !IntSet !IntSet
 -- 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
@@ -288,20 +302,8 @@ size t
       Tip _ bm -> bitcount 0 bm
       Nil   -> 0
 
--- The 'go' function in the member causes 10% speedup, but also an
--- increased memory allocation. It does not cause speedup with other methods
--- like insert and delete, so it is present only in member.
-
--- Also mind the 'nomatch' line in member definition, which is not present in
--- IntMap.hs. That condition stops the search if the prefix of current vertex
--- is different that the element looked for. The member is correct both with
--- and without this condition. With this condition, elements not present are
--- rejected sooner, but a little bit more work is done for the elements in the
--- set (we are talking about 3-5% slowdown). Any of the solutions is better
--- than the other, because we do not know the distribution of input data.
--- Current state is historic.
-
 -- | /O(min(n,W))/. Is the value a member of the set?
+
 member :: Int -> IntSet -> Bool
 member x = x `seq` go
   where
index 95d3972..0185179 100644 (file)
 -- the Big-O notation <http://en.wikipedia.org/wiki/Big_O_notation>.
 -----------------------------------------------------------------------------
 
+-- [Note: Using INLINABLE]
+-- ^^^^^^^^^^^^^^^^^^^^^^^
 -- It is crucial to the performance that the functions specialize on the Ord
 -- type when possible. GHC 7.0 and higher does this by itself when it sees th
 -- unfolding of a function -- that is why all public functions are marked
 -- INLINABLE (that exposes the unfolding).
---
+
+-- [Note: Using INLINE]
+-- ^^^^^^^^^^^^^^^^^^^^
 -- For other compilers and GHC pre 7.0, we mark some of the functions INLINE.
 -- We mark the functions that just navigate down the tree (lookup, insert,
 -- delete and similar). That navigation code gets inlined and thus specialized
 -- therefore only the tree navigation, all the real work (rebalancing) is not
 -- INLINED by using a NOINLINE.
 --
--- All methods that can be INLINE are not recursive -- a 'go' function doing
--- the real work is provided.
+-- All methods marked INLINE have to be nonrecursive -- a 'go' function doing
+-- the real work is provided. Curiously, it has to be given a type. Otherwise
+-- the Ord dictionary is not passed to 'go' and it is heap-allocated at the
+-- entry of the outer method.
 
 module Data.Map.Base (
             -- * Map type
index f8ffc5e..4d722ff 100644 (file)
 -- on strict maps, the resulting maps will be lazy.
 -----------------------------------------------------------------------------
 
--- It is crucial to the performance that the functions specialize on the Ord
--- type when possible. GHC 7.0 and higher does this by itself when it sees th
--- unfolding of a function -- that is why all public functions are marked
--- INLINABLE (that exposes the unfolding).
---
--- For other compilers and GHC pre 7.0, we mark some of the functions INLINE.
--- We mark the functions that just navigate down the tree (lookup, insert,
--- delete and similar). That navigation code gets inlined and thus specialized
--- when possible. There is a price to pay -- code growth. The code INLINED is
--- therefore only the tree navigation, all the real work (rebalancing) is not
--- INLINED by using a NOINLINE.
---
--- All methods that can be INLINE are not recursive -- a 'go' function doing
--- the real work is provided.
+-- See the notes at the beginning of Data.IntMap.Base.
 
 module Data.Map.Strict
     (
index 529c612..866e398 100644 (file)
 -- equality.
 -----------------------------------------------------------------------------
 
+-- [Note: Using INLINABLE]
+-- ^^^^^^^^^^^^^^^^^^^^^^^
 -- It is crucial to the performance that the functions specialize on the Ord
 -- type when possible. GHC 7.0 and higher does this by itself when it sees th
 -- unfolding of a function -- that is why all public functions are marked
 -- INLINABLE (that exposes the unfolding).
---
+
+-- [Note: Using INLINE]
+-- ^^^^^^^^^^^^^^^^^^^^
 -- For other compilers and GHC pre 7.0, we mark some of the functions INLINE.
 -- We mark the functions that just navigate down the tree (lookup, insert,
 -- delete and similar). That navigation code gets inlined and thus specialized
 -- therefore only the tree navigation, all the real work (rebalancing) is not
 -- INLINED by using a NOINLINE.
 --
--- All methods that can be INLINE are not recursive -- a 'go' function doing
--- the real work is provided.
+-- All methods marked INLINE have to be nonrecursive -- a 'go' function doing
+-- the real work is provided. Curiously, it has to be given a type. Otherwise
+-- the Ord dictionary is not passed to 'go' and it is heap-allocated at the
+-- entry of the outer method.
 
 module Data.Set (
             -- * Strictness properties