[antlr-interest] Lexer speed comparison

[Ric Klaren]

On Wed, Feb 25, 2004 at 10:59:30PM -0000, Uli Bubenheimer wrote:
> I ran some tests comparing Lexers generated by different tools in
> terms of speed. The sophistication of my Lexer specification that I
> used as input for the Lexer generators is about that of a lexer for C.
> The average numbers I found by repeatedly running the generated lexers
> on a large source file were these:
> 
> ANTLR           8300ms
> JLex            6500ms
> JFlex 1.4pre5   2000ms
> Flex            1900ms
> 
> I was surprised to find that ANTLR generated the slowest lexer.

Not very surprised myself ;) ANTLR generates horrible code for lexers. I'm
not sure how big the impact is of the recursive descent parsing/lexing
style, but I would not be surprised if I could handoptimize an ANTLR lexer
to the level of JLex. ANTLR generated code is wasting a lot of time calling
match methods where the outcome is already known.

BTW it's a pity you did not test C++ mode next to the Java mode.

> Naturally, when interpreting these numbers keep in mind that the
> outcome may have been different on a different lexer specification or
> lexer input text. On the other hand, it makes sense to me that a DFA
> would be faster on average than a more powerful recursive-descent parser.
>
> Are there other performance numbers available? I have not been able to
> dig up anything substantial. I also wonder how ANTLR-generated LL(k)
> parsers perform compared to LALR(1) parsers.

Not much only some random tests done by people over time. It would be nice
if you could share the input files for these lexers for future reference.

Cheers and thanks for sharing this info!

Ric
-- 
-----+++++*****************************************************+++++++++-------
    ---- Ric Klaren ----- j.klaren at utwente.nl ----- +31 53 4893722  ----
-----+++++*****************************************************+++++++++-------
   Words fly like arrows
      as if we knew what was right and wrong. --- Chuang Tsu



 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
     http://groups.yahoo.com/group/antlr-interest/

<*> To unsubscribe from this group, send an email to:
     antlr-interest-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
     http://docs.yahoo.com/info/terms/