6 ms·

Syntax extensions and regular expressions for Rust

126 points by dbaupp 13y ago

Ygg2 13y ago
How does this compare to other regex parsing libraries, performance wise?
- deleted 13y ago
  [deleted]
- charlieflowers 13y ago
  He gives a link to this at the bottom: https://github.com/BurntSushi/regexp/tree/master/benchmark/regex-dna https://github.com/BurntSushi/regexp/tree/master/benchmark/r... (You have to scroll down to the code block sections to see the numbers). Rust beats Go pretty soundly (on this specific benchmark), but C beats Rust pretty soundly. Why is C so much faster?
  - innguest 13y ago
    > Why is C so much faster? Because processors are made with C in mind, as it's the lingua franca, and so they end up being optimized for it.
    - Ygg2 13y ago
      Ok, but why is Python faster than Rust implementation? (And yes, I assume those are C libs behind python). NOTE: Rust is supposed to have zero cost abstractions. I think this is more to lack of optimization on regexp part, than some fault of language.
      - dbaupp 13y ago
        The Rust implementation hasn't been extensively microoptimised.
    - pcwalton 13y ago
      > Because processors are made with C in mind, as it's the lingua franca, and so they end up being optimized for it. No, Rust exposes the C memory model pretty directly, and it uses the backend of an industrial-strength C++ compiler (clang/LLVM). The difference here is algorithmic. (Rust does have some codegen bugs that affect performance, however, though I suspect they won't affect this code.)
  - burntsushi 13y ago
    Yeah, this is really the only comparison I have so far. It was included with a PR for adding regexes to Rust, so hopefully it will make it into the shootout proper in the next release. I also have some more specific benchmarks against Go: https://github.com/BurntSushi/regexp/tree/master/benchmark https://github.com/BurntSushi/regexp/tree/master/benchmark (For any curious readers out there, the benchmark is multithreaded in Rust[1], with a particularly nice use of futures.) > Rust beats Go pretty soundly (on this specific benchmark), but C beats Rust pretty soundly. I believe the dynamic regexes also beat Go on this specific benchmark, but the optimizing compiler is likely to blame there. (And to be clear, Go still beats Rust native regexes in some benchmarks, primarily because it has more clever optimizations. It was written by Russ Cox, after all!) > Why is C so much faster? The C program is pretty elaborate, but here are my guesses. * There are many ways to implement regex matching. For example, RE/C++ uses both a very very quick DFA and a NFA simulation. My library only has the (slower) NFA simulation. I don't know what Tcl uses for an implementation strategy, but whatever it is, it's likely a factor. * If string replacement is done in place, then it's going to avoid a good chunk of allocation. (In this particular benchmark, it would be perfectly legal to do string replacement in place.) I'm sure there are other things I'm missing, but these seem like good candidates for a good chunk of the difference. [1] - https://github.com/BurntSushi/regexp/blob/master/benchmark/regex-dna/regex-dna.rs https://github.com/BurntSushi/regexp/blob/master/benchmark/r...
thristian 13y ago
The author asks about other languages with "native" regex implementations, and I'm not entirely sure whether PyPy counts. Like regular Python, it compiles regexes into a bytecode-based virtual machine, but like just sprintf-style string formatting and the rest of Python in general, the regex VM is JIT-compiled into native code.
- gsnedders 13y ago
  Plenty of implementations have JITing regexp implementations. PCRE nowadays has a JIT mode, so any VM embedding PCRE for their regexp has such a thing, likewise all the JS engines have their own custom JIT implementations.
- burntsushi 13y ago
  Author here. I don't know enough about PyPy to really answer your question with any certainty, but I have some guesses. Firstly, it's my understanding that JITing pays a runtime cost. That's not the case with Rust compiled regexes. (Admittedly, this cost is likely negligible.) Secondly, wouldn't PyPy JIT the general matching algorithm? This seems like a substantively different process than doing code generation specifically for a regex whose structure you know at compile time. (Whether I'm currently taking advantage of any optimizations that PyPy's JIT isn't is of course a different story.)
  - thristian 13y ago
    PyPy uses a tracing JIT, so it observes the general matching algorithm for a few iterations and then emits code that implements what the general algorithm actually did, i.e. the specific matching steps for that specific regex. JITting a regex isn't really the same thing as your Rust native regexes; for example, if somebody wrote a regex library with a JIT and linked it to a C program, I woudln't count it. However, in PyPy's case regexes are exactly as native as the rest of the codebase rather than being a nested VM, so in that sense they're 'native'.
sixbrx 13y ago
Very impressive. Especially the native regexs which will fail at compile time if they are invalid and which compile to a custom matcher machine (without having to express them in nasty template syntax). Rust has more macro-chops than I suspected.
pohl 13y ago
Aside from Servo itself, this is the coolest and most ambitious piece of Rust code I've yet seen. I haven't had the pleasure of using a language with a good macro facility. What other sorts of applications do macros have, aside from this and type safe println are there? Could one make a json or XML parsing library with this technique? Or a driver for a database? How does one go about acquiring an intuition for when to use or not use them?
- burntsushi 13y ago
  Thanks for your kind comments. :) > How does one go about acquiring an intuition for when to use or not use them? Truthfully, I don't know. In this particular case, the benefits seem really clear: we get safety and performance increases. But here's a caveat: the particular reason why this works well for regexes is because the common use case is to write the string literal corresponding to the regex into your program. This is what allows the macro facilities to kick in. For example, if the regex is derived from user input at runtime, then the `regex!` macro can't be used. i.e., you can't do this: let restr = "a*"; let re = regex!(restr); The `regex!` macro must accept a string literal (or another macro invocation that produces a string literal).
  - pohl 13y ago
    I see. So maybe if you had a fixed XSD or XSLT at compile time you could emit a faster but specialized parser or transformer. But maybe that wouldn't work out so well in practice. I did find an interesting slide deck from the scala universe that mentions something like F# type providers (among other things) as possible applications. http://scalamacros.org/paperstalks/2014-02-04-WhatAreMacrosGoodFor.pdf http://scalamacros.org/paperstalks/2014-02-04-WhatAreMacrosG...
- rca 13y ago
  I think you would ask yourself : can I compute this at compile time? (And is it useful to do so?) I don't really see how you could use that for a database driver, but for example you could create a library that uses macros to generate custom serialization/deserialization code to/from json (or whatever format) for your data structures. (Edit: after a quick check this use case seems to be already covered by #[deriving(Encodable, Decodable)] in rust.)
Dewie 13y ago
Is this implementation close to the theoretical concept of regular expressions? I have read that some implementations of regular expressions are quite a bit more powerful than regular expressions from CS, in that they can recognize languages that are not regular.
- burntsushi 13y ago
  Yes. It's a reasonably faithful port of RE2, which elides features like backreferences.
  - pjscott 13y ago
    This is usually a small price to pay for guaranteed O(n) matching speed. (Kudos to the author for doing the Right Thing here.)
    - burntsushi 13y ago
      Thanks :-) The implementation is basically the Pike VM as described by Russ Cox. Recursion depth in particular has an upper bound corresponding to the number of instructions in the regex. In practice, this means it's safe to run a regex on untrusted data. (Creating a regex from untrusted data still needs a bit of work, but is fixable!)
jeffdavis 13y ago
Impressive. I like how the rust community is offering so many good examples of real utility for the language. Some languages are a little heavy on theory but have trouble connecting with potential users; and other languages are popular but have a lot of problems due to fundamental weaknesses. Rust, and its community, seems to have a good balance. Good theoretical foundation, but a lot of people always working to show some practical reason to care about the theory.
CyberShadow 13y ago
Would be interesting to see a benchmark between D's ctRegex and Rust's "regex!". IIRC, when ctRegex was announced, it beat all other contestants (including V8's JIT-ed REs) in the author's benchmarks. There will be a talk at this year's D conference on D's implementation of regular expressions: http://dconf.org/2014/talks/olshansky.html http://dconf.org/2014/talks/olshansky.html

126 points by dbaupp 13y ago

Ygg2 13y ago

How does this compare to other regex parsing libraries, performance wise?

deleted 13y ago
[deleted]
charlieflowers 13y ago
He gives a link to this at the bottom: https://github.com/BurntSushi/regexp/tree/master/benchmark/regex-dna https://github.com/BurntSushi/regexp/tree/master/benchmark/r... (You have to scroll down to the code block sections to see the numbers). Rust beats Go pretty soundly (on this specific benchmark), but C beats Rust pretty soundly. Why is C so much faster?
- innguest 13y ago
  > Why is C so much faster? Because processors are made with C in mind, as it's the lingua franca, and so they end up being optimized for it.
  - Ygg2 13y ago
    Ok, but why is Python faster than Rust implementation? (And yes, I assume those are C libs behind python). NOTE: Rust is supposed to have zero cost abstractions. I think this is more to lack of optimization on regexp part, than some fault of language.
    - dbaupp 13y ago
      The Rust implementation hasn't been extensively microoptimised.
  - pcwalton 13y ago
    > Because processors are made with C in mind, as it's the lingua franca, and so they end up being optimized for it. No, Rust exposes the C memory model pretty directly, and it uses the backend of an industrial-strength C++ compiler (clang/LLVM). The difference here is algorithmic. (Rust does have some codegen bugs that affect performance, however, though I suspect they won't affect this code.)
- burntsushi 13y ago
  Yeah, this is really the only comparison I have so far. It was included with a PR for adding regexes to Rust, so hopefully it will make it into the shootout proper in the next release. I also have some more specific benchmarks against Go: https://github.com/BurntSushi/regexp/tree/master/benchmark https://github.com/BurntSushi/regexp/tree/master/benchmark (For any curious readers out there, the benchmark is multithreaded in Rust[1], with a particularly nice use of futures.) > Rust beats Go pretty soundly (on this specific benchmark), but C beats Rust pretty soundly. I believe the dynamic regexes also beat Go on this specific benchmark, but the optimizing compiler is likely to blame there. (And to be clear, Go still beats Rust native regexes in some benchmarks, primarily because it has more clever optimizations. It was written by Russ Cox, after all!) > Why is C so much faster? The C program is pretty elaborate, but here are my guesses. * There are many ways to implement regex matching. For example, RE/C++ uses both a very very quick DFA and a NFA simulation. My library only has the (slower) NFA simulation. I don't know what Tcl uses for an implementation strategy, but whatever it is, it's likely a factor. * If string replacement is done in place, then it's going to avoid a good chunk of allocation. (In this particular benchmark, it would be perfectly legal to do string replacement in place.) I'm sure there are other things I'm missing, but these seem like good candidates for a good chunk of the difference. [1] - https://github.com/BurntSushi/regexp/blob/master/benchmark/regex-dna/regex-dna.rs https://github.com/BurntSushi/regexp/blob/master/benchmark/r...

thristian 13y ago

The author asks about other languages with "native" regex implementations, and I'm not entirely sure whether PyPy counts. Like regular Python, it compiles regexes into a bytecode-based virtual machine, but like just sprintf-style string formatting and the rest of Python in general, the regex VM is JIT-compiled into native code.

gsnedders 13y ago
Plenty of implementations have JITing regexp implementations. PCRE nowadays has a JIT mode, so any VM embedding PCRE for their regexp has such a thing, likewise all the JS engines have their own custom JIT implementations.
burntsushi 13y ago
Author here. I don't know enough about PyPy to really answer your question with any certainty, but I have some guesses. Firstly, it's my understanding that JITing pays a runtime cost. That's not the case with Rust compiled regexes. (Admittedly, this cost is likely negligible.) Secondly, wouldn't PyPy JIT the general matching algorithm? This seems like a substantively different process than doing code generation specifically for a regex whose structure you know at compile time. (Whether I'm currently taking advantage of any optimizations that PyPy's JIT isn't is of course a different story.)
- thristian 13y ago
  PyPy uses a tracing JIT, so it observes the general matching algorithm for a few iterations and then emits code that implements what the general algorithm actually did, i.e. the specific matching steps for that specific regex. JITting a regex isn't really the same thing as your Rust native regexes; for example, if somebody wrote a regex library with a JIT and linked it to a C program, I woudln't count it. However, in PyPy's case regexes are exactly as native as the rest of the codebase rather than being a nested VM, so in that sense they're 'native'.

sixbrx 13y ago

Very impressive. Especially the native regexs which will fail at compile time if they are invalid and which compile to a custom matcher machine (without having to express them in nasty template syntax). Rust has more macro-chops than I suspected.

pohl 13y ago

Aside from Servo itself, this is the coolest and most ambitious piece of Rust code I've yet seen. I haven't had the pleasure of using a language with a good macro facility. What other sorts of applications do macros have, aside from this and type safe println are there? Could one make a json or XML parsing library with this technique? Or a driver for a database? How does one go about acquiring an intuition for when to use or not use them?

burntsushi 13y ago
Thanks for your kind comments. :) > How does one go about acquiring an intuition for when to use or not use them? Truthfully, I don't know. In this particular case, the benefits seem really clear: we get safety and performance increases. But here's a caveat: the particular reason why this works well for regexes is because the common use case is to write the string literal corresponding to the regex into your program. This is what allows the macro facilities to kick in. For example, if the regex is derived from user input at runtime, then the `regex!` macro can't be used. i.e., you can't do this: let restr = "a*"; let re = regex!(restr); The `regex!` macro must accept a string literal (or another macro invocation that produces a string literal).
- pohl 13y ago
  I see. So maybe if you had a fixed XSD or XSLT at compile time you could emit a faster but specialized parser or transformer. But maybe that wouldn't work out so well in practice. I did find an interesting slide deck from the scala universe that mentions something like F# type providers (among other things) as possible applications. http://scalamacros.org/paperstalks/2014-02-04-WhatAreMacrosGoodFor.pdf http://scalamacros.org/paperstalks/2014-02-04-WhatAreMacrosG...
rca 13y ago
I think you would ask yourself : can I compute this at compile time? (And is it useful to do so?) I don't really see how you could use that for a database driver, but for example you could create a library that uses macros to generate custom serialization/deserialization code to/from json (or whatever format) for your data structures. (Edit: after a quick check this use case seems to be already covered by #[deriving(Encodable, Decodable)] in rust.)

Dewie 13y ago

Is this implementation close to the theoretical concept of regular expressions? I have read that some implementations of regular expressions are quite a bit more powerful than regular expressions from CS, in that they can recognize languages that are not regular.

burntsushi 13y ago
Yes. It's a reasonably faithful port of RE2, which elides features like backreferences.
- pjscott 13y ago
  This is usually a small price to pay for guaranteed O(n) matching speed. (Kudos to the author for doing the Right Thing here.)
  - burntsushi 13y ago
    Thanks :-) The implementation is basically the Pike VM as described by Russ Cox. Recursion depth in particular has an upper bound corresponding to the number of instructions in the regex. In practice, this means it's safe to run a regex on untrusted data. (Creating a regex from untrusted data still needs a bit of work, but is fixable!)

jeffdavis 13y ago

Impressive. I like how the rust community is offering so many good examples of real utility for the language. Some languages are a little heavy on theory but have trouble connecting with potential users; and other languages are popular but have a lot of problems due to fundamental weaknesses. Rust, and its community, seems to have a good balance. Good theoretical foundation, but a lot of people always working to show some practical reason to care about the theory.

CyberShadow 13y ago

Would be interesting to see a benchmark between D's ctRegex and Rust's "regex!". IIRC, when ctRegex was announced, it beat all other contestants (including V8's JIT-ed REs) in the author's benchmarks. There will be a talk at this year's D conference on D's implementation of regular expressions: http://dconf.org/2014/talks/olshansky.html http://dconf.org/2014/talks/olshansky.html