[Haskell-cafe] appending an element to a list

[Derek Elkins]

On Wed, 2008-06-11 at 17:18 -0700, Evan Laforge wrote:
> > Lets look at the actual reductions going on. To make the example easier,
> > I would like to use last instead of your complicated until. It shouldn't
> > make a difference.
> 
> [ winds up doing twice as much work ]
> 
> This was also my intuition.  I had a function that built up a large
> output list by generating chunks and ++ them onto the output (e.g.
> basically concatMap).  My intuition was that this would get gradually
> slower because each (++) implied a copy of the previous part of the
> list.  So if I have another function consuming the eventual output it
> will get slower and slower because demanding an element will reduce
> the (++)s for each chunk, and copy the element 1000 times if I have
> appended 1000 chunks by now.
> 
> So I switched to using DList, which has O(1) append.  Then I ran
> timing on a list that wound up adding up a million or so chunks... and
> both versions were exactly the same speed (and -O2 gave both an
> equally big speed boost).
> 
> In fact, when I try with a toy example, the DList using one is much
> slower than the concatMap using one, which I don't quite understand.
> Shouldn't concatMap be quite inefficient?

concatMap is very efficient.  (++) isn't slow.  Left associative uses of
(++) are slow.  concatMap = foldr ((++) . f) []

> 
> The program below gives me this output:
> 
> 15000000
> 45.7416
> 15000000
> 110.2112
> 
> -O2 brings both implementations to 45.
> 
> Interestingly, if I call 't1' from ghci, it sucks up 1gb of memory and
> slows the system to a crawl until I kill it.. this is *after* it's
> computed a result and given me my prompt back... even if its somehow
> keeping the whole list around in some ghci variable (where?), isn't
> 1gb+ a lot even for 15m boxed Integers?  And why does it continue to
> grow after the function has completed?  The compiled version doesn't
> have this problem.
> 
> 
> import System.CPUTime
> import qualified Data.DList as DList
> 
> dconcat_map f xs = DList.toList (DList.concat (map (DList.fromList . f) xs))
> 
> mkchunk n = [n, n*2, n*3]
> 
> main = do
>     t1
>     t2
> 
> t1 = do
>     let a = concatMap mkchunk [0..5000000]
>     t <- getCPUTime
>     print (last a)
>     t2 <- getCPUTime
>     print (fromIntegral (t2 - t) / fromIntegral cpuTimePrecision)
> 
> t2 = do
>     let a = dconcat_map mkchunk [0..5000000]
>     t <- getCPUTime
>     print (last a)
>     t2 <- getCPUTime
>     print (fromIntegral (t2 - t) / fromIntegral cpuTimePrecision)
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe