[Haskell-cafe] Re: Strange memory consumption problems in something that should be tail-recursive

[apfelmus at quantentunnel.de]

Jefferson Heard wrote:
> Argh, bitten by the scheme bug! Right -- NO tail recursion...  So that leaves 
> me with some rather non-intuitive strategies for achieving execution time 
> efficiency.  Anyone care to point me in the direction of a document on 
> efficiency in Haskell?

Besides, proper tail recursion in Haskell needs strictness annotations,
but the best way is to forget the two words "tail recursive" altogether :)

It always helps to do a rough calculation of how much time you have to
expect it to run. Processing 1TB with a 1GHz processor and 16=2^4
machine instruction in the inner loop (must be quite short, the loop) takes

 2^40 / (2^30 / 16) = 2^14 seconds ~ 4.5 hours

Of course, these 4.5 hours are quite sensitive to the 2^4 factor and
might well be 3 or 9 hours. Assuming that you ran alex on a String, the
reported 36 hours are entirely reasonable, in the sense of alex not
being overly slow.

Regards,
apfelmus