Commits

Bryan O'Sullivan  committed e665573

Measure and improve replicate.

  • Participants
  • Parent commits a634bc2

Comments (0)

Files changed (4)

File Data/Text.hs

 import Prelude (Char, Bool(..), Functor(..), Int, Maybe(..), String,
                 Eq(..), Ord(..), (++),
                 Read(..), Show(..),
-                (&&), (||), (+), (-), (.), ($), (>>),
-                fromIntegral, div, not, return, otherwise)
+                (&&), (||), (+), (-), (.), ($), (>>), (*),
+                div, not, return, otherwise)
 import Control.DeepSeq (NFData)
 import Control.Exception (assert)
 import Data.Char (isSpace)
 -- ** Generating and unfolding 'Text's
 
 -- | /O(n*m)/ 'replicate' @n@ @t@ is a 'Text' consisting of the input
--- @t@ repeated @n@ times. Subject to fusion.
+-- @t@ repeated @n@ times.
 replicate :: Int -> Text -> Text
-replicate n t
-    | isSingleton t = replicateChar n (unsafeHead t)
-    | otherwise     = unstream (S.replicateI (fromIntegral n) (S.stream t))
+replicate n t@(Text a o l)
+    | n <= 0 || l <= 0 = empty
+    | n == 1           = t
+    | isSingleton t    = replicateChar n (unsafeHead t)
+    | otherwise        = Text (A.run x) 0 len
+  where
+    len = l * n
+    x = do
+      arr <- A.unsafeNew len
+      let loop !d !i | i >= n    = return arr
+                     | otherwise = let m = d + l
+                                   in copy arr d a o m >> loop m (i+1)
+      loop 0 0
 {-# INLINE [1] replicate #-}
 
 {-# RULES

File Data/Text/Fusion/Common.hs

            | otherwise = Yield c (i + 1)
 {-# INLINE [0] replicateCharI #-}
 
+data RI s = RI !s {-# UNPACK #-} !Int64
+
 replicateI :: Int64 -> Stream Char -> Stream Char
 replicateI n (Stream next0 s0 len) =
-    Stream next (0 :*: s0) (fromIntegral (max 0 n) * len)
+    Stream next (RI s0 0) (fromIntegral (max 0 n) * len)
   where
-    next (k :*: s)
+    next (RI s k)
         | k >= n = Done
         | otherwise = case next0 s of
-                        Done       -> Skip    (k+1 :*: s0)
-                        Skip s'    -> Skip    (k :*: s')
-                        Yield x s' -> Yield x (k :*: s')
+                        Done       -> Skip    (RI s0 (k+1))
+                        Skip s'    -> Skip    (RI s' k)
+                        Yield x s' -> Yield x (RI s' k)
 {-# INLINE [0] replicateI #-}
 
 -- | /O(n)/, where @n@ is the length of the result. The unfoldr function

File Data/Text/Lazy.hs

                               (s', ys) = mapAccumR f s xs
 
 -- | /O(n*m)/ 'replicate' @n@ @t@ is a 'Text' consisting of the input
--- @t@ repeated @n@ times. Subject to fusion.
+-- @t@ repeated @n@ times.
 replicate :: Int64 -> Text -> Text
-replicate n t
-    | isSingleton t = replicateChar n (head t)
-    | otherwise     = unstream (S.replicateI n (S.stream t))
+replicate n t = concat (rep 0)
+    where rep i | i >= n    = []
+                | otherwise = t : rep (i+1)
 {-# INLINE replicate #-}
 
 -- | /O(n)/ 'replicateChar' @n@ @c@ is a 'Text' of length @n@ with @c@ the

File tests/Benchmarks.hs

       , bench "bl" $ nf (BL.map f . BL.map f) bla
       , bench "l" $ nf (L.map f . L.map f) la
       ],
+      bgroup "replicate" [
+        bench "ts" $ nf (TS.replicate bsa_len) (TS.singleton c)
+      , bench "tl" $ nf (TL.replicate (fromIntegral bsa_len)) (TL.singleton c)
+      , bench "bs" $ nf (BS.replicate bsa_len) c
+      , bench "bl" $ nf (BL.replicate (fromIntegral bsa_len)) c
+      , bench "l" $ nf (L.replicate bsa_len) c
+      ],
+      bgroup "2replicate" [
+        bench "ts" $ nf (TS.replicate (bsa_len `div` TS.length tsw)) tsw
+      , bench "tl" $ nf (TL.replicate (fromIntegral bsa_len `div` TL.length tlw)) tlw
+      , bench "l" $ nf (replicat (bsa_len `div` TS.length tsw)) lw
+      ],
       bgroup "reverse" [
         bench "ts" $ nf TS.reverse tsa
       , bench "tl" $ nf TL.reverse tla
         , bench "bs" $ nf (BS.length . BS.map f . BS.map f) bsa
         , bench "l" $ nf (L.length . L.map f . L.map f) la
         ],
+        bgroup "replicate" [
+          bench "ts" $ nf (TS.length . TS.replicate bsa_len) (TS.singleton c)
+        , bench "tl" $ nf (TL.length . TL.replicate (fromIntegral bsa_len)) (TL.singleton c)
+        , bench "bs" $ nf (BS.length . BS.replicate bsa_len) c
+        , bench "bl" $ nf (BL.length . BL.replicate (fromIntegral bsa_len)) c
+        , bench "l" $ nf (L.length . L.replicate bsa_len) c
+        ],
+        bgroup "2replicate" [
+          bench "ts" $ nf (TS.length . TS.replicate (bsa_len `div` TS.length tsw)) tsw
+        , bench "tl" $ nf (TL.length . TL.replicate (fromIntegral bsa_len `div` TL.length tlw)) tlw
+        , bench "l" $ nf (L.length . replicat (bsa_len `div` TS.length tsw)) lw
+        ],
         bgroup "take" [
           bench "ts" $ nf (TS.length . TS.take (tsa_len `div` 3)) tsa
         , bench "tl" $ nf (TL.length . TL.take (tla_len `div` 3)) tla
     tlw  = TL.fromChunks [tsw]
     f (C# c#) = C# (chr# (ord# c# +# 1#))
     len l _ = l + (1::Int)
+    replicat n = concat . L.replicate n
 
 chunksOf :: Int -> BS.ByteString -> [BS.ByteString]
 chunksOf k = go