On Tue, 2007-04-10 at 12:14 +0200, apfelmus wrote:
Oren Ben-Kiki wrote:
> The code is in http://hpaste.org/1314#a1 if anyone at all is willing
> to take pity on me and explain what I'm doing wrong.
There is an important point to note about streaming, namely that it
conflicts with knowing whether the input is syntactically correct or
not.
True, this is the core issue. Think of a turing machine processing an
infinite tape. It is writing output and producing a final result; it is
possible to examine the output tape before knowing the final result.
Haskell parsers insist on having the "output tape" live in memory until
the final result is known, and then give it to you as one huge object
when done (or discard it and just give you the error message). NOT a
good idea if your input tape is a 200 MB file!
You've probably noticed this already and introduced rToken for that
reason but I'm not sure.
The idea is that the parser generates a stream of tokens. If/when it
hits an error, you get an error token at the end and parsing stops.
> Chasing down my memory leak I got into a weird situation where adding
> a magic manual SCC section and compiling with -prof makes the leak
> disappear.
That sounds fishy. Note that manual SCC annotations + optimization
currently is a bit buggy in GHC, in the sense that optimization disturbs
correct cost attribution.
Er... I just added '-prof'. No '-O' flag at all so no optimizations,
right?
Does the program eat the output of yes 'a' without memory explosion
showed by "top"? If so, it could perhaps be a problem of the
optimization phase which maybe expands
D.append parsed (case result of ...)
to
case result of {
Nothing -> D.append parsed D.empty
Just .. -> D.append parsed (D.singleton...) }
The latter won't stream because of the reason noted above.
Ah, but it *does* stream! This is the beauty of lazy evaluation.
The "free" code is basically:
reply = parse ... -- Lazily evaluated
tokens = rTokens reply -- Has some values "immediately"
list = D.toList tokens -- Has some values "immediately"
mapM_ list print -- Start printing "immediately"!
Where what "parse" does is:
reply = Reply {
rTokens = D.append concreteToken lazyTokens, -- "Immediate"
rResult = lazyResult -- Only available at end of parsing
}
So every time the parser calls "D.append" into the tokens, the printing
"D.toList" is able to extract, print and GC the token immediately. And
this works perfectly, with constant memory consumption. The problem
occurs when I peek at the final "rResult" field. The "leak" code says:
reply = parse ... -- Lazily evaluated
result = rResult reply -- Lazy; has value when parsing is done
extra = case result ... -- Lazy; has value when parsing is done
parsed = rTokens reply -- Has some values "immediately"
tokens = D.append parsed extra -- Has some values "immediately"
list = D.toList tokens -- Has some values "immediately"
mapM_ list print -- Starts printing "immediately"!
This *still* starts printing tokens immediately. However, while in the
previous case the GC is smart enough to keep the program in constant
memory size, in the second case it for some reasons starts missing more
and more PAP objects so memory usage goes through the roof.
But it's
highly unlikely that GHC performs a transformation that changes
semantics this radically.
You'd think... but the fact of the matter is that while the first
version works fine, the second doesn't, UNLESS I add the magic SCC
section:
extra = {-# SCC "magic" #-} case result ...
And compile with '-prof' (no '-O' flags). Then it somehow, finally, "get
the idea" and the program runs perfectly well with constant memory
consumption. Which, as you aptly put it, is very "fishy" indeed...
> I can achieve the results I want in very short elegant code...
In my opinion, your streaming parser is not as elegant as it could be
which makes it hard to read the code.
Well... one point is the above basically establishes two "threads", one
printing tokens and one producing them. communicating through a sort of
message queue (rTokens). I think that's pretty elegant compared to the
hoops you need to jump through to do this in any other language :-)
Another point is that this is a dumbed-down toy example. In the real
program the parser does much more which justifies the awkwardness you
point out. Specifically there are nifty ways to handle decision points
(parsing isn't much good unless there are alternatives to be tested at
each point :-).
With monad transformers, we almost
have
Parser a ~= StateT State (WriterT (D.DList Token) Maybe) a
~= State -> (D.DList Token, Maybe (a,State))
Monad transformers are a bit beyond my grasp at this point, but from the
little I know about them I don't see how they would help me with the
GC/memory problem. They definitely might make the code even more
elegant...
Also, I'm really missing type signatures, especially for many. When
reading the code, I expected
many :: Parser a -> Parser [a]
but had to conclude
many :: Parser a -> Parser ()
by inspecting its code.
Sorry about that. Yes, all the "syntax" functions have this signature. I
added these as www.hpaste.org/1314#a2.
Is it possible I have hit on a bug in GHC's implementation, and adding
'-prof' somehow caused it to work around it?
Thanks,
Oren Ben-Kiki
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
