Ticket #3586: faster-newArray-for-STU.dpatch

Wed Oct 14 19:52:09 CEST 2009  Bertram Felgenhauer <int-e@gmx.de>
  * Fix newArray performance (#3586)
  newArray wasn't getting inlined, and thus not specialized for STUArray types.

Wed Oct 14 20:01:24 CEST 2009  Bertram Felgenhauer <int-e@gmx.de>
  * use forM_ rather than sequence_ (related to #3586)
  It turns out that forM_ [0 .. n - 1] f  produces faster code than
  sequence_ [f i | i <- [0 .. n - 1]].


New patches:

[Fix newArray performance (#3586)
Bertram Felgenhauer <int-e@gmx.de>**20091014175209
 Ignore-this: 335a897b5de209bdcd2932931eefd7cb
 newArray wasn't getting inlined, and thus not specialized for STUArray types.
] {
hunk ./Data/Array/Base.hs 963
        -- The INLINE is crucial, because until we know at least which monad    
        -- we are in, the code below allocates like crazy.  So inline it,
        -- in the hope that the context will know the monad.
-    newArray (l,u) initialValue = do
-        let n = safeRangeSize (l,u)
-        marr <- unsafeNewArray_ (l,u)
-        sequence_ [unsafeWrite marr i initialValue | i <- [0 .. n - 1]]
-        return marr
+    newArray = newArrayImpl
 
     {-# INLINE unsafeNewArray_ #-}
     unsafeNewArray_ (l,u) = newArray (l,u) arrEleBottom
hunk ./Data/Array/Base.hs 986
     -- default initialisation with undefined values if we *do* know the
     -- initial value and it is constant for all elements.
 
+{-# INLINE newArrayImpl #-}
+newArrayImpl (l,u) initialValue = do
+        let n = safeRangeSize (l,u)
+        marr <- unsafeNewArray_ (l,u)
+        sequence_ [unsafeWrite marr i initialValue | i <- [0 .. n - 1]]
+        return marr
+
 instance MArray IOArray e IO where
 #if defined(__HUGS__)
     getBounds   = return . boundsIOArray
}
[use forM_ rather than sequence_ (related to #3586)
Bertram Felgenhauer <int-e@gmx.de>**20091014180124
 Ignore-this: 21e270df88eb12abb3cd856fa0126a1
 It turns out that forM_ [0 .. n - 1] f  produces faster code than
 sequence_ [f i | i <- [0 .. n - 1]].
] {
hunk ./Data/Array/Base.hs 30
 
 import Control.Monad.ST.Lazy ( strictToLazyST )
 import qualified Control.Monad.ST.Lazy as Lazy (ST)
+import Control.Monad ( forM_ )
 import Data.Ix ( Ix, range, index, rangeSize )
 import Foreign.C.Types
 import Foreign.StablePtr
hunk ./Data/Array/Base.hs 115
 unsafeReplaceST :: (IArray a e, Ix i) => a i e -> [(Int, e)] -> ST s (STArray s i e)
 unsafeReplaceST arr ies = do
     marr <- thaw arr
-    sequence_ [unsafeWrite marr i e | (i, e) <- ies]
+    forM_ ies $ \ (i, e) -> unsafeWrite marr i e
     return marr
 
 {-# INLINE unsafeAccumST #-}
hunk ./Data/Array/Base.hs 122
 unsafeAccumST :: (IArray a e, Ix i) => (e -> e' -> e) -> a i e -> [(Int, e')] -> ST s (STArray s i e)
 unsafeAccumST f arr ies = do
     marr <- thaw arr
-    sequence_ [do
+    forM_ ies $ \ (i, new) -> do
         old <- unsafeRead marr i
         unsafeWrite marr i (f old new)
hunk ./Data/Array/Base.hs 125
-        | (i, new) <- ies]
     return marr
 
 {-# INLINE unsafeAccumArrayST #-}
hunk ./Data/Array/Base.hs 131
 unsafeAccumArrayST :: Ix i => (e -> e' -> e) -> e -> (i,i) -> [(Int, e')] -> ST s (STArray s i e)
 unsafeAccumArrayST f e (l,u) ies = do
     marr <- newArray (l,u) e
-    sequence_ [do
+    forM_ ies $ \ (i, new) -> do
         old <- unsafeRead marr i
         unsafeWrite marr i (f old new)
hunk ./Data/Array/Base.hs 134
-        | (i, new) <- ies]
     return marr
 
 
hunk ./Data/Array/Base.hs 443
                   => (i,i) -> [(Int, e)] -> e -> ST s (UArray i e)
 unsafeArrayUArray (l,u) ies default_elem = do
     marr <- newArray (l,u) default_elem
-    sequence_ [unsafeWrite marr i e | (i, e) <- ies]
+    forM_ ies $ \ (i, e) -> unsafeWrite marr i e
     unsafeFreezeSTUArray marr
 
 {-# INLINE unsafeFreezeSTUArray #-}
hunk ./Data/Array/Base.hs 463
                     => UArray i e -> [(Int, e)] -> ST s (UArray i e)
 unsafeReplaceUArray arr ies = do
     marr <- thawSTUArray arr
-    sequence_ [unsafeWrite marr i e | (i, e) <- ies]
+    forM_ ies $ \ (i, e) -> unsafeWrite marr i e
     unsafeFreezeSTUArray marr
 
 {-# INLINE unsafeAccumUArray #-}
hunk ./Data/Array/Base.hs 471
                   => (e -> e' -> e) -> UArray i e -> [(Int, e')] -> ST s (UArray i e)
 unsafeAccumUArray f arr ies = do
     marr <- thawSTUArray arr
-    sequence_ [do
+    forM_ ies $ \ (i, new) -> do
         old <- unsafeRead marr i
         unsafeWrite marr i (f old new)
hunk ./Data/Array/Base.hs 474
-        | (i, new) <- ies]
     unsafeFreezeSTUArray marr
 
 {-# INLINE unsafeAccumArrayUArray #-}
hunk ./Data/Array/Base.hs 481
                        => (e -> e' -> e) -> e -> (i,i) -> [(Int, e')] -> ST s (UArray i e)
 unsafeAccumArrayUArray f initialValue (l,u) ies = do
     marr <- newArray (l,u) initialValue
-    sequence_ [do
+    forM_ ies $ \ (i, new) -> do
         old <- unsafeRead marr i
         unsafeWrite marr i (f old new)
hunk ./Data/Array/Base.hs 484
-        | (i, new) <- ies]
     unsafeFreezeSTUArray marr
 
 {-# INLINE eqUArray #-}
hunk ./Data/Array/Base.hs 987
 newArrayImpl (l,u) initialValue = do
         let n = safeRangeSize (l,u)
         marr <- unsafeNewArray_ (l,u)
-        sequence_ [unsafeWrite marr i initialValue | i <- [0 .. n - 1]]
+        forM_ [0 .. n - 1] $ \ i -> unsafeWrite marr i initialValue
         return marr
 
 instance MArray IOArray e IO where
hunk ./Data/Array/Base.hs 1061
   (l,u) <- getBounds marr
   n <- getNumElements marr
   marr' <- newArray_ (l,u)
-  sequence_ [do
+  forM_ [0 .. n - 1] $ \ i -> do
         e <- unsafeRead marr i
         unsafeWrite marr' i (f e)
hunk ./Data/Array/Base.hs 1064
-        | i <- [0 .. n - 1]]
   return marr'
 
 {-# INLINE mapIndices #-}
hunk ./Data/Array/Base.hs 1073
 mapIndices (l',u') f marr = do
     marr' <- newArray_ (l',u')
     n' <- getNumElements marr'
-    sequence_ [do
+    forM_ (range (l',u')) $ \ i' -> do
         e <- readArray marr (f i')
         unsafeWrite marr' (safeIndex (l',u') n' i') e
hunk ./Data/Array/Base.hs 1076
-        | i' <- range (l',u')]
     return marr'
 
 -----------------------------------------------------------------------------
hunk ./Data/Array/Base.hs 1778
   (l,u) -> do
     marr <- newArray_ (l,u)
     let n = safeRangeSize (l,u)
-    sequence_ [ unsafeWrite marr i (unsafeAt arr i)
-              | i <- [0 .. n - 1]]
+    forM_ [0 .. n - 1] $ \ i -> unsafeWrite marr i (unsafeAt arr i)
     return marr
 
 thawSTUArray :: Ix i => UArray i e -> ST s (STUArray s i e)
}

Context:

[TAG GHC 6.10.4 release
Ian Lynagh <igloo@earth.li>**20090719123606] 
[TAG GHC 6.10.2 release
Ian Lynagh <igloo@earth.li>**20090401221746] 
[TAG array 0.2.0.0
Ian Lynagh <igloo@earth.li>**20081212141719] 
[TAG GHC 6.10.1 release
Ian Lynagh <igloo@earth.li>**20081107191823] 
[Point the reader of the Data.Array docs in the direction of GHC.Arr
Ian Lynagh <igloo@earth.li>**20081013172536] 
[remove unnecessary Data.Generics.* imports
'Jose Pedro Magalhaes <jpm@cs.uu.nl>'**20081002082411] 
[Bump version number to 0.2.0.0
Ian Lynagh <igloo@earth.li>**20080920155739] 
[TAG 6.10 branch has been forked
Ian Lynagh <igloo@earth.li>**20080919123437] 
[TAG GHC 6.10 fork
Ian Lynagh <igloo@earth.li>**20080919004905] 
Patch bundle hash:
cc749a0dd6e36bb871a6957a4a7b79ab58a994a7