13 ms·

Go bindings to Rust's regex engine

127 points by burntsushi 11y ago

exDM69 11y ago
This right here is why I think Rust really stands out from other languages. You can call it from other languages just as you can call native code written in C. It's not married to a complex runtime system. Most other languages are "dead ends", because code written in them is not easily reusable from other languages.
- dangerlibrary 11y ago
  It's easy to call any code from any language - all you need is the power of HTTP and micro services! ;)
  - dikaiosune 11y ago
    Microservices don't help polyglots make regexes faster. If you're sticking a 100ns operation behind an endpoint with JSON serialization/deserialization, network round-trip, etc., then I'm not sure what to say to that.
    - sixbrx 11y ago
      Note wink at end of dangerlibrary's post!
      - dikaiosune 11y ago
        A wink does not necessarily mean sarcasm? I agree that in this case it probably does, but I don't see how that use of sarcasm adds anything substantive to the conversation (aside from a not-relevant-to-this-post dig on microservices, perhaps).
        cobalt 11y ago
        i think he was making a joke... (dangerlibrary)
        derefr 11y ago
        What the wink means is that dangerlibrary was making the same point you made in your reply to them.
    - cderwin 11y ago
      Actually this microservices approach has existed for decades in erlang/otp and can maintain quite excellent speed. You're not going to beat raw c speed-wise, but typically you will beat comparable dynamic languages -- and you don't have to worry about decoding/encoding json or any of that bs. I'd personally be absolutely thrilled if something like genserver and some other otp protocols were ported to other dynamic languages -- but alas real processes aren't nearly efficient enough.
      - vvanders 11y ago
        You can also delegate to C with Erlang via NIFs
        steveklabnik 11y ago
        Then there's https://github.com/hansihe/Rustler https://github.com/hansihe/Rustler
        vvanders 11y ago
        Yes, that's been on my (long) list of things to check out.
  - btrask 11y ago
    I wish you were joking.
    - xaduha 11y ago
      Granted.
  - jkrems 11y ago
    Reminds me of this: https://blogs.oracle.com/angelo/entry/url_encoding_and_other_from https://blogs.oracle.com/angelo/entry/url_encoding_and_other...
  - xiaq 11y ago
    On a serious note, implementing libraries as standalone applications that can be accessed via IPC is actually a viable approach. Plan 9 does this with almost all of its services. Not exactly a fair comparison though, since the IPC mechanism in Plan 9 is just the file system and much easier to learn.
- pjmlp 11y ago
  > This right here is why I think Rust really stands out from other languages. You can call it from other languages just as you can call native code written in C Which is only true, when we forget about the history of computing before C was widespread outside AT&T and C ABI became a synonym for OS ABI. Rust is great, and a very good step forward in terms of safe code, but lets not forget the ones that came before.
  - catnaroek 11y ago
    Did any of those provide safety by means of compile-time checks (as opposed to sophisticated runtime systems, which are by necessity more expensive), though? AFAICT, Lisp didn't, Smalltalk didn't and Oberon didn't.
    - pjmlp 11y ago
      Not all the use cases that Rust covers, but many of the typical errors that are possible in C, yes. For example, the NEWP in MCP only allowed unsafe code in modes where the system administrator would configure them as such, back in 1961. https://en.wikipedia.org/wiki/Burroughs_MCP https://en.wikipedia.org/wiki/Burroughs_MCP https://en.wikipedia.org/wiki/NEWP https://en.wikipedia.org/wiki/NEWP
      - catnaroek 11y ago
        If you need unsafe code to implement the garbage collector and other core system facilities, then “selectively” disabling safety doesn't really mean much, does it? Also, determining whether code is safe to run requires proof, not trust. Since when are system administrators particularly skilled at coming up with proofs?
        pjmlp 11y ago
        Who said anything about NEWP using a GC?! Also the type of enabling/disabling unsafe code in those lanugages was not much different than running "rustc -D unsafe-code" Also computer admins in the 60's were programmers.
- 0xFFC 11y ago
  What do you think of IPC ? in terms of performance and usability. (BTW I am genuinely asking)
  - jstimpfle 11y ago
    Assuming that you imply serialization and message passing here: probably too slow for many useful library functions.
    - derefr 11y ago
      How about message-passing without serialization? Imagine that what we got in the 1970s instead of Unix was something like an Erlang VM, in the sense of each OS "process" having an inbox ring-buffer to which other processes could write; and every process having a set of basic agreed-upon tagged types, such that processes could stick raw-memory structs into other processes' inboxes, as long as they consisted only of those basic tagged types.
      - jstimpfle 11y ago
        > basic agreed-upon tagged types Anything going beyond ASCII/UTF-8 or C types will be very hard to agree upon. And I think there is no way around serialization ( == chasing pointers and converting to a contiguous chunk of memory). Except if you restrict to a single language ecosystem like Erlang or Haskell, which enable data sharing between (often userspace-) threads in a shared address space. But these need a much more complex runtime.
        derefr 11y ago
        Almost every "language ecosystem" has a runtime which itself—at least on ⋆nix—relies on libc. This is why every modern language exposes e.g. a FILE type with the same semantics; they're all just wrapping the libc FILE struct + API. What I'm imagining is a world where "libc", from way-back-when in the 1970s, exposed declarations for some more interesting ADT types + APIs than just register-sized scalars and ASCIZ strings. Not types that require heap allocation or anything, mind you; just some fancier on-stack value types. Imagine the C runtime being just "batteries-included" enough that if you were writing, say, a JSON parser in C, there would be obvious "native C types" to decode each of JSON's container types into. And now imagine a world where every modern "language ecosystem" had been built up on top of this libc, instead of the one we have. A libc one can rely on to represent almost all the basic types one needs in a well-known (or at least, consistent per machine) manner in memory. Imagine how easy message-passing IPC would become in such a world.
- deleted 11y ago
  [deleted]
- giovannibajo1 11y ago
  This only works for simple algorithms that don't touch the system. As soon as you try to bind something that handles a file on disk, a socket, a thread, it's wishful thinking anyway, as any language have different ways and paradigms to approach threading, asynchronous I/O, signals and other runtime-level issues, and getting code from a different language / library / paradigm is probably not going to fly, or even introduce subtle bugs. For instance, if I bind a Rust library that opens a file on disk and use it from Go, I lose all the benefits of the Go runtime like the fact that the FD is not inherited by sub processes (as Go always uses O_CLOEXEC, while glibc doesn't), or the fact that blocking calls never return EINTR to application code in case of signals (the Go runtime handles this for the application). So you might think that the library works, while its subtly violating your language's runtime conventions in a way that might cause hard to debug bugs in production. One of the benefit of writing code in single "modern" language/runtime is that you don't have to worry about these hairy issues.
  - pcwalton 11y ago
    Note that the Rust standard library also sets O_CLOEXEC. https://github.com/rust-lang/rust/pull/24034 https://github.com/rust-lang/rust/pull/24034
  - burntsushi 11y ago
    It feels like you're throwing the baby out with the bath water, and I don't think a good regex library could be classified as "simple." I specifically wrote Go bindings to Rust's regex lib in tandem with the C API to make sure I wasn't baking any assumptions into the C API that would make it difficult for another language to bind to them. This process was lucrative. My first draft of the C API defined an iterator that held on to a pointer to the text being searched for the lifetime of the iterator. It turns out that this is inconvenient to use from a language like Go (or perhaps, any language with a moving GC) because C holding on to pointers to memory allocated in the host language can be bad juju. Because I did this process in tandem, I was able to correct the issue at the C API level. As a result, if you need fast regexes in Go, you now have an option, and that option is built on a reasonably mature regex library with thousands of tests and a benchmark harness that sports PCRE1, PCRE2, Tcl, RE2 and Oniguruma, of which, Rust's regex engine compares quite favorably.
- falcolas 11y ago
  > ... because code written in them is not easily reusable from other languages. Which is also technically true for C as well. The ABI [EDIT: Not API] is an implementation detail which can vary from compiler to compiler. So long as you're just using LLVM-based compilers for both Rust and your other languages, you should be OK, but don't be surprised if you run into problems.
  - masklinn 11y ago
    > Which is also technically true for C as well. The API is an implementation detail which can vary from compiler to compiler. The C ABI (API is less relevant there) is really the platform/OS's calling convention, which — aside from Microsoft (and embedded systems I guess, because embedded) — is generally the architecture's calling conventions. Which are usually well documented. > So long as you're just using LLVM-based compilers for both Rust and your other languages, you should be OK, but don't be surprised if you run into problems. As long as all the languages involved use the same ABI you're in the clear, that's got nothing to do with LLVM. That's what cgo does on the Go side[0]. And as pcwalton notes in an other comment, in theory you could even have the Rust FFI follow the Go/Plan9 ABI. [0] at a significant cost for the default toolchain since `gc` doesn't use the platform ABI. I believe the gccgo-based alternative toolchain has no cgo overhead.
  - burntsushi 11y ago
    > So long as you're just using LLVM-based compilers for both Rust and your other languages, you should be OK, but don't be surprised if you run into problems. No. You can use the Go bindings to Rust's regex library where the regex library is compiled with `rustc` (llvm based) and your host program, written in Go, is compiled with the standard Go compiler, which is not llvm based. This works because the Go toolchain knows how to link with objects exposing a C ABI and the Rust toolchain knows how to provide said objects. There is no particular dependency on llvm here.
  - Manishearth 11y ago
    - Calling into the C ABI is a stable and well documented operation that most languages support in some form - Rust allows you to export functions with the C ABI - LLVM wasn't involved here at all
- tyingq 11y ago
  >>Most other languages are "dead ends", because code written in them is not easily reusable from other languages. FFI isn't the only way to be reusable from another language though. Many interpreted languages are easy to embed into C, C++, and often other languages.
  - duaneb 11y ago
    Yes, but the conversion between domain types is the killer there. Have you ever tried embedding ruby into python (or vice versa?) The string/unicode/bytes conversions alone demand a full project's worth of work. Basically, having base types convert toll-free is HUGE.
- tagrun 11y ago
  Runtime doesn't necessarily mean "can't call from other languages". Languages with runtimes can still conform to C ABI on that arch. You can call Go from C, or even from Java on Android out-of-the-box (and Objective C on iOS), for example.
  - Jweb_Guru 11y ago
    You can call Go from C, but it's extremely slow and requires special handling of GC'd references (among other things). It's not really a suitable replacement for C bindings in many circumstances.
  - exDM69 11y ago
    True on all accounts but you forgot the "easily" part. Installing JVM and then writing JNI wrappers isn't really easy reuse. You just don't see Java or Go code (let alone both) used in programs predominantly written in another language.
- robohamburger 11y ago
  What will be interesting is when rust gets its own ABI. There is an rfc for it even: https://github.com/rust-lang/rfcs/issues/600 https://github.com/rust-lang/rfcs/issues/600 Hopefully if such a thing exists you could link directly to a rust library from other high level languages and possibly even have lower overhead. For now being able to do the equivalent of extern "C" is not that new but still really useful I suppose.
  - kibwen 11y ago
    I wouldn't quite say that's an RFC, it's just an issue in the RFCs repo. Typically people use the issue tracker in order to represent RFCs that they would like to see written, sort of a wishlist.
    - robohamburger 11y ago
      Ah I misunderstood! Thinking about it a bit more and given how heavily rust uses generics it seems like having an ABI that is at all usable by another higher level language might be challenging. I guess there is always compiler plugins though :)
- PeCaN 11y ago
  Ada does this with the rather convenient pragma Export(Convention => C, Entity => My_Ada_Function, External_Name => "mypackage_ada_function"); You can kinda coerce D and C++¹ to do the same thing, but this is definitely something Rust and Ada got really right. -- ¹Okay I lied, C++ does this pretty easily with extern "C". However, C++ APIs frequently do not convert well to C at all and you often have to write wrappers for them. C++ classes in particular just can't cross ABI boundaries without a lot of pain, while Ada records and Rust structs are usually just a pragma away from being accessible from C (their “methods” don't use a special calling convention; method calls are just syntactic sugar for passing a struct as the first argument).
  - nitrogen 11y ago
    The x86 C++ ABI convention of passing this in ECX probably caused a lot of C interop headaches over the years, but really, C should have been passing the first argument in a register anyway.
deleted 11y ago
[deleted]
Animats 11y ago
The usual way to use regular expressions in Rust is to use the Rust module that complies them at compile time. That can't be called from Go.
- burntsushi 11y ago
  Unfortunately, no, that is not the usual way any more. Two primary reasons: 1. Compiling regexes at compile time requires a compiler plugin, which only works on nightly. 2. The compile-time regexes are dramatically slower (think orders of magnitude) than the normal Regex::new method. The normal Regex::new method is what's shown here in these bindings. The compiler plugin was code I wrote two years ago, and really hasn't changed since then. Regex::new on the other hand has gotten a lot of love. The plugin's performance may one day get better, but it won't be soon unless someone else works on it.
  - AYBABTME 11y ago
    curious, why is the compile-time regex slower? is it just a less efficient implementation?
    - killercup 11y ago
      Yes, several of the optimizations of the dynamic regexes aren't available in the compile-time version. (It doesn't even have a DFA, IIRC.) There is [a lint][1] which checks that your regular expressions are valid (at compile time), though. [1]: https://github.com/Manishearth/rust-clippy/wiki#invalid_regex https://github.com/Manishearth/rust-clippy/wiki#invalid_rege...
    - burntsushi 11y ago
      Regex::new has these tools at its disposal: Pike VM (NFA), backtracking (NFA), DFA (online), DFA (offline), Boyer-Moore The plugin has these tools at its disposal: Pike VM. But yeah, killercup is correct. The DFA (online) is one of the bigger reasons. But the offline DFA and Boyer-Moore are probably just as important. You might glean more information from my hacking guide: https://github.com/rust-lang-nursery/regex/blob/master/HACKING.md https://github.com/rust-lang-nursery/regex/blob/master/HACKI...
jerf 11y ago
Something I've wondered for a while... in the long term (that is, I'm more asking about architecture than what exists today), is it possible to integrate Rust more deeply into the calling convention of another language, so that rather than generating "C" functions, it might generate true "Go" functions? I'm also asking beyond Go, so if the answer is "M:N really screws up Go w.r.t. Rust", I'm also curious about whether, for instance, you could write native Rust extensions to Perl or Python or $WHATEVER by changing out the runtime or something. If it works better for some languages than others, which ones might they be? It's nice to be able to generate true C functions, and it is of course perfectly appropriate and correct to start there, given the real-world state of the ecosystem. But a lot of languages take various forms of penalties to call into C, in order to ensure guarantees that are not necessarily required by languages that aren't C, and, simultaneously, miss out on guarantees that Rust may be able to provide that C can't express and thus the C bindings can't count on.
- pcwalton 11y ago
  Possibly. You'd have to add support for the nonstandard Plan 9 calling conventions, stack growth checks, and GC stack map information. LLVM broadly has support for all of these features (contrary to what some Go team members have said), but the specific binary formats for these features are incompatible with the Go runtime, so it'd be necessary to contribute upstream changes to LLVM or fork it.
  - geodel 11y ago
    Did they say segmented stack / stack maps is not available in llvm or it was not available when they started working on Go around 2007? Because I notice that segmented support was added around 2012 and stack maps in 2013.
glangdale 11y ago
We're interested in how the Hyperscan library (full disclosure: I am an Intel employee and Hyperscan designer) stacks up in this comparison. From what I understand there are Go and Rust bindings for Hyperscan out there as 3rd party projects (although I don't know much about them). We find Rust intriguing and the fine-grained control would be a good match for what our run-time needs; it would be a interesting project to re-implement parts of Hyperscan in Rust.
- steveklabnik 11y ago
  Oh neat! I hadn't heard of hyperscan before. I will have to check this out.
- burntsushi 11y ago
  I'm interested too. I'm looking into adding hyperscan to Rust's benchmark harness (which already has PCRE1, PCRE2, RE2, Tcl and Oniguruma). I'm trying to figure out how best to wrap the API. The callback function in `hs_scan` is something I haven't seen in a regex library before (although I bet I can understand why it's used), but for example, Rust's wrapper cripples the callback in comparison to C by dropping the `void *context` parameter: http://flier.github.io/rust-hyperscan/doc/hyperscan/type.MatchEventCallback.html http://flier.github.io/rust-hyperscan/doc/hyperscan/type.Mat... I'm happy to wrap the C directly (in fact, that's what I've done for most of the other regex engines I benchmark against). Before I try to wrangle the callback-style API, is there an alternate API with a more explicit iterator-like interface?
  - glangdale 11y ago
    Thanks for looking into this; we like to see benchmarks run by other people to avoid the prospect that we're just benchmarking the things we already know about and like doing (which are often also the things which we've optimized). There are no other interfaces outside of the callback API. It's an interesting prospect to have an iterator-like API but a naive implementation of an iterator API would involve us having to save out all of our state somehow (in an explicit fashion, as opposed to a bunch of stack frames). Our system is pretty complex and so it's not just a case of saving out a couple DFA states...
niersi 11y ago
May I ask why? From my understanding Rust just have revamped their regex[0] using the same (similar) scheme as in RE2, which is now the Go's implementation, am I misinformed? [0]: https://github.com/rust-lang-nursery/regex/commit/e5a5198eeea6de2a10a2244fece8a1cc206faf22 https://github.com/rust-lang-nursery/regex/commit/e5a5198eee...
- dbaupp 11y ago
  The Rust regex library does use various techniques that RE2 and Go's library also use (and has from the start, that patch is just adding another feature that was missing), but it is generally faster than both of those libraries: take a look at the benchmarks in the link.
  - deleted 11y ago
    [deleted]
  - burntsushi 11y ago
    @jerf - In response to your deleted comment, the README explains some of the numbers. The really crazy numbers are silly, and I say so in the README. However, there are plenty of benchmarks well over 10x that are not silly at all. Look at the second block. The BeforeHolmes benchmark in particular is a good litmus test, since it defeats most optimizations. Those particular speed ups are due to algorithms used. RE2 would have a similar speedup when compared with Go's regexp package. Some of the other benchmarks in the 100x-400x range are likely due to smarter use of literal scanning.
- mastax 11y ago
  > I wrote these bindings primarily as a test case for the C API of Rust's regex library. In particular, I wanted to be sure that it was feasible to write low overhead bindings to another language. For the most part, I think that was a success. https://github.com/BurntSushi/rure-go#motivation https://github.com/BurntSushi/rure-go#motivation

127 points by burntsushi 11y ago

This right here is why I think Rust really stands out from other languages. You can call it from other languages just as you can call native code written in C. It's not married to a complex runtime system. Most other languages are "dead ends", because code written in them is not easily reusable from other languages.

dangerlibrary 11y ago
It's easy to call any code from any language - all you need is the power of HTTP and micro services! ;)
- dikaiosune 11y ago
  Microservices don't help polyglots make regexes faster. If you're sticking a 100ns operation behind an endpoint with JSON serialization/deserialization, network round-trip, etc., then I'm not sure what to say to that.
  - sixbrx 11y ago
    Note wink at end of dangerlibrary's post!
    - dikaiosune 11y ago
      A wink does not necessarily mean sarcasm? I agree that in this case it probably does, but I don't see how that use of sarcasm adds anything substantive to the conversation (aside from a not-relevant-to-this-post dig on microservices, perhaps).
      - cobalt 11y ago
        i think he was making a joke... (dangerlibrary)
      - derefr 11y ago
        What the wink means is that dangerlibrary was making the same point you made in your reply to them.
  - cderwin 11y ago
    Actually this microservices approach has existed for decades in erlang/otp and can maintain quite excellent speed. You're not going to beat raw c speed-wise, but typically you will beat comparable dynamic languages -- and you don't have to worry about decoding/encoding json or any of that bs. I'd personally be absolutely thrilled if something like genserver and some other otp protocols were ported to other dynamic languages -- but alas real processes aren't nearly efficient enough.
    - vvanders 11y ago
      You can also delegate to C with Erlang via NIFs
      - steveklabnik 11y ago
        Then there's https://github.com/hansihe/Rustler https://github.com/hansihe/Rustler
        vvanders 11y ago
        Yes, that's been on my (long) list of things to check out.
- btrask 11y ago
  I wish you were joking.
  - xaduha 11y ago
    Granted.
- jkrems 11y ago
  Reminds me of this: https://blogs.oracle.com/angelo/entry/url_encoding_and_other_from https://blogs.oracle.com/angelo/entry/url_encoding_and_other...
- xiaq 11y ago
  On a serious note, implementing libraries as standalone applications that can be accessed via IPC is actually a viable approach. Plan 9 does this with almost all of its services. Not exactly a fair comparison though, since the IPC mechanism in Plan 9 is just the file system and much easier to learn.
pjmlp 11y ago
> This right here is why I think Rust really stands out from other languages. You can call it from other languages just as you can call native code written in C Which is only true, when we forget about the history of computing before C was widespread outside AT&T and C ABI became a synonym for OS ABI. Rust is great, and a very good step forward in terms of safe code, but lets not forget the ones that came before.
- catnaroek 11y ago
  Did any of those provide safety by means of compile-time checks (as opposed to sophisticated runtime systems, which are by necessity more expensive), though? AFAICT, Lisp didn't, Smalltalk didn't and Oberon didn't.
  - pjmlp 11y ago
    Not all the use cases that Rust covers, but many of the typical errors that are possible in C, yes. For example, the NEWP in MCP only allowed unsafe code in modes where the system administrator would configure them as such, back in 1961. https://en.wikipedia.org/wiki/Burroughs_MCP https://en.wikipedia.org/wiki/Burroughs_MCP https://en.wikipedia.org/wiki/NEWP https://en.wikipedia.org/wiki/NEWP
    - catnaroek 11y ago
      If you need unsafe code to implement the garbage collector and other core system facilities, then “selectively” disabling safety doesn't really mean much, does it? Also, determining whether code is safe to run requires proof, not trust. Since when are system administrators particularly skilled at coming up with proofs?
      - pjmlp 11y ago
        Who said anything about NEWP using a GC?! Also the type of enabling/disabling unsafe code in those lanugages was not much different than running "rustc -D unsafe-code" Also computer admins in the 60's were programmers.
0xFFC 11y ago
What do you think of IPC ? in terms of performance and usability. (BTW I am genuinely asking)
- jstimpfle 11y ago
  Assuming that you imply serialization and message passing here: probably too slow for many useful library functions.
  - derefr 11y ago
    How about message-passing without serialization? Imagine that what we got in the 1970s instead of Unix was something like an Erlang VM, in the sense of each OS "process" having an inbox ring-buffer to which other processes could write; and every process having a set of basic agreed-upon tagged types, such that processes could stick raw-memory structs into other processes' inboxes, as long as they consisted only of those basic tagged types.
    - jstimpfle 11y ago
      > basic agreed-upon tagged types Anything going beyond ASCII/UTF-8 or C types will be very hard to agree upon. And I think there is no way around serialization ( == chasing pointers and converting to a contiguous chunk of memory). Except if you restrict to a single language ecosystem like Erlang or Haskell, which enable data sharing between (often userspace-) threads in a shared address space. But these need a much more complex runtime.
      - derefr 11y ago
        Almost every "language ecosystem" has a runtime which itself—at least on ⋆nix—relies on libc. This is why every modern language exposes e.g. a FILE type with the same semantics; they're all just wrapping the libc FILE struct + API. What I'm imagining is a world where "libc", from way-back-when in the 1970s, exposed declarations for some more interesting ADT types + APIs than just register-sized scalars and ASCIZ strings. Not types that require heap allocation or anything, mind you; just some fancier on-stack value types. Imagine the C runtime being just "batteries-included" enough that if you were writing, say, a JSON parser in C, there would be obvious "native C types" to decode each of JSON's container types into. And now imagine a world where every modern "language ecosystem" had been built up on top of this libc, instead of the one we have. A libc one can rely on to represent almost all the basic types one needs in a well-known (or at least, consistent per machine) manner in memory. Imagine how easy message-passing IPC would become in such a world.
deleted 11y ago
[deleted]
giovannibajo1 11y ago
This only works for simple algorithms that don't touch the system. As soon as you try to bind something that handles a file on disk, a socket, a thread, it's wishful thinking anyway, as any language have different ways and paradigms to approach threading, asynchronous I/O, signals and other runtime-level issues, and getting code from a different language / library / paradigm is probably not going to fly, or even introduce subtle bugs. For instance, if I bind a Rust library that opens a file on disk and use it from Go, I lose all the benefits of the Go runtime like the fact that the FD is not inherited by sub processes (as Go always uses O_CLOEXEC, while glibc doesn't), or the fact that blocking calls never return EINTR to application code in case of signals (the Go runtime handles this for the application). So you might think that the library works, while its subtly violating your language's runtime conventions in a way that might cause hard to debug bugs in production. One of the benefit of writing code in single "modern" language/runtime is that you don't have to worry about these hairy issues.
- pcwalton 11y ago
  Note that the Rust standard library also sets O_CLOEXEC. https://github.com/rust-lang/rust/pull/24034 https://github.com/rust-lang/rust/pull/24034
- burntsushi 11y ago
  It feels like you're throwing the baby out with the bath water, and I don't think a good regex library could be classified as "simple." I specifically wrote Go bindings to Rust's regex lib in tandem with the C API to make sure I wasn't baking any assumptions into the C API that would make it difficult for another language to bind to them. This process was lucrative. My first draft of the C API defined an iterator that held on to a pointer to the text being searched for the lifetime of the iterator. It turns out that this is inconvenient to use from a language like Go (or perhaps, any language with a moving GC) because C holding on to pointers to memory allocated in the host language can be bad juju. Because I did this process in tandem, I was able to correct the issue at the C API level. As a result, if you need fast regexes in Go, you now have an option, and that option is built on a reasonably mature regex library with thousands of tests and a benchmark harness that sports PCRE1, PCRE2, Tcl, RE2 and Oniguruma, of which, Rust's regex engine compares quite favorably.
falcolas 11y ago
> ... because code written in them is not easily reusable from other languages. Which is also technically true for C as well. The ABI [EDIT: Not API] is an implementation detail which can vary from compiler to compiler. So long as you're just using LLVM-based compilers for both Rust and your other languages, you should be OK, but don't be surprised if you run into problems.
- masklinn 11y ago
  > Which is also technically true for C as well. The API is an implementation detail which can vary from compiler to compiler. The C ABI (API is less relevant there) is really the platform/OS's calling convention, which — aside from Microsoft (and embedded systems I guess, because embedded) — is generally the architecture's calling conventions. Which are usually well documented. > So long as you're just using LLVM-based compilers for both Rust and your other languages, you should be OK, but don't be surprised if you run into problems. As long as all the languages involved use the same ABI you're in the clear, that's got nothing to do with LLVM. That's what cgo does on the Go side[0]. And as pcwalton notes in an other comment, in theory you could even have the Rust FFI follow the Go/Plan9 ABI. [0] at a significant cost for the default toolchain since `gc` doesn't use the platform ABI. I believe the gccgo-based alternative toolchain has no cgo overhead.
- burntsushi 11y ago
  > So long as you're just using LLVM-based compilers for both Rust and your other languages, you should be OK, but don't be surprised if you run into problems. No. You can use the Go bindings to Rust's regex library where the regex library is compiled with `rustc` (llvm based) and your host program, written in Go, is compiled with the standard Go compiler, which is not llvm based. This works because the Go toolchain knows how to link with objects exposing a C ABI and the Rust toolchain knows how to provide said objects. There is no particular dependency on llvm here.
- Manishearth 11y ago
  - Calling into the C ABI is a stable and well documented operation that most languages support in some form - Rust allows you to export functions with the C ABI - LLVM wasn't involved here at all
tyingq 11y ago
>>Most other languages are "dead ends", because code written in them is not easily reusable from other languages. FFI isn't the only way to be reusable from another language though. Many interpreted languages are easy to embed into C, C++, and often other languages.
- duaneb 11y ago
  Yes, but the conversion between domain types is the killer there. Have you ever tried embedding ruby into python (or vice versa?) The string/unicode/bytes conversions alone demand a full project's worth of work. Basically, having base types convert toll-free is HUGE.
tagrun 11y ago
Runtime doesn't necessarily mean "can't call from other languages". Languages with runtimes can still conform to C ABI on that arch. You can call Go from C, or even from Java on Android out-of-the-box (and Objective C on iOS), for example.
- Jweb_Guru 11y ago
  You can call Go from C, but it's extremely slow and requires special handling of GC'd references (among other things). It's not really a suitable replacement for C bindings in many circumstances.
- exDM69 11y ago
  True on all accounts but you forgot the "easily" part. Installing JVM and then writing JNI wrappers isn't really easy reuse. You just don't see Java or Go code (let alone both) used in programs predominantly written in another language.
robohamburger 11y ago
What will be interesting is when rust gets its own ABI. There is an rfc for it even: https://github.com/rust-lang/rfcs/issues/600 https://github.com/rust-lang/rfcs/issues/600 Hopefully if such a thing exists you could link directly to a rust library from other high level languages and possibly even have lower overhead. For now being able to do the equivalent of extern "C" is not that new but still really useful I suppose.
- kibwen 11y ago
  I wouldn't quite say that's an RFC, it's just an issue in the RFCs repo. Typically people use the issue tracker in order to represent RFCs that they would like to see written, sort of a wishlist.
  - robohamburger 11y ago
    Ah I misunderstood! Thinking about it a bit more and given how heavily rust uses generics it seems like having an ABI that is at all usable by another higher level language might be challenging. I guess there is always compiler plugins though :)
PeCaN 11y ago
Ada does this with the rather convenient pragma Export(Convention => C, Entity => My_Ada_Function, External_Name => "mypackage_ada_function"); You can kinda coerce D and C++¹ to do the same thing, but this is definitely something Rust and Ada got really right. -- ¹Okay I lied, C++ does this pretty easily with extern "C". However, C++ APIs frequently do not convert well to C at all and you often have to write wrappers for them. C++ classes in particular just can't cross ABI boundaries without a lot of pain, while Ada records and Rust structs are usually just a pragma away from being accessible from C (their “methods” don't use a special calling convention; method calls are just syntactic sugar for passing a struct as the first argument).
- nitrogen 11y ago
  The x86 C++ ABI convention of passing this in ECX probably caused a lot of C interop headaches over the years, but really, C should have been passing the first argument in a register anyway.

deleted 11y ago

[deleted]

Animats 11y ago

The usual way to use regular expressions in Rust is to use the Rust module that complies them at compile time. That can't be called from Go.

burntsushi 11y ago
Unfortunately, no, that is not the usual way any more. Two primary reasons: 1. Compiling regexes at compile time requires a compiler plugin, which only works on nightly. 2. The compile-time regexes are dramatically slower (think orders of magnitude) than the normal Regex::new method. The normal Regex::new method is what's shown here in these bindings. The compiler plugin was code I wrote two years ago, and really hasn't changed since then. Regex::new on the other hand has gotten a lot of love. The plugin's performance may one day get better, but it won't be soon unless someone else works on it.
- AYBABTME 11y ago
  curious, why is the compile-time regex slower? is it just a less efficient implementation?
  - killercup 11y ago
    Yes, several of the optimizations of the dynamic regexes aren't available in the compile-time version. (It doesn't even have a DFA, IIRC.) There is [a lint][1] which checks that your regular expressions are valid (at compile time), though. [1]: https://github.com/Manishearth/rust-clippy/wiki#invalid_regex https://github.com/Manishearth/rust-clippy/wiki#invalid_rege...
  - burntsushi 11y ago
    Regex::new has these tools at its disposal: Pike VM (NFA), backtracking (NFA), DFA (online), DFA (offline), Boyer-Moore The plugin has these tools at its disposal: Pike VM. But yeah, killercup is correct. The DFA (online) is one of the bigger reasons. But the offline DFA and Boyer-Moore are probably just as important. You might glean more information from my hacking guide: https://github.com/rust-lang-nursery/regex/blob/master/HACKING.md https://github.com/rust-lang-nursery/regex/blob/master/HACKI...

jerf 11y ago

Something I've wondered for a while... in the long term (that is, I'm more asking about architecture than what exists today), is it possible to integrate Rust more deeply into the calling convention of another language, so that rather than generating "C" functions, it might generate true "Go" functions? I'm also asking beyond Go, so if the answer is "M:N really screws up Go w.r.t. Rust", I'm also curious about whether, for instance, you could write native Rust extensions to Perl or Python or $WHATEVER by changing out the runtime or something. If it works better for some languages than others, which ones might they be? It's nice to be able to generate true C functions, and it is of course perfectly appropriate and correct to start there, given the real-world state of the ecosystem. But a lot of languages take various forms of penalties to call into C, in order to ensure guarantees that are not necessarily required by languages that aren't C, and, simultaneously, miss out on guarantees that Rust may be able to provide that C can't express and thus the C bindings can't count on.

pcwalton 11y ago
Possibly. You'd have to add support for the nonstandard Plan 9 calling conventions, stack growth checks, and GC stack map information. LLVM broadly has support for all of these features (contrary to what some Go team members have said), but the specific binary formats for these features are incompatible with the Go runtime, so it'd be necessary to contribute upstream changes to LLVM or fork it.
- geodel 11y ago
  Did they say segmented stack / stack maps is not available in llvm or it was not available when they started working on Go around 2007? Because I notice that segmented support was added around 2012 and stack maps in 2013.

glangdale 11y ago

We're interested in how the Hyperscan library (full disclosure: I am an Intel employee and Hyperscan designer) stacks up in this comparison. From what I understand there are Go and Rust bindings for Hyperscan out there as 3rd party projects (although I don't know much about them). We find Rust intriguing and the fine-grained control would be a good match for what our run-time needs; it would be a interesting project to re-implement parts of Hyperscan in Rust.

steveklabnik 11y ago
Oh neat! I hadn't heard of hyperscan before. I will have to check this out.
burntsushi 11y ago
I'm interested too. I'm looking into adding hyperscan to Rust's benchmark harness (which already has PCRE1, PCRE2, RE2, Tcl and Oniguruma). I'm trying to figure out how best to wrap the API. The callback function in `hs_scan` is something I haven't seen in a regex library before (although I bet I can understand why it's used), but for example, Rust's wrapper cripples the callback in comparison to C by dropping the `void *context` parameter: http://flier.github.io/rust-hyperscan/doc/hyperscan/type.MatchEventCallback.html http://flier.github.io/rust-hyperscan/doc/hyperscan/type.Mat... I'm happy to wrap the C directly (in fact, that's what I've done for most of the other regex engines I benchmark against). Before I try to wrangle the callback-style API, is there an alternate API with a more explicit iterator-like interface?
- glangdale 11y ago
  Thanks for looking into this; we like to see benchmarks run by other people to avoid the prospect that we're just benchmarking the things we already know about and like doing (which are often also the things which we've optimized). There are no other interfaces outside of the callback API. It's an interesting prospect to have an iterator-like API but a naive implementation of an iterator API would involve us having to save out all of our state somehow (in an explicit fashion, as opposed to a bunch of stack frames). Our system is pretty complex and so it's not just a case of saving out a couple DFA states...

niersi 11y ago

May I ask why? From my understanding Rust just have revamped their regex[0] using the same (similar) scheme as in RE2, which is now the Go's implementation, am I misinformed? [0]: https://github.com/rust-lang-nursery/regex/commit/e5a5198eeea6de2a10a2244fece8a1cc206faf22 https://github.com/rust-lang-nursery/regex/commit/e5a5198eee...

dbaupp 11y ago
The Rust regex library does use various techniques that RE2 and Go's library also use (and has from the start, that patch is just adding another feature that was missing), but it is generally faster than both of those libraries: take a look at the benchmarks in the link.
- deleted 11y ago
  [deleted]
- burntsushi 11y ago
  @jerf - In response to your deleted comment, the README explains some of the numbers. The really crazy numbers are silly, and I say so in the README. However, there are plenty of benchmarks well over 10x that are not silly at all. Look at the second block. The BeforeHolmes benchmark in particular is a good litmus test, since it defeats most optimizations. Those particular speed ups are due to algorithms used. RE2 would have a similar speedup when compared with Go's regexp package. Some of the other benchmarks in the 100x-400x range are likely due to smarter use of literal scanning.
mastax 11y ago
> I wrote these bindings primarily as a test case for the C API of Rust's regex library. In particular, I wanted to be sure that it was feasible to write low overhead bindings to another language. For the most part, I think that was a success. https://github.com/BurntSushi/rure-go#motivation https://github.com/BurntSushi/rure-go#motivation