Go: regexp: investigate further performance improvements

[hsluoyz]

Languages Regex Benchmark:

Language | Email(ms) | URI(ms) | IP(ms) | Total(ms)
--- | ---: | ---: | ---: | ---:
C PCRE2 | 25.00 | 25.02 | 5.65 | 55.66
Rust | 31.31 | 31.73 | 6.75 | 69.79
PHP | 54.39 | 50.22 | 5.80 | 110.40
Javascript | 74.88 | 63.09 | 2.02 | 140.00
D ldc | 146.01 | 140.03 | 5.19 | 291.24
D dmd | 205.52 | 200.30 | 5.59 | 411.41
Perl | 246.91 | 170.74 | 45.60 | 463.24
Crystal | 339.79 | 280.74 | 27.03 | 647.56
Python PyPy | 207.96 | 177.18 | 329.85 | 714.99
Ruby | 354.16 | 308.55 | 52.73 | 715.44
Java | 382.57 | 456.34 | 297.66 | 1136.57
Kotlin | 395.23 | 474.31 | 293.53 | 1163.07
Python 2 | 368.85 | 286.70 | 514.10 | 1169.65
Python 3 | 565.71 | 416.32 | 493.07 | 1475.09
Go | 423.53 | 415.45 | 722.53 | 1561.51
C# .Net Core | 1952.13 | 1681.00 | 111.32 | 3744.45
C# Mono | 2463.84 | 2088.87 | 153.78 | 4706.49

In the above benchmark, Go's regex is even slower than Python. It is not ideal because as Python is a scripting language, and Go is a static language, Go should be faster than Python.

I noticed that there's an issue here: https://github.com/golang/go/issues/19629, and someone said that because Python uses C for regex, and C is faster than Go. But Python is a cross-platform language and it can enjoy the C regex implementations for all platforms. Why can't Go do the same thing? This may be a stupid question but I just don't understand why Go has to use cgo to call C code, but Python doesn't have this limitation? Thanks.

[ianlancetaylor]

Calling out to C carries a cost. We don't want to do it for a basic package like regexp. We're much more interested in speeding up Go's regexp package. If people want to work on that, that would be great.

Note that one reason that Go's regexp package may be slower is that it works on UTF-8 characters, not ASCII bytes. I don't know what Python does.

Also note that Go is committed to using regexps that scale well (see https://swtch.com/~rsc/regexp/). I don't know what Python does.

I'm not sure it's useful to leave a general issue like this open. It doesn't suggest any specific action to take. Are you interested in examining the regexp code to understand why Python does better on this benchmark?

[mvdan]

The benchmark code includes compiling the regex. In a common use of regexp, one would compile the regex once and run it many times, so the benchmark numbers aren't very helpful.

Also note that the benchmark numbers are almost a year old at this point, and Go does two releases per year.

[Azareal]

I might be mistaken, but doesn't PCRE have a JIT compiler? That might explain it, at-least for a couple of the top ones (I know PHP uses PCRE).

[Azareal]

The benchmark code includes compiling the regex. In a common use of regexp, one would compile the regex once and run it many times, so the benchmark numbers aren't very helpful.

https://github.com/mariomka/regex-benchmark/issues/2 I found an example on the same repository which apparently excludes compilation, but it doesn't look too scientific (only ten executions). It shows more or less the same results (which is odd as I'd thought that compilation would have more of an impact on the times).

[mvdan]

The compilation does have a large impact on the speed:

$ cat f_test.go
package p

import (
        "regexp"
        "testing"
)

var Sink bool

func BenchmarkCompileRun(b *testing.B) {
        for i := 0; i < b.N; i++ {
                rx := regexp.MustCompile(`[\w\.+-]+@[\w\.-]+\.[\w\.-]+`)
                Sink = rx.MatchString("123456789 [email protected]")
        }
}

func BenchmarkRun(b *testing.B) {
        rx := regexp.MustCompile(`[\w\.+-]+@[\w\.-]+\.[\w\.-]+`)
        for i := 0; i < b.N; i++ {
                Sink = rx.MatchString("123456789 [email protected]")
        }
}
$ go test -bench=.
goos: linux
goarch: amd64
pkg: mvdan.cc/p
BenchmarkCompileRun-4             100000             14160 ns/op
BenchmarkRun-4                   1000000              1121 ns/op
PASS
ok      mvdan.cc/p      2.693s

I presume it doesn't show up in the original numbers because the input data is very large, though.

I agree with @ianlancetaylor that a generic issue like this isn't very helpful. If specific parts of the regexp package could be improved, or certain edge cases are orders of magnitude slower than they should be, we should use separate issues to tackle those. For example, we already have some like #24411 and #21463.

[CAFxX]

While it's true that this issue is less than actionable as-is, it is also true that the results of the benchmark reported here are not too dissimilar from the ones on https://benchmarksgame-team.pages.debian.net/benchmarksgame/performance/regexredux.html (where they use 1.10). I agree it's unfortunate that all those benchmarks include pattern compilation (although it seems it's not so significant).

[junyer]

My comments on https://github.com/golang/go/issues/26943:

Would it be feasible to move the syntax.InstRune* match checks from step() to add()? A thread failing in step() constitutes wasted work – even for a regular expression as simple as [+-]?[0-9]+.

Also, what about using slice assignment when a thread is enqueued? Let cap have copy-on-write semantics.

Also also, it might be worth evaluating the benefit of using a slice as a stack instead of recursing. Anything to reduce the overhead of syntax.InstAlt instructions.

[gopherbot]

Change https://golang.org/cl/130417 mentions this issue: regexp/syntax: don't do both linear and binary sesarch in MatchRunePos

[gopherbot]

Timed out in state WaitingForInfo. Closing.

(I am just a bot, though. Please speak up if this is a mistake or you have the requested information.)

[josharian]

Reopening to prevent @junyer having to relocate his ideas yet again. :)

[mvdan]

I think @gopherbot needs to be taught some manners.

[agnivade]

That benchmark site has not been updated in a year.

I just ran the input with the tip compiler (go version devel +aa20ae4853 Mon Nov 12 23:07:25 2018 +0530 linux/amd64), along with converting the benchmark to an idiomatic one.

Code -

package main

import (
    "bytes"
    "log"
    "os"
    "regexp"
    "testing"
)

var matches []string
var count int

func measure(data string, pattern string, b *testing.B) {
    r, err := regexp.Compile(pattern)
    if err != nil {
        log.Fatal(err)
    }

    for i := 0; i < b.N; i++ {
        matches = r.FindAllString(data, -1)
        count = len(matches)
    }
}

func BenchmarkAll(b *testing.B) {
    filerc, err := os.Open(os.Getenv("FILE_NAME"))
    if err != nil {
        log.Fatal(err)
    }
    defer filerc.Close()

    buf := new(bytes.Buffer)
    buf.ReadFrom(filerc)
    data := buf.String()
    // Email
    b.Run("Email", func(b *testing.B) {
        measure(data, `[\w\.+-]+@[\w\.-]+\.[\w\.-]+`, b)
    })

    // URI
    b.Run("URI", func(b *testing.B) {
        measure(data, `[\w]+://[^/\s?#]+[^\s?#]+(?:\?[^\s#]*)?(?:#[^\s]*)?`, b)
    })

    // IP
    b.Run("IP", func(b *testing.B) {
        measure(data, `(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9])`, b)
    })
}

With that, if I compare with 1.10, there is a substantial improvement now

$benchstat go1.10.txt tip.txt 
name         old time/op  new time/op  delta
All/Email-4   507ms ± 1%   410ms ± 1%  -19.03%  (p=0.008 n=5+5)
All/URI-4     496ms ± 1%   398ms ± 1%  -19.86%  (p=0.008 n=5+5)
All/IP-4      805ms ± 0%   607ms ± 1%  -24.63%  (p=0.008 n=5+5)

And also the total is now 1415ms which brings us above Python3. If we are to go by the original issue title, I'd say it is pretty much resolved.

Only @junyer's comments here have some concrete suggestions to improve.

I don't know whether they are still applicable in the current tip as of now. I will let someone investigate that and re-purpose the issue to that effect.

[junyer]

As per https://perf.golang.org/search?q=upload:20181127.2, moving the syntax.InstRune* match checks from step() to add() seems helpful.

Note that this is the regular expression used for the Match/Hard1/* benchmarks:

        {"Hard1", "ABCD|CDEF|EFGH|GHIJ|IJKL|KLMN|MNOP|OPQR|QRST|STUV|UVWX|WXYZ"},

[junyer]

As per https://perf.golang.org/search?q=upload:20181127.3, letting cap have copy-on-write semantics seems additionally helpful.

[junyer]

Both of those are quite trivial changes. I also suggested reducing the overhead of syntax.InstAlt instructions, but that would require some design discussion, so I'm not tinkering with that tonight.

[CAFxX]

This may be a bit of a wild idea (that would likely need to be tracked in a separate issue, but as I'm not even sure how feasible it is and as it's related to this pretty open-ended issue I'm dumping it here) but it came to mind while reading this old article from @dgryski: would it make sense, for regexp source expressions known at compile time, having the go compiler compile the regexp and then emit native machine code implementing doExecute for that specific expression (kind-of like ragel)? At runtime regexp.Compile would somehow discover that the expression has been already compiled to native code, and would use the precompiled doExecute.

To avoid having to generate native code directly just for the regexp it would probably be ok to generate go code and let the rest of the go compiler handle that.

[smasher164]

having the go compiler compile the regexp and then emit native machine code

There is precedent for this, namely CTRE for C++, and what used to be rust's compile-time regex macro. The optimization doesn't seem too farfetched to me, since it's similar to how intrinsics and SSA rules can redirect usage of the standard library to different implementations.

As a side note, it would be an interesting project for someone to put together a go generate tool and ctre package that mirrored regexp's API, but generated code at compile time.

[junyer]

CTRE is a veritable nightmare of C++ template metaprogramming. Let us never speak of it again.

The state of the art for code generation is probably Trofimovich's TDFA work for RE2C. See http://re2c.org/2017_trofimovich_tagged_deterministic_finite_automata_with_lookahead.pdf.

[prasad83]

This pcre based regex gave better performance compared to regexp - still PHP preg_match out performed in my test of (apache access log parsing).