Apparently it doesn't, and it seems to be fixed now.

Does anyone know what exactly the bug was? Because this seems like a serious bug to me. I've run into it myself today and wasn't happy. Linear algorithms should work in linear time however much memory they allocate (modulo cache thrashing of course). Existence of people claiming otherwise surprises me! On 22 September 2011 01:05, John Lato wrote:

On Wed, Sep 21, 2011 at 1:57 PM, Tim Docker wrote:

...

On 09/09/2011, at 8:19 PM, John Lato wrote:

...

Agreed.  Whenever I'd like to use mapM (or any other function for which a *M_ is available), I've found the following rules helpful:

1.  If I can guarantee the list is short (~ n<=20), go ahead and use mapM 2.  Otherwise use mapM_, foldM_, or foldM if a real reduction is possible (i.e. not "foldM snocM []").

Step 2 sometimes requires changing my design, but it's always been for the better.  `mapM_` tends to require more pipeline composition, so it's leveraging the language's strengths.

This thread is really interesting - it relates directly to problems I am currently having with mapM over large lists (see the thread "stack overflow pain").

Can you explain what you mean by "mapM_ tends to require more pipeline composition"? In what way is it leveraging the language strengths?

Hmm, that is suitably cryptic.  One way to think of it is an inversion of control.  Instead of operating on whole collections of things in a monad, you specify monadic actions (pipelines) which are applied sequentially to each input.

Here's a simple example.  Suppose you have a bunch of data serialized to files, and you want to read each file into a data structure, apply some process based upon the last file's data, and write out the output to new files.  One way to do that would look like:

do    dats <- mapM readMyData files    let pairs = zip (mempty:dats) dats    zipWithM_ (\(last, this) fname -> writeMyData (update last this) fname) pairs newFiles

However, you could also put everything into a single monadic operation, like this

do    foldM_ (\last (infile, outfile) -> do                                                    this <- readMyData infile                                                    writeMyData (update last this) outfile                                                    return this               )               mempty               (zip files newFiles)

The first interleaves control (mapM, zipWIthM_) with monadic actions (file IO), whereas the second only has one control function (foldM_) which completely processes one input.  I say this is more pipeline composition because you have to create an entire pipeline from input to output, which is then sequentially fed inputs by the control function.

I say this leverages Haskell's strengths because it's quite easy to compose functions and monadic actions in Haskell.  It also tends to be garbage-collector friendly.  I also find it much easier to reason about space usage.  You don't need to worry if part of a list is being retained, because the full list of data doesn't appear anywhere.  If you need to access prior elements they're specified explicitly so you know exactly how much data you're holding on to.

My perspective might be warped by my work on iteratees, but I find this a very natural approach.

John L.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Garbage collection takes amortized O(1) per allocation, doesn't it? On 26 September 2011 18:00, Lennart Augustsson wrote:

You seem to ignore garbage collection.

On Sat, Sep 24, 2011 at 6:40 AM, Arseniy Alekseyev wrote:

...

...

Apparently it doesn't, and it seems to be fixed now.

Does anyone know what exactly the bug was? Because this seems like a serious bug to me. I've run into it myself today and wasn't happy. Linear algorithms should work in linear time however much memory they allocate (modulo cache thrashing of course). Existence of people claiming otherwise surprises me!

On 22 September 2011 01:05, John Lato wrote:

...

On Wed, Sep 21, 2011 at 1:57 PM, Tim Docker wrote:

...

On 09/09/2011, at 8:19 PM, John Lato wrote:

...

Agreed.  Whenever I'd like to use mapM (or any other function for which a *M_ is available), I've found the following rules helpful:

1.  If I can guarantee the list is short (~ n<=20), go ahead and use mapM 2.  Otherwise use mapM_, foldM_, or foldM if a real reduction is possible (i.e. not "foldM snocM []").

Step 2 sometimes requires changing my design, but it's always been for the better.  `mapM_` tends to require more pipeline composition, so it's leveraging the language's strengths.

This thread is really interesting - it relates directly to problems I am currently having with mapM over large lists (see the thread "stack overflow pain").

Can you explain what you mean by "mapM_ tends to require more pipeline composition"? In what way is it leveraging the language strengths?

Hmm, that is suitably cryptic.  One way to think of it is an inversion of control.  Instead of operating on whole collections of things in a monad, you specify monadic actions (pipelines) which are applied sequentially to each input.

Here's a simple example.  Suppose you have a bunch of data serialized to files, and you want to read each file into a data structure, apply some process based upon the last file's data, and write out the output to new files.  One way to do that would look like:

do    dats <- mapM readMyData files    let pairs = zip (mempty:dats) dats    zipWithM_ (\(last, this) fname -> writeMyData (update last this) fname) pairs newFiles

However, you could also put everything into a single monadic operation, like this

do    foldM_ (\last (infile, outfile) -> do                                                    this <- readMyData infile                                                    writeMyData (update last this) outfile                                                    return this               )               mempty               (zip files newFiles)

The first interleaves control (mapM, zipWIthM_) with monadic actions (file IO), whereas the second only has one control function (foldM_) which completely processes one input.  I say this is more pipeline composition because you have to create an entire pipeline from input to output, which is then sequentially fed inputs by the control function.

I say this leverages Haskell's strengths because it's quite easy to compose functions and monadic actions in Haskell.  It also tends to be garbage-collector friendly.  I also find it much easier to reason about space usage.  You don't need to worry if part of a list is being retained, because the full list of data doesn't appear anywhere.  If you need to access prior elements they're specified explicitly so you know exactly how much data you're holding on to.

My perspective might be warped by my work on iteratees, but I find this a very natural approach.

John L.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Malcolm, one should amortize the cost of the collection over the amount of free space allocated rather than recovered (there are cases when no space is recovered, would you call the GC cost infinite then?). If one does that, and also runs the expensive collection not too often [1], the time amortizes to O(1) easily (notice that the amount allocated between GCs can be kept proportional to H). I don't know if GC used in GHC does indeed have amortized O(1) cost per allocation, but if it doesn't, it should. [1] - a sufficient condition would be that there exists some real number q such that q > 1 and the next GC runs not sooner than when H reaches H_0*q where H_0 is the heap size remaining after the last collection. On 27 September 2011 10:02, Malcolm Wallace wrote:

On 26 Sep 2011, at 23:14, Arseniy Alekseyev wrote:

...

Garbage collection takes amortized O(1) per allocation, doesn't it?

No.  For Mark-Sweep GC, the cost is proportional to

(H+R) / (H-R) where H is the total heap size      R is the reachable (i.e. live) heap

This formula amortises the cost of a collection over the amount of free space recovered. For two-space copying collection, the cost is proportional to

R / ((H/2)-R)

In both cases, as R approaches H (or H/2), the cost of GC becomes rather large.  So in essence, the more live data you have, the more GC will cost.

Regards,    Malcolm

Ketil, I suppose your argument is correct for some implementations of GC (hopefully not the ones I use). However, a trivial optimisation of running GC with a frequency logarithmic in the (allocation rate / heap size) seems to make almost any kind of GC amortized O(1) while keeping the total heap bounded within constant factor of the reachable heap size. So, we optimize the (1.) in your algorithm and in case of mapM we should get a logarithmic (instead of linear) number of GCs with exponentially (instead of linearly) increasing costs reaching O(N) in the end and totalling to O(N) too! Does anyone know if such worst-case complexity precautions are taken in GHC? If not, why? Malcolm, I fail to see how "They are the same thing" is compatible with "Indeed I would". They together imply that O(1) (GC amortized over the amount allocated) and O(+inf) (GC amortized over the amount reclaimed) are the same thing. Also, I don't see how OOM condition is relevant here. I may have enough memory for a lot of useful things even without GC. On 27 September 2011 12:42, Ketil Malde wrote:

Here's my feeble understanding of GC:

1. GC runs when after some specified amount of allocations 2. GC runs in time proportional to the live heap, which it needs to   traverse.

This means that for a long running mapM, like any other computation generating a long list, (1) GC will run a number of times proportional to the length of the list, and (2) each run will have a cost proportional to the length of the list.  I.e. a linear algorithm is now quadratic.

A lazy mapM (or mapM_), consuming the list as fast as it is generated, will of course keep the list short/heap small, and thus the cost of each GC is constant (for some value of "constant").

I suppose generational GC will help in practice, since the young generation gets to start near the end of the list, but it will still be linear in generated length, and you still need major GCs too, occasionally.

Also, I guess mapM is more vulnerable to this, since the operations (IO, say) involved in building the list likely do short-lived allocations, triggering more GCs than simpler, pure computations would.

Do let me know if this is probably a terribly naive view.

-k -- If I haven't seen further, it is by standing in the footprints of giants

On 27 September 2011 12:35, Malcolm Wallace wrote:

On 27 Sep 2011, at 11:23, Arseniy Alekseyev wrote:

...

Malcolm, one should amortize the cost of the collection over the amount of free space allocated rather than recovered

They are the same thing.  You can only allocate from the space that has been recovered.  It is true that generational GC has a nursery area of largely constant size, which is always used for fresh allocation, but that is usually considered an optimisation (albeit a considerable one), which does not fundamentally change the underlying asymptotic costs of the major collections.  When you have large heap residency, the proportion of time spent in GC increases.

...

(there are cases when no space is recovered, would you call the GC cost infinite then?).

Indeed I would.  When that happens, usually the program aborts without completing its computation, so the computation is infinitely delayed.

Regards,    Malcolm