Lark: Improvement: Use Cython for Speed

[eddieschoute]

Having written a LALR parser for my language (https://github.com/eddieschoute/quippy) it still takes many seconds to parse a file of 100k LOC. One benchmark It takes very roughly 2m20s to parse a 600kLOC input file that I have, which is slow in my opinion. One straightforward improvement that I can think of is to use Cython to generate a C-implementation of the LALR parser. Most of the time seems to be spent in the main LALR parser loop, which can be significantly sped up by Cython. I would also be open to other suggestions to improve the parsing speed.

Since specifically the LALR parser is meant to compete in speed, I think it would be worth exploring the possibility of pushing this parser to its limit. Hopefully, converting the code to Cython code will be fairly painless and from there it just remains to optimize the functionality.

I do not know how the standalone parser will be affected by this, but I can image that instead of generating py files it should instead generate a pyx file that can be cythonized.

[erezsh]

Yes, that's a good idea. I played around with Cython a while back, and it sped up the LALR parser by about x2. I believe it's possible to go even faster..

The standalone parser is another issue, but I'm sure it can be solved.

[geographika]

@erezsh @eddieschoute - if this goes ahead I'd be happy to help setup AppVeyor to make Windows compatible builds and automate deployment to pypi.

[psboyce]

This is not a good idea, something this parsing library offers which nothing else has is the ability to create ridiculously portable parsers. The zipimport system used by Python allows you to make single executable parsers (as in a Python executable that consists of only one .zip file) that will run on literally any platform with a Python interpreter, batteries included, without requiring any compilation, configuration or setup. The zipimport system also makes the standalone parser superfluous as you can package Lark directly into the executable and the __main__ script can use pkgutil to pull in, say, a grammar file from within the archive.

If you need speed then use PyPy; in my experience you can get a 5x speedup with it for free when using Lark. If you're in a situation where slow compilation is costing you money and portability is not a concern then I would consider switching to a compiler compiler like Bison or Yacc.

If you want to add optional CPython/Cython extensions that are preferred over their pure Python counterparts that's a happy medium, however additional care will need to be taken to ensure the compiled extensions behave _exactly the same_ as their pure Python versions. This means writing unit tests for module APIs to make sure functions and classes remain in cohesion. If you want to retain support for PyPy with the compiled extensions that's yet another layer of new work.

The group of contributors for this project are loosely organized and small, and duplicating the functionality of existing modules in compiled extensions will double the project's workload. Maintaining the extensions in a manner that doesn't make life more interesting will slow down bug fixes and improvements in the future as changes will have to be mirrored between two functionally identical, yet syntactically different, source codes. Odds are you'll end up getting the extensions only partially complete, or modules will stop being maintained.

Or you could sacrifice zipimport and PyPy support for a modest speed improvement, a fatal blow to portability and a more complicated PyPI upload process. I say KIS.

[eddieschoute]

The use case for portability is not relevant to me, but I can see some use in it. But you do skirt around the issue of speed. While a 5x speedup is nice, perhaps much more is possible if Cython is used. It may be worth experimenting with in a separate branch, without "official support" yet to see if it is worth it. Moreover, it is possible to maintain support for a pure Python interpreter while also allowing Cython compilation speedups and annotations: http://docs.cython.org/en/latest/src/tutorial/pure.html

I can image than benchmarking the main loop and only typing that could provide the majority of the speed up. The main loop is only about 70 lines long so it should be fairly easy to experiment with.

[erezsh]

This looks like a controversial issue, so let me just say: Lark will never require a compilation step to install.

I'm also reasonably cautious of adding too many half-baked features to Lark. There is room for experimental features, but never at the expense of the common use case.

Having said that, I believe it's possible to explore using Cython for optimization, without violating that principle. If it proves worthwhile, it can be introduced either as an optional feature in Lark, or as a separate package that uses Lark.

And finally, that is only likely to happen if one of you "loosely organized" (joking) contributors picks it up, because I'd say my work queue for Lark is pretty full for the near future.

[eddieschoute]

I'm not sure how much it will help, but here is a snapshot of a profiling run on a medium-sized file (128k LOC) that I want to read more quickly. I briefly looked at Cython to see if a quick improvement was possible, but I think it would be necessary to start at the root, the lexer and the parse table and then work my way up to the parser. Plus it is also not possible to use generators in C so the current lexer generator structure, where new tokens are emitted, would have to be reworked to support pure C.

I'm actually not too sure why the lexer function itself is taking so much time. I would expect the regexes to take almost all of the time spent in the lexer. Perhaps it is possible to rewrite the lexer in some way (not necessarily Cython) to gain some speed?

[psboyce]

I'm willing to take a look at this later, if there's anything I know well it's Python's C API.

@eddieschoute I'm not sure what you mean by "is is not possible to use generators in C..." In C you can call the Python equivalent of next() on an interator until it's exhausted using PyIter_Next(), and you can also define extension types that are either iterable themselves or provide iterators using the tp_iter and tp_iternext slots.

[psboyce]

Wall of text containing my speculations, I think I have an angle on how to speed up the lexer and I'm willing to experiment.

This is the first 13 lines of a cProfile trace from clishmaclaver, the toy language I made to exploit an issue with Lark. The parser was fed 500,000 lines of source.

        85109145 function calls (85107239 primitive calls) in 113.752 seconds

  Ordered by: cumulative time

  ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    30/1    0.001    0.000  113.752  113.752 {built-in method builtins.exec}
       1    0.001    0.001  113.752  113.752 clishmaclaver.py:2(<module>)
       1    0.000    0.000  113.703  113.703 clishmaclaver.py:87(main)
       3    0.000    0.000  113.596   37.865 parser_frontends.py:35(parse)
       3   14.647    4.882  113.596   37.865 lalr_parser.py:32(parse)
       1    0.000    0.000  113.585  113.585 lark.py:196(parse)
 3501506   23.733    0.000   60.678    0.000 lexer.py:86(lex)
 4002000   15.948    0.000   33.506    0.000 lalr_parser.py:52(reduce)
 6502857   15.460    0.000   15.460    0.000 {method 'match' of '_sre.SRE_Pattern' objects}
 6502826    8.480    0.000   11.315    0.000 lexer.py:67(feed)
 3501519    6.724    0.000    8.633    0.000 lexer.py:28(__new__)
 2000914    4.092    0.000    8.365    0.000 parse_tree_builder.py:60(__call__)
11505506    5.941    0.000    5.941    0.000 lalr_parser.py:43(get_action)

About half the parser's time was spent in the lexer._Lex.lex generator, and a quarter of the time spent in the token generator was spent matching regular expressions. It looks like token matching is being done by merging regular expressions together into "mres" (I can only assume this means "multiple re") and iterating over the mres. Matching takes 2.4 µs per mre on average. If it were possible to iterate through the regular expressions in a tree or set like manner I believe this would cut down the time spent in _Lex.lex significantly. (I want to call _Lex.lex the tokenizer by the way, since that appears to be its purpose.)

There's also a good chance that a different regex engine can match individual expressions in less time than Python's re implementation, however these engines usually forgo features like backreferencing because they can lead to exponential behaviors in pathological cases. That shouldn't be an issue if these features aren't used by Lark.

Google's RE2 is a good candidate for a replacement re engine, it has an RE2::Set class that can be used to compile a collection of regular expressions together so iterating over each regular expressions isn't necessary; matching returns the indices of matching regular expressions. It's also written in C++, so writing a bridge for Lark in C++ or Python would be necessary.

Other things in lexer.py I've noted; Token is a really good candidate for reimplementation in a C extension because it subtypes the unicode built-in. This might improve the time it takes to create new Tokens.

I think the tokenizer _Lex.lex is also a good candidate for C reimplementation, however for best results I think the tokenizer will need to be refactored as a pure generator function instead of a class and the build_mres step will need to be moved into the tokenizer. This way the tokenizer, the Token type and anything the tokenizer needs to do before emitting tokens can be relegated to a new Python module. An alternate implementation of the new module can then be written as a C extension, and instead of using mres it can use RE2, or perhaps something else entirely.

I wanted to jot my thoughts down here before writing code, it's still a large task but I think it's manageable. RE2 is a promising library for a C++ extension, and writing unit tests for Token and the tokenizer won't be as bad as I thought initially.

[eddieschoute]

For a pure python solution it may be worth trying regex instead of re which is a reimplementation of re. It has a group limit of 500 apparently (https://stackoverflow.com/a/14391579/1517171) or maybe even larger (https://stackoverflow.com/a/10798598/1517171) so it may not be necessary to split the regex. Plus it may contain other optimisations.

[psboyce]

regex doesn't appear to be pure Python, and the only wheels available on PyPI are for Windows. Are you referring to another package with the same name?

[erezsh]

Python's re is written in C, so only native compiled libraries will outperform it.

I'm doubtful that re2 will be faster for the common use-case, since its focus is on improving the worst-case performance. But this is all very easy to test.

[drslump]

Regarding cython, a quick way to check if it can yield something is with its pure python mode, you just create a .pxd file annotating the module's functions.

Anyhow, lurking on the re sources I found this undocumented Scanner class. It's probably of no use directly but it shows how to interact directly with the C extension's scanner.

Looking at the sre sources, it should be a bit faster than the current approach via pattern.match since it only allocates the internal state once. Probably only noticeable when parsing very large documents though.

Quickly testing it yields the following with the python example:

    ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    >>> regexp.match
    73488    0.145    0.000    0.145    0.000 {built-in method match}
    44842    0.137    0.000    0.384    0.000 lexer.py:88(lex)       
    >>> regexp.scanner.match
    56952    0.129    0.000    0.129    0.000 {built-in method match}
    44842    0.122    0.000    0.366    0.000 lexer.py:88(lex)

It's not that bad actually, but it would have to be made to work with the Contextual lexer and check if Pypy supports that undocumented feature too.

[psboyce]

I have the Token class's constructor working in a C extension, instantiating new tokens takes a quarter of the time in C as it does in Python;

>>> timeit("Token('HELLO', 'world!')", "from lark.tokenizer.py_tokenizer import Token", number=10**7)
18.843468595994636
>>> timeit("Token('HELLO', 'world!')", "from lark.tokenizer.cpp_tokenizer import Token", number=10**7)
5.160433470038697
>>> 18.8435 / 5.1604
3.6515580187582355
>>> 5.1604 / 18.8435
0.27385570621169103

I still have to write the methods for the Token class, then I'm going to continue with the LineCounter and Tokenizer classes proper. (formerly _Lex.lex) I'm still planning on using the RE2 library for the Tokenizer class, if I find it doesn't give a very large performance boost I may try the Hyperscan library.

[drslump]

Tried a few approaches to speed up the lexer, all speed ups are only for the lexing phase not the whole parsing:

Jump table

Analyze each pattern to see if it starts with a literal, if it does find all other patterns that start with the same literal or don't start with one (ie: /[a-z]+/), then build an "mres" with them and store it in a dict with the literal as key.

When processing a character check if it's on the literal dict, if so run match with its specific mres, otherwise use the default.

Roughly a ~8% speed up. It could probably go higher if the analysis takes into account ranges and so on. It could also avoid running a regex completely if there are no other pattern candidates.

re.sub

One issue with using a regex is that for each token we create a new regex state to parse the stream. To avoid it we can pass a replacement function to regex.sub, this allows to collect all the matches in the input and when it's over yield the tokens.

About a 7% speed up. It's quite a hack though, and doubles the memory required for the input.

regex captures

Using the alternative regex extension, it has a feature called captures that allows to collect multiple values for a repeating capture group (ie: /((?P<foo>)\w+))+/). This allows to run the regexp continuously for a batch of tokens (around 500 seems to give the best results).

When the batch completes we collect the matched tokens, sort them according to their start position, and then yield the tokens.

About 18% speed up, the downside is that it's not in the stdlib.

---

Overall I think the jump table approach could be explored further but I don't expect a huge speed up (probably around ~10%). If the lexer is a bottleneck it's probably due to the patterns used in the grammar, the python re module doesn't optimize the pattern at all so there is going to be a lot of backtracking. For instance, I'm getting a 5% speed up just by defining the common grammar CNAME as /[A-Za-z_][A-Za-z0-9_]*/, so when defining a term it's best to rely on a regex directly instead of composing with other terms.

[erezsh]

I'm getting a 5% speed up just by defining the common grammar CNAME as /[A-Za-z_][A-Za-z0-9_]*/,

If that's really the case, we can optimize them ourselves (at least in some cases). The CNAME example is especially easy to solve, seeing how load_grammar.py already has the transformers for it.

[erezsh]

I'd like to weigh in regarding this discussion, without going into any specific suggestion:

Lark's performance is very important me, but the readability and simplicity of the code is important to me as well. A clean and simple code base is easier to maintain, has less bugs, and is more likely to invite future contributions.

So as a general rule, I'm not very keen on optimizations that significantly complicate the code for a very small performance reward.

This is also why I like the idea of using Cython - the boost is potentially huge (I'll bet a 10x boost is possible, if done correctly), and the resulting complications can reside in a separate, optional module. And if anyone wants to understand how it works, or if there's an uncertainty about what is the correct behavior, there will always be a clean Python reference implementation to refer to.

I'm also toying with the idea of writing a pure-C implementation of the lexer & LALR parser, that will be generated by the standalone tool, and interface with Python for outputting the AST (either with Cython or ctypes). The performance difference between a loop with dict-lookups vs a loop with switches and gotos is potentially huge. I'm just putting it out there, but it probably won't happen anytime soon.

[drslump]

I agree that it's not worth it to complicate the lexer too much just to make it slightly faster. The only way to improve it substantially is going with native code, specially if there are no regexes at that step. Even if using Cython or some custom C code the problem with backtracking is going to be there. My opinion is that if there is a generation step for the lexer it should dump something for re2c, which is commonly available and should be faster than most manually written lexers.

The other problem is how to avoid the excessive chatting between the native C code and the python code while scanning. However given the current design of the lexer I don't see a clear way to solve it. Ideally the lexer could hold a context in the C side with all the data and the Python side would get the details of individual tokens on demand instead of marshalling all of them during the scan. This reduces the work needed for many tokens like whitespace or punctuation for which we don't really care about their value.

That said, some low hanging fruit from my tests that improve a bit the current lexer:

• Avoid inheriting from str for Token. Its creation is 40% slower on my tests vs a slots based class.
• Use optimized regexes on the common grammar, since it's probably used by everyone for one thing or another.
• Use .scanner(stream).match instead of .match on the loop

[drslump]

I bring some news, after playing with re2c I checked the output and saw that it was generating really simple finite state machine. I then checked the opcodes generated by Python when doing simple comparisons and it wasn't too efficient for building a FSM. So I took it a step further and built a simple FSM compiler that generates a compiled function from custom bytecode.

Experiment files: https://gist.github.com/drslump/55752165288b7639b06f60888e22c759

I'm getting speed ups of over 20%, although with unicode it's very important to make sure Python is not doing encoding conversions under the hood.

The generated opcodes are the bare minimum, this is an example of a comparison + jump:

LOAD_FAST ch
LOAD_CONST '0123456789'
COMPARE_OP 'in'
POP_JUMP_IF_TRUE label

While the FSM compilation approach might be a bit too much just to optimize a lexer, I think it's worth pursuing given that:

• It builds on re2c, so a C extension lexer can be also generated quite easily
• It could be extended to be used for the LALR parser

[drslump]

I've put together a repo with the experiments at https://github.com/drslump/lark-lexer-experiments

It compares the current lexer implementation based on building a regexp with the different token expressions with the re2c based finite-state-machine bytecode generation and a C extension.

The finite-state machine approach is surprisingly good providing a ~50% speed up over the regex one. The C extension is obviously faster with a 300% speed up, but it can go up to 500% if it consumes all the tokens and returns a list when it's done.

Overall I think that relying on re2c to generate a high performant lexer is a good approach, it's an extra dependency but it produces very fast lexers. The FSM approach requires a preprocessing step but the result is platform independent, so it can be shipped with the code without requiring any compilation. Of course that for the highest performance the C extension is the way to go.

The only big piece missing, besides handling unicode correctly, would be to implement the transform from the perl flavour regexes used in Lark grammars to the format understood by re2c. Not all regexes could be transformed though.

-------------------------------------------------------------- benchmark: 4 tests -------------------------------------------------------------
Name (time in us)            Min                   Max                  Mean              StdDev                Median               OPS
-----------------------------------------------------------------------------------------------------------------------------------------------
test_cseq               442.9817 (1.0)        757.9327 (1.0)        483.4539 (1.0)       26.1906 (1.0)        478.0293 (1.0)  2,068.4495 (1.0)
test_c                  790.1192 (1.78)     1,079.7977 (1.42)       822.6287 (1.70)      40.6050 (1.55)       796.0796 (1.67) 1,215.6152 (0.59)
test_fsm              1,598.8350 (3.61)     1,986.0268 (2.62)     1,677.9255 (3.47)      88.4932 (3.38)     1,627.9221 (3.41)   595.9740 (0.29)
test_regex            2,313.8523 (5.22)     2,911.8061 (3.84)     2,500.1628 (5.17)     128.5901 (4.91)     2,499.1035 (5.23)   399.9740 (0.19)
-----------------------------------------------------------------------------------------------------------------------------------------------

By the way, if someone could try it on Pypy I'll appreciate it, I can't seem to install it on my laptop for some reason. I'm eager to see the results, if the FSM function is elegible for its JIT (it's kind of big so not sure if they skip based on size), the performance should be really close to the C extension.

[erezsh]

@drslump Very cool! Any chance you can add PyPy to the benchmark? (with sufficient warm-up time)

[drslump]

@erezsh the lexer used on the FSM to parse the C code generated by re2c is failing under PyPy (2.7-5.10.0):

            else:
                if line_ctr.char_pos < len(stream):
>                   raise UnexpectedInput(stream, line_ctr.char_pos, line_ctr.line, line_ctr.column)
E                   UnexpectedInput: No token defined for: ':' in ':\n   ' at line 69 col 3

It would be great if you could have a look and see if you can spot the problem.

For the other lexers, as expected the Regex based one is the fastest and competitive with the C extension with CPython.

--------------------------------------------------------------------------------------------- benchmark: 3 tests --------------------------------------------------------------------------------------------
Name (time in us)            Min                     Max                  Mean                 StdDev                Median                   IQR            Outliers       OPS            Rounds  Iterations
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_regex              610.1131 (1.0)       17,050.0278 (1.0)      1,058.4620 (1.0)       1,816.9326 (1.0)        761.9858 (1.0)        168.8004 (1.75)       50;106  944.7670 (1.0)        1601           1
test_cseq               748.1575 (1.23)     789,040.0887 (46.28)    2,210.9609 (2.09)     23,217.3401 (12.78)      823.9746 (1.08)        96.3211 (1.0)         2;223  452.2920 (0.48)       1425           1
test_c                1,584.0530 (2.60)      29,750.8240 (1.74)     3,318.7148 (3.14)      4,182.2400 (2.30)     1,857.9960 (2.44)     2,131.3429 (22.13)       24;24  301.3215 (0.32)        621           1

[drslump]

I generated the FSM structure with CPython and loaded it with PyPy and the results are very impressive, I was expecting it to be fast but it's really incredibly fast 😳

---------------------------------------------------------------------------------------------- benchmark: 4 tests ---------------------------------------------------------------------------------------------
Name (time in us)            Min                     Max                  Mean                 StdDev                Median                   IQR            Outliers         OPS            Rounds  Iterations
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
test_fsm                 98.9437 (1.0)       16,355.0377 (1.0)        182.1235 (1.0)         679.1908 (1.0)        102.9968 (1.0)         15.9740 (1.0)      138;1837  5,490.7793 (1.0)       10107           1
test_regex              608.9211 (6.15)      17,454.8626 (1.07)     1,068.3822 (5.87)      1,766.2271 (2.60)       761.9858 (7.40)       175.4761 (10.99)      49;139    935.9947 (0.17)       1648           1
test_cseq               725.0309 (7.33)     791,435.9570 (48.39)    2,657.4733 (14.59)    27,917.2280 (41.10)      812.7689 (7.89)       116.8251 (7.31)        3;229    376.2973 (0.07)       1363           1
test_c                1,587.1525 (16.04)     29,666.9006 (1.81)     3,407.8027 (18.71)     4,253.6592 (6.26)     1,894.9509 (18.40)    2,256.1550 (141.24)      24;24    293.4442 (0.05)        616           1
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

[erezsh]

Wow, that's amazing. I knew PyPy is good, and I've long held the intuition that using its JIT to run state-machines might outperform C, but this is so much faster that I think it might be a mistake?

Does your test make sure that it produces the correct result?

[drslump]

@erezsh yes -> https://github.com/drslump/lark-lexer-experiments/blob/master/benchmark.py#L111

I agree that it's a great result, although the generated state machine is very simple, mostly forward jumps and a few local variables without function calls. It might well be though that PyPy's optimizer is clever enough to know that the lexer results aren't being actually used and the function gets optimized away.

[drslump]

@erezsh I have matured the implementation of the re2c based finite-state machine lexer and it's now able to transform the regexes to the expected format and generate the lexer on the fly (if re2c is available) or pregenerate it for distribution.

There is quite a bit of code, so before trying to move it into Lark and implement some tests I would prefer to have your feedback. The main parts are:

• Assembler: A minimal abstraction over Python's opcode handling features. For a "standalone" distribution this is basically the only code required.
• FSM: Builds on the assembler and implements some basic actions for implementing a finite state machine. Right now used for the lexer but it should serve as well for the LALR parser.
• re2c: package to transform the grammar, run re2c and build a python FSM from the result. It has a command line tool for generating the standalone driver but can also do the process transparently.

It's not clear how to make a custom lexer fit the current interface in Lark, it would require some changes and I was thinking that perhaps these changes shouldn't be backwards compatible and instead target a new major version. There is some performance to be gain still by changing how Token is implemented, avoiding the inheritance from Str.

Check out this approach, the tokens reference a LexicalInfo instance that is the one recording the line numbers, allowing the token to be lighter with only a char offset. potentially the token "value" could also be deferred to the LexicalInfo instance and just store the length, so the string slicing (expensive) is only performed if the value is actually used (whitespace, symbols and keywords are actually seldom required in practice).

By the way, for the Python2 grammar the FSM approach is 75% faster, probably more since keywords are not properly modelled (no callbacks) on the regex based bench. Also interesting that on PyPy the fsm lexer is only 200% faster than the regex one, it seems that now that it uses a couple more local variables the JIT is not able to optimize it so nicely. I'm confident that it could be tuned, although it's very fast already.

[erezsh]

@drslump
This is very ambitious and impressive. But at the same time, I have some reservations about taking this approach (vs writing it in C and adding bindings). It boils down to two points:

1) For CPython, which is the vastly more popular interpreter, the C code is the fastest. Also, you didn't demonstrate that the PyPy FSM is faster than C. Understandably, because the currently implementation weaves in-and-out between C and PyPy, there will be considerable slowdown (Also true to a lesser degree with CPython, which is why cseq is twice as fast). However, my vision is that in the final version the lexer and the parser will both be in C so there won't be any barrier between them. The interface to Python will be in the Tree layer, which will require less C calls than a lexer. And perhaps, as an additional mode when memory isn't of issue, it could be done with a single call (and one big data transfer).

2) The implementation is a little fragile. AFAIK Python's bytecode isn't compatible between minor releases, let alone 2 vs 3 vs PyPy, which means it will probably require a lot of special cases, and an update every time there's a new minor release of Python. And there's also re2c, which probably doesn't promise to maintain the same file structure & format; they only care that it compiles and runs. The end result is that this approach will probably require a lot of maintenance and attention to edge-cases.

Having said that, I would really like to see how far this experiment can go. It would be very cool to benchmark a jitted fsm of lexer+parser vs C code.

But I think both approaches (C and FSM) would be better off in separate repos that use Lark, since they're both rather big projects, with their own dependencies, and possibly with a slightly different interface than Lark (ideally it would stay exactly the same, but that seems unlikely). They will focus on speed, while Lark focuses on ease of use. I'm probably going to move Lark into its own github organization soon, so we can create the new repos under same organization.

What do you think?

P.S.
Regarding the code, I have a few comments about the style, but the structure and approach seem good at a first glance.

P.P.S. Your FSM bytecode generator might be worth turning into an independent project someday.

[drslump]

Thanks for the detailed response @erezsh!

About the second point, just to clear it up, while Python's bytecode does indeed change quite frequently, its opcodes (eval loop actions) do not, the "assembler" relies on the standard dis module to ensure it's compatible across different versions (including Pypy). The only difference that is not handled by dis is how the opcodes are encoded in binary, which indeed has changed with CPython 3.6 (wordcode instead of bytecode).

In general I tend to agree that a C extension that handles efficiently the whole lexing+parsing would be a nice feature, offering a clean path to maximum performance once the user has a working parser. However, the ability to distribute a fully portable parser, without compilation steps, that gives the best performance possible feels like a killer feature for anyone planning on using a parser on their library.

My suggestion if you want to go deep into the C path would be to model it like the CPython's re module, having a low level C virtual machine for handling the expensive lexing/parsing. This allows to publish pre-built versions on Pypi, which should provide very good performance without the inconvenience of having to build/distribute a generated, grammar specific, C extension.

[jayvdb]

https://pypi.org/project/regex/#files regex still only has windows wheels.

Another regex library is rure (Rust RE) which has wheels for linux and osx, but not yet for Windows. https://pypi.org/project/rure/#files It promises linear performance.

It is a drop in replacement except that it refuses arbitrary look-ahead and backreferences. e.g. it first of all barfs at terminal OP which is '[+*][?]?|[?](?![a-z])' . The next terminal to fail will be REGEXP defined as /(?!/)(\\/|\\\\|[^/\n])*?/ . If these could be expressed without the look-ahead, it might be a viable solution, and the maintainer is interested in automating their build system so I guess Windows wheels support would be part of that.