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

[Donald Bruce Stewart]

duncan.coutts:
> On Tue, 2007-02-13 at 15:27 -0500, Jefferson Heard wrote:
> > Hi, I am running the following code against a 210 MB file in an attempt to 
> > determine whether I should use alex or whether, since my needs are very 
> > performance oriented, I should write a lexer of my own.  I thought that 
> > everything I'd written here was tail-recursive
> 
> Isn't that exactly the problem - that it's tail recursive? You do not
> want it to be tail recursive since then it must consume the whole input
> before producing any output. You want it to be as lazy as possible so
> that it can start producing tokens as soon as possible without having to
> consume everything.
> 
> If performance is really important to you then you may also want to
> investigate lexing from a lazy ByteString. Alex can now do that (darcs
> version) or you can do it by hand as you're trying now.
> 

I'd reenforce this point: the only chance for C like performance for
this kind of problem is to use lazy bytestrings, or a combined strict
head, lazy tail approach. Then you can reasonably expect to compete with
C.

Examples on the shootout.

-- Don