Combinator parsing questions ... is performance problematic?

On Thursday September 24 2009, Marius Danciu wrote:
> Hi all,
>
> I'd like to parse large csv file using combinator parser ...
>
> ...
>
> Are combinator parsers fitful for parsing large files?

Fitful?

I tend to think a format as simple as CSV (even if you have variations
on the literal "comma-separated" part) is not best served by a parser
formalism as rich as an LL* parser.

Similarly, I don't think it will be easy, if at all possible, to make a
combinator parser perform as well as a simpler, hand-written parser (or
the Java StreamTokenizer), at least not for a parsing task that is so
manageable using such simpler techniques.

> Br's,
> Marius

Randall Schulz

hi Marius

I use String.split and happily parse 1000000+ record csv files in less
than a minute

michael

On 9/25/09, Marius Danciu wrote:
> Hi all,
>
> I'd like to parse large csv file using combinator parser so I have the
> following simple example:
>
> class CSVParser extends Parsers {
> type Elem = Char
>
> var fnc: List[String] => Unit = l => ()
>
> lazy val item = elem("elem", c => {isLetterOrDigit(c) || c == '_'}).+ ^^
> {_ mkString("")}
> lazy val spaces = elem("elem", isSpace).*
> lazy val sep = spaces ~ elem(',') ~ spaces
> lazy val expr = item ~ (sep ~> item).* ^^ {case l ~ r => l :: r}
> lazy val exprs = ((expr <~ (elem('\r') ~ elem('\n'))) ^^ (fnc(_))).+
>
> def parse(in: java.io.Reader)(f: List[String] => Unit) {
> fnc = f
> exprs(StreamReader(in))
> }
> }
>
> I have a 64 MB csv file and I'm getting pretty soon:
>
> Exception in thread "main" java.lang.StackOverflowError
> at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
> at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
> at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
>
>
> The second thing is that if I read the file using a Java BufferedReader and
> feed to my parser line by line, it takes to parse 64MB in more then one
> minute. A pure Java StringTokenizer approach takes about 5 seconds. Any
> thoughts?
>
> Are combinator parsers fitful for parsing large files?
>
>
>
> Br's,
> Marius
>

hi Marius

I use String.split and happily parse 1000000+ record csv files in less
than a minute

michael

On 9/25/09, Marius Danciu <marius [dot] danciu [at] gmail [dot] com> wrote:
> Hi all,
>
> I'd like to parse large csv file using combinator parser so I have the
> following simple example:
>
> class CSVParser extends Parsers {
>   type Elem = Char
>
>   var fnc: List[String] => Unit = l => ()
>
>   lazy val item = elem("elem", c => {isLetterOrDigit(c) || c == '_'}).+ ^^
> {_ mkString("")}
>   lazy val spaces = elem("elem", isSpace).*
>   lazy val sep = spaces ~ elem(',') ~ spaces
>   lazy val expr = item ~ (sep ~> item).* ^^ {case l ~ r => l :: r}
>   lazy val exprs = ((expr <~ (elem('\r') ~ elem('\n'))) ^^ (fnc(_))).+
>
>   def parse(in: java.io.Reader)(f: List[String] => Unit) {
>     fnc = f
>     exprs(StreamReader(in))
>   }
> }
>
> I have a 64 MB csv file and I'm getting pretty soon:
>
> Exception in thread "main" java.lang.StackOverflowError
>     at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
>     at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
>     at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
>
>
> The second thing is that if I read the file using a Java BufferedReader and
> feed to my parser line by line, it takes to parse 64MB in more then one
> minute. A pure Java StringTokenizer approach takes about 5 seconds. Any
> thoughts?
>
> Are combinator parsers fitful for parsing large files?
>
>
>
> Br's,
> Marius
>

Hi,

I understand that split/StringTokenizer are really easy to use in many cases. However there might be more complex grammars that I would have liked to parse using combinator parsers for pretty large files.

Can anyone explain why the combinator parsers is not even compare (based on simple tests that I made) with raw imperative parsing? .. I mean I expected some overhead induced by functional style of comb. parsers but the difference is quite significant.


Br's,
Marius

On Fri, Sep 25, 2009 at 8:30 AM, Michael Davey <michael4096 [at] googlemail [dot] com> wrote:

hi Marius

I use String.split and happily parse 1000000+ record csv files in less
than a minute

michael

On 9/25/09, Marius Danciu <marius [dot] danciu [at] gmail [dot] com> wrote:
> Hi all,
>
> I'd like to parse large csv file using combinator parser so I have the
> following simple example:
>
> class CSVParser extends Parsers {
>   type Elem = Char
>
>   var fnc: List[String] => Unit = l => ()
>
>   lazy val item = elem("elem", c => {isLetterOrDigit(c) || c == '_'}).+ ^^
> {_ mkString("")}
>   lazy val spaces = elem("elem", isSpace).*
>   lazy val sep = spaces ~ elem(',') ~ spaces
>   lazy val expr = item ~ (sep ~> item).* ^^ {case l ~ r => l :: r}
>   lazy val exprs = ((expr <~ (elem('\r') ~ elem('\n'))) ^^ (fnc(_))).+
>
>   def parse(in: java.io.Reader)(f: List[String] => Unit) {
>     fnc = f
>     exprs(StreamReader(in))
>   }
> }
>
> I have a 64 MB csv file and I'm getting pretty soon:
>
> Exception in thread "main" java.lang.StackOverflowError
>     at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
>     at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
>     at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
>
>
> The second thing is that if I read the file using a Java BufferedReader and
> feed to my parser line by line, it takes to parse 64MB in more then one
> minute. A pure Java StringTokenizer approach takes about 5 seconds. Any
> thoughts?
>
> Are combinator parsers fitful for parsing large files?
>
>
>
> Br's,
> Marius
>

Any other thoughts please?

Thanks,
Marius

On Fri, Sep 25, 2009 at 8:48 AM, Marius Danciu <marius [dot] danciu [at] gmail [dot] com> wrote:

Hi,

I understand that split/StringTokenizer are really easy to use in many cases. However there might be more complex grammars that I would have liked to parse using combinator parsers for pretty large files.

Can anyone explain why the combinator parsers is not even compare (based on simple tests that I made) with raw imperative parsing? .. I mean I expected some overhead induced by functional style of comb. parsers but the difference is quite significant.


Br's,
Marius

On Fri, Sep 25, 2009 at 8:30 AM, Michael Davey <michael4096 [at] googlemail [dot] com> wrote:

hi Marius

I use String.split and happily parse 1000000+ record csv files in less
than a minute

michael

On 9/25/09, Marius Danciu <marius [dot] danciu [at] gmail [dot] com> wrote:
> Hi all,
>
> I'd like to parse large csv file using combinator parser so I have the
> following simple example:
>
> class CSVParser extends Parsers {
>   type Elem = Char
>
>   var fnc: List[String] => Unit = l => ()
>
>   lazy val item = elem("elem", c => {isLetterOrDigit(c) || c == '_'}).+ ^^
> {_ mkString("")}
>   lazy val spaces = elem("elem", isSpace).*
>   lazy val sep = spaces ~ elem(',') ~ spaces
>   lazy val expr = item ~ (sep ~> item).* ^^ {case l ~ r => l :: r}
>   lazy val exprs = ((expr <~ (elem('\r') ~ elem('\n'))) ^^ (fnc(_))).+
>
>   def parse(in: java.io.Reader)(f: List[String] => Unit) {
>     fnc = f
>     exprs(StreamReader(in))
>   }
> }
>
> I have a 64 MB csv file and I'm getting pretty soon:
>
> Exception in thread "main" java.lang.StackOverflowError
>     at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
>     at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
>     at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
>
>
> The second thing is that if I read the file using a Java BufferedReader and
> feed to my parser line by line, it takes to parse 64MB in more then one
> minute. A pure Java StringTokenizer approach takes about 5 seconds. Any
> thoughts?
>
> Are combinator parsers fitful for parsing large files?
>
>
>
> Br's,
> Marius
>

I think there's a version of combinator parsers somewhere (in 2.8-land? in paulp's hidden attic of awesome scala code?) that are memoized and thus substantially faster.

I don't think original parser combinators library was written with performance particularly in mind.

--j

On Fri, Sep 25, 2009 at 9:14 PM, Marius Danciu <marius [dot] danciu [at] gmail [dot] com> wrote:

Any other thoughts please?

Thanks,
Marius

On Fri, Sep 25, 2009 at 8:48 AM, Marius Danciu <marius [dot] danciu [at] gmail [dot] com> wrote:

Hi,

I understand that split/StringTokenizer are really easy to use in many cases. However there might be more complex grammars that I would have liked to parse using combinator parsers for pretty large files.

Can anyone explain why the combinator parsers is not even compare (based on simple tests that I made) with raw imperative parsing? .. I mean I expected some overhead induced by functional style of comb. parsers but the difference is quite significant.


Br's,
Marius

On Fri, Sep 25, 2009 at 8:30 AM, Michael Davey <michael4096 [at] googlemail [dot] com> wrote:

hi Marius

I use String.split and happily parse 1000000+ record csv files in less
than a minute

michael

On 9/25/09, Marius Danciu <marius [dot] danciu [at] gmail [dot] com> wrote:
> Hi all,
>
> I'd like to parse large csv file using combinator parser so I have the
> following simple example:
>
> class CSVParser extends Parsers {
>   type Elem = Char
>
>   var fnc: List[String] => Unit = l => ()
>
>   lazy val item = elem("elem", c => {isLetterOrDigit(c) || c == '_'}).+ ^^
> {_ mkString("")}
>   lazy val spaces = elem("elem", isSpace).*
>   lazy val sep = spaces ~ elem(',') ~ spaces
>   lazy val expr = item ~ (sep ~> item).* ^^ {case l ~ r => l :: r}
>   lazy val exprs = ((expr <~ (elem('\r') ~ elem('\n'))) ^^ (fnc(_))).+
>
>   def parse(in: java.io.Reader)(f: List[String] => Unit) {
>     fnc = f
>     exprs(StreamReader(in))
>   }
> }
>
> I have a 64 MB csv file and I'm getting pretty soon:
>
> Exception in thread "main" java.lang.StackOverflowError
>     at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
>     at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
>     at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
>
>
> The second thing is that if I read the file using a Java BufferedReader and
> feed to my parser line by line, it takes to parse 64MB in more then one
> minute. A pure Java StringTokenizer approach takes about 5 seconds. Any
> thoughts?
>
> Are combinator parsers fitful for parsing large files?
>
>
>
> Br's,
> Marius
>

Marius Danciu wrote:
> Can anyone explain why the combinator parsers is not even compare (based on
> simple tests that I made) with raw imperative parsing? .. I mean I expected
> some overhead induced by functional style of comb. parsers but the
> difference is quite significant.
>
Marius,

Bernie Pope gave talk about Parser Combinators at Melbourne Scala User
Group that discussed performance issues related to backtracking.

See the following slides, esp slide 47
http://www.cs.mu.oz.au/~bjpop/parser_combinators.pdf

-Ben

>
> Br's,
> Marius
>
> On Fri, Sep 25, 2009 at 8:30 AM, Michael Davey
> wrote:
>
>
>> hi Marius
>>
>> I use String.split and happily parse 1000000+ record csv files in less
>> than a minute
>>
>> michael
>>
>> On 9/25/09, Marius Danciu wrote:
>>
>>> Hi all,
>>>
>>> I'd like to parse large csv file using combinator parser so I have the
>>> following simple example:
>>>
>>> class CSVParser extends Parsers {
>>> type Elem = Char
>>>
>>> var fnc: List[String] => Unit = l => ()
>>>
>>> lazy val item = elem("elem", c => {isLetterOrDigit(c) || c == '_'}).+
>>>
>> ^^
>>
>>> {_ mkString("")}
>>> lazy val spaces = elem("elem", isSpace).*
>>> lazy val sep = spaces ~ elem(',') ~ spaces
>>> lazy val expr = item ~ (sep ~> item).* ^^ {case l ~ r => l :: r}
>>> lazy val exprs = ((expr <~ (elem('\r') ~ elem('\n'))) ^^ (fnc(_))).+
>>>
>>> def parse(in: java.io.Reader)(f: List[String] => Unit) {
>>> fnc = f
>>> exprs(StreamReader(in))
>>> }
>>> }
>>>
>>> I have a 64 MB csv file and I'm getting pretty soon:
>>>
>>> Exception in thread "main" java.lang.StackOverflowError
>>> at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
>>> at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
>>> at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
>>>
>>>
>>> The second thing is that if I read the file using a Java BufferedReader
>>>
>> and
>>
>>> feed to my parser line by line, it takes to parse 64MB in more then one
>>> minute. A pure Java StringTokenizer approach takes about 5 seconds. Any
>>> thoughts?
>>>
>>> Are combinator parsers fitful for parsing large files?
>>>
>>>
>>>
>>> Br's,
>>> Marius
>>>
>>>
>
>

Marius Danciu wrote:

Can anyone explain why the combinator parsers is not even compare (based on
simple tests that I made) with raw imperative parsing? .. I mean I expected
some overhead induced by functional style of comb. parsers but the
difference is quite significant.
 

Marius,

Bernie Pope gave talk about Parser Combinators at Melbourne Scala User Group that discussed performance issues related to backtracking.

See the following slides, esp slide 47
http://www.cs.mu.oz.au/~bjpop/parser_combinators.pdf

-Ben

Br's,
Marius

On Fri, Sep 25, 2009 at 8:30 AM, Michael Davey
<michael4096 [at] googlemail [dot] com>wrote:

 

hi Marius

I use String.split and happily parse 1000000+ record csv files in less
than a minute

michael

On 9/25/09, Marius Danciu <marius [dot] danciu [at] gmail [dot] com> wrote:
   

Hi all,

I'd like to parse large csv file using combinator parser so I have the
following simple example:

class CSVParser extends Parsers {
 type Elem = Char

 var fnc: List[String] => Unit = l => ()

 lazy val item = elem("elem", c => {isLetterOrDigit(c) || c == '_'}).+
     

^^
   

{_ mkString("")}
 lazy val spaces = elem("elem", isSpace).*
 lazy val sep = spaces ~ elem(',') ~ spaces
 lazy val expr = item ~ (sep ~> item).* ^^ {case l ~ r => l :: r}
 lazy val exprs = ((expr <~ (elem('\r') ~ elem('\n'))) ^^ (fnc(_))).+

 def parse(in: java.io.Reader)(f: List[String] => Unit) {
   fnc = f
   exprs(StreamReader(in))
 }
}

I have a 64 MB csv file and I'm getting pretty soon:

Exception in thread "main" java.lang.StackOverflowError
   at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
   at scala.collection.immutable.Page.latest(PagedSeq.scala:220)
   at scala.collection.immutable.Page.latest(PagedSeq.scala:220)


The second thing is that if I read the file using a Java BufferedReader
     

and
   

feed to my parser line by line, it takes to parse 64MB in more then one
minute. A pure Java StringTokenizer approach takes about 5 seconds. Any
thoughts?

Are combinator parsers fitful for parsing large files?



Br's,
Marius

     

 

The scala 2.8 preview notes mention "efficiency" as a side-effect of using
packrat parsers in the parser combinator library:
http://www.scala-lang.org/node/1564.

I'm not sure however if that'll make a big difference on Marius use case.

Eric.

I wonder how Haskell combinator parsers "score" against Scala
combinator parsers.

The JVM JIT compiler seems pretty good these days, so I wonder if the
Scala combinator parsers aren't JIT friendly.

--
Regards,
Casey

I wonder how Haskell combinator parsers "score" against Scala
combinator parsers.

The JVM JIT compiler seems pretty good these days, so I wonder if the
Scala combinator parsers aren't JIT friendly.

--
Regards,
Casey

On Sunday September 27 2009, Casey Hawthorne wrote:
> I wonder how Haskell combinator parsers "score" against Scala
> combinator parsers.

I refer you to this message from earlier in this very thread:

On Sunday September 27 2009, Ben Hutchison wrote:
> ...
>
> Marius,
>
> Bernie Pope gave talk about Parser Combinators at Melbourne Scala
> User Group that discussed performance issues related to backtracking.
>
> See the following slides, esp slide 47
> http://www.cs.mu.oz.au/~bjpop/parser_combinators.pdf
>
> -Ben

> The JVM JIT compiler seems pretty good these days, so I wonder if the
> Scala combinator parsers aren't JIT friendly.
>
> --
> Regards,
> Casey

Randall Schulz

2009/9/28 Randall R Schulz :
> On Sunday September 27 2009, Casey Hawthorne wrote:
>> I wonder how Haskell combinator parsers "score" against Scala
>> combinator parsers.
>
> I refer you to this message from earlier in this very thread:

Thus, apart from empty hijacked threads, we now have recursive threads
too. Lets see what other types of threads are waiting to be found :)

>
> On Sunday September 27 2009, Ben Hutchison wrote:
>> ...
>>
>> Marius,
>>
>> Bernie Pope gave talk about Parser Combinators at Melbourne Scala
>> User Group that discussed performance issues related to backtracking.
>>
>> See the following slides, esp slide 47
>> http://www.cs.mu.oz.au/~bjpop/parser_combinators.pdf
>>
>> -Ben
>
>
>> The JVM JIT compiler seems pretty good these days, so I wonder if the
>> Scala combinator parsers aren't JIT friendly.
>>
>> --
>> Regards,
>> Casey
>
>
> Randall Schulz
>

On Monday September 28 2009, Jim Andreou wrote:
> 2009/9/28 Randall R Schulz :
> > On Sunday September 27 2009, Casey Hawthorne wrote:
> >> I wonder how Haskell combinator parsers "score" against Scala
> >> combinator parsers.
> >
> > I refer you to this message from earlier in this very thread:
>
> Thus, apart from empty hijacked threads, we now have recursive
> threads too. Lets see what other types of threads are waiting to be
> found :)

Judging from some lists I subscribe to,
infinite threads are a possibility.

> ...

RRS

I wonder how Haskell combinator parsers "score" against Scala
combinator parsers.

The JVM JIT compiler seems pretty good these days, so I wonder if the
Scala combinator parsers aren't JIT friendly.

--
Regards,
Casey