[Haskell-cafe] Re: Haskell-Cafe Digest, Vol 78, Issue 14
greg at gregorycollins.net
Thu Feb 11 11:00:09 EST 2010
Maciej Piechotka <uzytkownik2 at gmail.com> writes:
> On Tue, 2010-02-09 at 16:41 +0000, John Lato wrote:
>> See http://inmachina.net/~jwlato/haskell/ParsecIteratee.hs for a valid
>> Stream instance using iteratee. Also Gregory Collins recently posted
>> an iteratee wrapper for Attoparsec to haskell-cafe. To my knowledge
>> these are not yet in any packages, but hackage is vast.
> Hmm. Am I correct that his implementation caches everything?
The one that John posted (iteratees on top of parsec) has to keep a copy
of the entire input, because parsec wants to be able to do arbitrary
backtracking on the stream.
Attoparsec provides an *incremental* parser. You feed it bite-sized
chunks of an input stream, and it either says "ok, I'm done, here's your
value, and the rest of the stream I didn't use" or "I couldn't finish,
here's a parser continuation you can feed more chunks to." This, of
course, is a perfect conceptual match for iteratees -- with a little bit
of plumbing you should be able to parse a stream in O(1) space.
> I tried to rewrite the implementation using... well imperative linked
> list. For trivial benchmark it have large improvement (althought it may
> be due to error in test such as using ByteString) and, I believe, that
> it allows to free memory before finish.
> Results of test on Core 2 Duo 2.8 GHz:
> 10: 0.000455s 0.000181s
> 100: 0.000669s 0.001104s
> 1000: 0.005209s 0.023704s
> 10000: 0.053292s 1.423443s
> 100000: 0.508093s 132.208597s
Which column corresponds to which module here, and which module are you
benchmarking against, John's or mine?
Gregory Collins <greg at gregorycollins.net>
More information about the Haskell-Cafe