Why is Go's regex so slow?

I was going through this for the hell of it, and I saw that Go is generally quite quick. But there were a few outliers, and the most notable one for me was the regex code which was blown away by a ton of languages.

First of all most other languages use the C implementation so Go is losing to C.

Also as far as I remember, Go's regex is guaranteed to finish in time linear to the length of the input which protects from ReDoS attacks. That feature is really important for production services and while in terms of speed it might not be the fastest for certain regexps, it's still fast enough and safer on top. Meanwhile the Go team is working to improve it even more.

Edit: Found some official info by Ian Lance Taylor:


As you say, in a language like Python, the regexp engine is implemented in C. So you are comparing a somewhat tuned Go implementation with a highly tuned C implementation. You also need to consider the characteristics of the engine. Go has chosen to follow the re2 path (not surprising, since Russ Cox is a major author of both Go and re2). re2 has much better performance characteristics than some other regexp engines, in that it never has an exponential slowdown, but that comes at a cost for other regexps (https://swtch.com/~rsc/regexp/).

That is interesting.

It's not really an "apples to apples" comparison to some of those languages because they implement Perl style regular expressions instead of just regular expressions.

It looks like Go's implementation could use some more optimization. Rust's regular expression engine is way faster even though they use the same general design.

Yeah, I thought that whole site was pretty interesting.  Generally speaking, Go performed admirably, but regex definitely stood out.