Hand-written lexer in Javascript compared to the regex-based ones

http://eli.thegreenplace.net/2013/07/16/hand-written-lexer-in-javascript-compared-to-the-regex-based-ones/

by joeyespo • 13 years ago

81 22 13 years ago

eli.thegreenplace.net

kryptiskt• 13 years ago

An oddity in this lexer is that it allows numbers followed by an identifier with no separation: "99foo" turns into two tokens, number "99" and identifier "foo".

ksherlock• 13 years ago

That's fairly common in languages that aren't particularly whitespace sensitive.

vstm• 13 years ago

Agreed. The lexer just recognizes tokens it does (usually/ideally) not know about the grammar, the parser checks if the "token stream" actually complies with the grammar.

If the grammar allows for example "2x" as a "shortcut" for "2 * x" (if you parse mathematical expressions) it would make sense.

Nitpick: Depending on the syntax the lexer might also yield 99f (float literal) and the identifier "oo".

eliben7• 13 years ago

This is normal for lexers in whitespace-insensitive languages. In spirit this is similar to allowing "foo+" (plus after "foo") or any other token concatenation.

If this is an error in the language, the parser easily catches it.

Some languages AFAIR allow "units" to be attached to numbers so some use cases are actually valid. In any case, it's a higher-level decision the parser makes.

mikeash• 13 years ago

C, for example, allows trailing letters to specify the type of a numeric literal:

    42 // int
    42U // unsigned int
    42LL // long long
    42ULL // unsigned long long
    42.0 // double
    42.0f // float

Edit: except that whitespace isn't allowed here. "42 LL" is not legal. So that's kind of the opposite case!

quacker2• 13 years ago

I'm not surprised the hand-written version is faster. You need to store an object for each regex. If these objects are DFAs, for example, then there is a considerable amount of overhead storing the graph to represent the DFA. The hand-written version has comparatively little state, and no generalized logic which would further slow it down.

Error-reporting is another good reason for hand-written lexers (and parsers). It's harder to get readable and accurate error messages when the logic is embedded in the regex or some library/framework.

EDIT: The link posted in the comments of the article is great. From Rob Pike:

A regular expression library is a big thing. Using one to parse identifiers is like using a Ferrari to go to the store for milk.

http://commandcenter.blogspot.com/2011/08/regular-expression...

eliben7• 13 years ago

I'm not surprised the hand-written version is faster. You need to store an object for each regex. If these objects are DFAs, for example, then there is a considerable amount of overhead storing the graph to represent the DFA.

I'm not sure what this means specifically.

Presumably, the DFA is created once and then only some sort of small state has to be maintained (i.e. which state we're in, perhaps a little more). It's not like a bunch of heavy-wight regex objects have to be created for each input character.

quacker2• 13 years ago

I meant, you have a number of regular expressions, and each gets compiled (e.g. by calling re.compile in Python), so you have one DFA per regex.

At least in Python, there are also transient objects created whenever you match something with the regex (e.g. calling regex.match).

It's not like a bunch of heavy-wight regex objects have to be created for each input character.

I'm not familiar with the Python or JavaScript implementations. Abstractly, if the DFA is just a graph (nodes and edges), then you would need to store something for every node and every edge. This could be an object per character (depending on the implementation and the regex, I suppose?). EDIT: I'm confusing myself. Each node represents a state. The characters would be on the edges. You would need to store a set of characters for every state.

I just had this fuzzy notion that each regex requires a bit more state and a bit more logic than a handwritten version, so the hand-written version could very well be faster.

kkowalczyk• 13 years ago

The reason you should be surprised is this: regular expressions are implemented in C. In some implementation they are even jit'ed.

It's a testament to how good V8 is that char-by-char loop is faster in JavaScript than optimized C code but if you were to benchmark pre-V8 JavaScript interpreters or current implementations of Python or Ruby, regex matching would smoke char-by-char loop written in the language simply by virtue of being C code.

jlarocco• 13 years ago

No. This isn't too surprising to anybody who knows how regular expressions work under the hood. The hand rolled parser is asymptotically faster than using regex. It wouldn't surprise me at all if the hand rolled parser were still faster for a complicated enough language and a large enough input file.

It's analogous to a hand optimized assembly language implementation of bubble sort being slower than quicksort in a slow, high level language. At some point the bubble sort will lose, simply because it's asymptotically worse.

azakai3• 13 years ago

The benchmark here is on a large document, but it is very short-running. Would be interesting to see something even larger. The regex engine might not decide to JIT for short-running code, for example, not sure how that works.

eliben7• 13 years ago

Is that decision time-based? Because in terms of exercising the regexen and hand-written functions, they are surely run many thousands of times.

I've concatenated a number of Tablegen files together (the benchmark is described better here: http://eli.thegreenplace.net/2013/06/25/regex-based-lexical-...) for a total of ~20KLOC, so we're talking about tens of thousands of tokens here (around a megabyte of data). That sounds like enough to kick the JITs, don't you think?

azakai3• 13 years ago

I honestly do not know how regex JITs are tuned, but in JS JITs, even tens of thousands of iterations may not suffice.

Just to be sure, I would concatenate some more stuff ;) so the test runs for say 10 seconds.

Hand-written lexer in Javascript compared to the regex-based ones

Related Stories