Go bindings to Rust's regex engine

by burntsushi • 10 years ago

127 108 10 years ago

exDM692• 10 years 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• 10 years ago

It's easy to call any code from any language - all you need is the power of HTTP and micro services! ;)

dikaiosune2• 10 years 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.

btrask• 10 years ago

I wish you were joking.

jkrems• 10 years ago

Reminds me of this: https://blogs.oracle.com/angelo/entry/url_encoding_and_other...

xiaq• 10 years 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.

pjmlp12• 10 years 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.

catnaroek14• 10 years 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.

oldmanjay• 10 years ago

To what end, though? So the mostly dead people responsible can rest more easily in an uncaring universe?

We may as well remember Lucy, the former vacuum tube assembler and current resident of the dustbin of history.

0xFFC• 10 years ago

What do you think of IPC ? in terms of performance and usability.

(BTW I am genuinely asking)

jstimpfle2• 10 years ago

Assuming that you imply serialization and message passing here: probably too slow for many useful library functions.

giovannibajo12• 10 years 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.

pcwalton4• 10 years ago

Note that the Rust standard library also sets O_CLOEXEC. https://github.com/rust-lang/rust/pull/24034

burntsushi12• 10 years 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• 10 years 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.

masklinn2• 10 years 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.

burntsushi12• 10 years 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• 10 years 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• 10 years 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• 10 years 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• 10 years 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• 10 years 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.

exDM692• 10 years 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.

robohamburger2• 10 years 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

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• 10 years 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.

PeCaN2• 10 years 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• 10 years 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.

Animats• 10 years 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.

burntsushi12• 10 years 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• 10 years ago

curious, why is the compile-time regex slower? is it just a less efficient implementation?

jerf• 10 years 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.

pcwalton4• 10 years 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• 10 years 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.

glangdale4• 10 years 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.

steveklabnik2• 10 years ago

Oh neat! I hadn't heard of hyperscan before. I will have to check this out.

burntsushi12• 10 years 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.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?

glangdale4• 10 years 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...

pettou2• 10 years ago

Do you perhaps happen to have a link to the results of these benchmarks? I'm desperately looking for some, and http://lh3lh3.users.sourceforge.net/reb.shtml seems to be quite date.

And, impressive work on the regex engine!

niersi• 10 years 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/e5a5198eee...

dbaupp• 10 years 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.

burntsushi12• 10 years 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• 10 years 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

Go bindings to Rust's regex engine

Related Stories