Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)
On Tue, Apr 26, 2011 at 6:32 PM, John Millikin wrote: > On Tuesday, April 26, 2011 7:19:25 AM UTC-7, John Lato wrote: > >> I'd be interested to see the results of a shootout between iteratee and >> enumerator. I would expect them to be basically equivalent most of the >> time, with maybe two or three operations with a small (but consistent) >> difference one way or the other. >> > > I did some basic benchmarks a few months ago; if I remember correctly, it > depends almost entirely on how well GHC optimizes CPS on a particular > platform. The relative performace was very similar to Lennart Kolmodin's > benchmarks of "binary" at < > http://lennartkolmodin.blogspot.com/2011/02/binary-by-numbers.html >. In > particular, CPS/"iteratee" is faster on 32-bit, while state > passing/"enumerator" is faster on 64-bit. > > This difference exists for almost all operations, and was on the order of > 5-15% depending on the shape of the input. I couldn't figure out a good way > to benchmark the libraries themselves when there's so much noise from the > compiler. > That figures. Thanks for sharing this. John L. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)
On Tuesday, April 26, 2011 7:19:25 AM UTC-7, John Lato wrote: > I'd be interested to see the results of a shootout between iteratee and > enumerator. I would expect them to be basically equivalent most of the > time, with maybe two or three operations with a small (but consistent) > difference one way or the other. > I did some basic benchmarks a few months ago; if I remember correctly, it depends almost entirely on how well GHC optimizes CPS on a particular platform. The relative performace was very similar to Lennart Kolmodin's benchmarks of "binary" at < http://lennartkolmodin.blogspot.com/2011/02/binary-by-numbers.html >. In particular, CPS/"iteratee" is faster on 32-bit, while state passing/"enumerator" is faster on 64-bit. This difference exists for almost all operations, and was on the order of 5-15% depending on the shape of the input. I couldn't figure out a good way to benchmark the libraries themselves when there's so much noise from the compiler. I'm waiting for GHC7 to stabilise a bit before doing another benchmark -- the LLVM backend and new CPS handling should make both implementations faster, once they're a bit more mature. I really hope CPS becomes as fast on 64-bit as it is on 32-bit, because it's a much cleaner implementation. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)
Joining slightly late... > From: John Millikin > > John Lato's "iteratee" package is based on IterateeMCPS.hs[1]. I used > IterateeM.hs for "enumerator", because when I benchmarked them the non-CPS > version was something like 10% faster on most operations. > Based on tests I did before iteratee-0.4, the fastest implementation was Oleg's alternate design which is in the comments of IterateeM.hs. I don't think any current packages use that however, with good reason. I'd be interested to see the results of a shootout between iteratee and enumerator. I would expect them to be basically equivalent most of the time, with maybe two or three operations with a small (but consistent) difference one way or the other. John L. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)
You wouldn't be so confused if you had actually looked at Lato's implementation and compared it to Oleg's most recent version. Regards, John A. De Goes Twitter: @jdegoes LinkedIn: http://linkedin.com/in/jdegoes On Apr 21, 2011, at 6:27 PM, Jason Dagit wrote: > > > On Thu, Apr 21, 2011 at 8:36 AM, John A. De Goes wrote: > > This is a much cleaner definition of Iteratee and I'm happy to see it. > > I'm confused by this comment. Isn't John Lato's implementation of Iteratee > (on hackage) is based on the example implementation that Oleg pointed you > towards? > > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)
On Fri, Apr 22, 2011 at 5:54 AM, Maciej Marcin Piechotka
wrote:
> For the record: such code is therefore illegal
>
> abab :: Iteratee Char Identity ()
> abab = continue parseA
> where parseA (Chunks ('a':'b':xs)) = parseA (Chunks xs)
> parseA (Chunks ('a':[])) = continue parseB
> parseA (Chunks xs@(_:_)) = yield () xs
> parseA (Chunks []) = continue parseA
> parseA EOF = yield () EOF
> parseB (Chunks ('b':xs)) = parseA (Chunks xs)
> parseB (Chunks xs@(_:_)) = yield () (a:xs)
> parseB (Chunks []) = continue parseB
> parseB EOF = yield () ['a']
Is it really illegal? I guess you're pointing out a problem with the
last line, because it's EOF and we yield something. But that
something was given to us in some "continue" step. IMHO, that's
perfectly fine. The same thing goes for the other yield in parseB.
Cheers,
--
Felipe.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)
On Tue, 2011-04-19 at 10:02 -0300, Felipe Almeida Lessa wrote:
>
> Now, that's what I get from reading the code. I don't remember if it
> is explicitly allowed or forbidden for an iteratee to generate
> leftovers out of nowhere. My guess is that it doesn't make much sense
> to allow it.
For the record: such code is therefore illegal
abab :: Iteratee Char Identity ()
abab = continue parseA
where parseA (Chunks ('a':'b':xs)) = parseA (Chunks xs)
parseA (Chunks ('a':[])) = continue parseB
parseA (Chunks xs@(_:_)) = yield () xs
parseA (Chunks []) = continue parseA
parseA EOF = yield () EOF
parseB (Chunks ('b':xs)) = parseA (Chunks xs)
parseB (Chunks xs@(_:_)) = yield () (a:xs)
parseB (Chunks []) = continue parseB
parseB EOF = yield () ['a']
Regards
signature.asc
Description: This is a digitally signed message part
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)
John Lato's "iteratee" package is based on IterateeMCPS.hs[1]. I used IterateeM.hs for "enumerator", because when I benchmarked them the non-CPS version was something like 10% faster on most operations. The new IterateeM.hs solves some problems with the old encoding, but I haven't switched "enumerator" to it yet because it would break backwards compatibility. [1] http://okmij.org/ftp/Haskell/Iteratee/IterateeMCPS.hs ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)
On Thu, Apr 21, 2011 at 8:36 AM, John A. De Goes wrote: > > This is a much cleaner definition of Iteratee and I'm happy to see it. > I'm confused by this comment. Isn't John Lato's implementation of Iteratee (on hackage) is based on the example implementation that Oleg pointed you towards? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)
This is a much cleaner definition of Iteratee and I'm happy to see it. When are you going to move from your FTP site to Github, by the way? :) Regards, John A. De Goes Twitter: @jdegoes LinkedIn: http://linkedin.com/in/jdegoes On Apr 21, 2011, at 12:32 AM, o...@okmij.org wrote: > > Daniel Schuessler wrote: > >> The thing I don't understand yet is the last line: Why is it OK to discard >> the >> leftover input from the (f x) Iteratee and yield just the leftover input from >> the first one (m0)? > > First of all, the question is about an older version of Iteratee. For > example, the following code > http://okmij.org/ftp/Haskell/Iteratee/Iteratee.hs > defines Iteratee a bit differently so the question does not apply. > >> data Iteratee a = IE_done a >> | IE_cont (Maybe ErrMsg) (Stream -> (Iteratee a,Stream)) >> >> instance Monad Iteratee where >> return = IE_done >> IE_done a >>= f = f a >> IE_cont e k >>= f = IE_cont e (docase . k) >>where >>docase (IE_done a, stream) = case f a of >> IE_cont Nothing k -> k stream >> i -> (i,stream) >>docase (i, s) = (i >>= f, s) > > No left-over is discarded any more. > > Your question is about the previous design, called `The second design' > described in Iteratee.hs. The corresponding comment block answers your > question, please search for ``Justification for the case IE_done x > s >>= f''. > > Please see > http://okmij.org/ftp/Haskell/Iteratee/IterateeM.hs > for the `production' case of Iteratee in a base monad. The file > IterateeM.hs talks about one more design, and its drawbacks. > > It's all about finding the optimal trade-off, I guess. > > > > ___ > 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
Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)
Daniel Schuessler wrote: > The thing I don't understand yet is the last line: Why is it OK to discard the > leftover input from the (f x) Iteratee and yield just the leftover input from > the first one (m0)? First of all, the question is about an older version of Iteratee. For example, the following code http://okmij.org/ftp/Haskell/Iteratee/Iteratee.hs defines Iteratee a bit differently so the question does not apply. > data Iteratee a = IE_done a > | IE_cont (Maybe ErrMsg) (Stream -> (Iteratee a,Stream)) > > instance Monad Iteratee where > return = IE_done > IE_done a >>= f = f a > IE_cont e k >>= f = IE_cont e (docase . k) > where > docase (IE_done a, stream) = case f a of >IE_cont Nothing k -> k stream >i -> (i,stream) > docase (i, s) = (i >>= f, s) No left-over is discarded any more. Your question is about the previous design, called `The second design' described in Iteratee.hs. The corresponding comment block answers your question, please search for ``Justification for the case IE_done x s >>= f''. Please see http://okmij.org/ftp/Haskell/Iteratee/IterateeM.hs for the `production' case of Iteratee in a base monad. The file IterateeM.hs talks about one more design, and its drawbacks. It's all about finding the optimal trade-off, I guess. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)
It's not OK and it's an artifact of the weak-typing and ill-defined semantics that pervade iteratee libraries. It's possible to do a lot of bad stuff, including binding with an iteratee yielding a remainder without consuming input. Regards, John A. De Goes Twitter: @jdegoes LinkedIn: http://linkedin.com/in/jdegoes On Apr 19, 2011, at 6:27 AM, Daniel Schüssler wrote: > Hello, > > for reference, said instance is: > >> instance Monad m => Monad (Iteratee a m) where >> return x = yield x (Chunks []) >> >> m0 >>= f = ($ m0) $ fix $ >> \bind m -> Iteratee $ runIteratee m >>= \r1 -> >> case r1 of >> Continue k -> return (Continue (bind . k)) >> Error err -> return (Error err) >> Yield x (Chunks []) -> runIteratee (f x) >> Yield x extra -> runIteratee (f x) >>= \r2 -> >> case r2 of >> Continue k -> runIteratee (k >> extra) >> Error err -> return (Error err) >> Yield x' _ -> return (Yield x' >> extra) > > The thing I don't understand yet is the last line: Why is it OK to discard > the > leftover input from the (f x) Iteratee and yield just the leftover input from > the first one (m0)? > > Cheers, > Daniel > > ___ > 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
Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)
It's forbidden for an iteratee to yield extra input that it hasn't consumed; however, this is unfortunately not enforced by the type system. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)
2011/4/19 Daniel Schüssler : > Hello, > > for reference, said instance is: > >> instance Monad m => Monad (Iteratee a m) where >> return x = yield x (Chunks []) >> >> m0 >>= f = ($ m0) $ fix $ >> \bind m -> Iteratee $ runIteratee m >>= \r1 -> >> case r1 of >> Continue k -> return (Continue (bind . k)) >> Error err -> return (Error err) >> Yield x (Chunks []) -> runIteratee (f x) >> Yield x extra -> runIteratee (f x) >>= \r2 -> >> case r2 of >> Continue k -> runIteratee (k >> extra) >> Error err -> return (Error err) >> Yield x' _ -> return (Yield x' >> extra) > > The thing I don't understand yet is the last line: Why is it OK to discard the > leftover input from the (f x) Iteratee and yield just the leftover input from > the first one (m0)? On that stage no input was given to (f x), we just runned it without anything and it already yielded something. So whatever it yielded must be without leftovers. Now, that's what I get from reading the code. I don't remember if it is explicitly allowed or forbidden for an iteratee to generate leftovers out of nowhere. My guess is that it doesn't make much sense to allow it. Cheers, -- Felipe. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Question about the Monad instance for Iteratee (from the enumerator package)
Hello, for reference, said instance is: > instance Monad m => Monad (Iteratee a m) where > return x = yield x (Chunks []) > > m0 >>= f = ($ m0) $ fix $ > \bind m -> Iteratee $ runIteratee m >>= \r1 -> > case r1 of > Continue k -> return (Continue (bind . k)) > Error err -> return (Error err) > Yield x (Chunks []) -> runIteratee (f x) > Yield x extra -> runIteratee (f x) >>= \r2 -> > case r2 of > Continue k -> runIteratee (k > extra) > Error err -> return (Error err) > Yield x' _ -> return (Yield x' > extra) The thing I don't understand yet is the last line: Why is it OK to discard the leftover input from the (f x) Iteratee and yield just the leftover input from the first one (m0)? Cheers, Daniel ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
