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 foo@bar.etc")
        }
}

func BenchmarkRun(b *testing.B) {
        rx := regexp.MustCompile(`[\w\.+-]+@[\w\.-]+\.[\w\.-]+`)
        for i := 0; i < b.N; i++ {
                Sink = rx.MatchString("123456789 foo@bar.etc")
        }
}
$ 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 -

```go 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).

[candlerb]

@CAFxX:

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

That makes me think of a couple of less extreme optimisations:

1. for an expression of the form regexp.MustCompile(string_literal), at compile-time build the result value, and either store it immutably in the code segment, or clone at runtime. In fact, I guess this could be extended to any function call which can be marked "pure" and has constant arguments.

   Unfortunately this won't help benchmarks which loop over lists of strings to test as regexps. And it won't help real-world code much; they can get almost the same benefit if they do var xxx = regexp.MustCompile(...) globally.

2. regexp.MustCompile keeps a cache, i.e. map[string]*Regexp. It would be interesting to modify the benchmarks to do this explicitly, and see what difference it makes. The cache should have a size limit to avoid problems with dynamically-generated regexps.

[zikaeroh]

FWIW there's a good number of unreviewed CLs by @bboreham improving regexp performance that have been sitting for a cycle or so:

• CL 354909
• CL 353711
• CL 358756
• CL 355789
• CL 377294

Of the list, CL 355789 is exceptionally small (take the address of a big struct instead of copying it; 4 line change) compared to its 30-40% perf benefit.

[zikaeroh]

And, the benchstat with those 5 applied:

Time

``` name old time/op new time/op delta pkg:regexp goos:linux goarch:amd64 Find-8 158ns ±27% 130ns ±29% -17.37% (p=0.023 n=10+10) FindAllNoMatches-8 62.1ns ± 4% 59.2ns ± 1% -4.58% (p=0.000 n=8+8) FindString-8 148ns ±23% 128ns ±28% -13.39% (p=0.023 n=10+10) FindSubmatch-8 184ns ± 8% 172ns ± 5% -6.45% (p=0.017 n=10+10) FindStringSubmatch-8 175ns ±11% 194ns ±29% ~ (p=1.000 n=10+10) Literal-8 39.3ns ± 5% 39.6ns ±15% ~ (p=0.315 n=9+10) NotLiteral-8 865ns ±13% 773ns ±20% -10.72% (p=0.007 n=10+10) MatchClass-8 1.05µs ± 1% 1.01µs ± 7% -4.22% (p=0.016 n=9+10) MatchClass_InRange-8 1.01µs ± 2% 1.00µs ± 6% ~ (p=0.734 n=9+10) ReplaceAll-8 667ns ± 9% 652ns ± 5% ~ (p=0.156 n=9+10) AnchoredLiteralShortNonMatch-8 38.1ns ±25% 20.3ns ±11% -46.69% (p=0.000 n=10+10) AnchoredLiteralLongNonMatch-8 46.8ns ± 0% 19.5ns ± 1% -58.26% (p=0.001 n=6+8) AnchoredShortMatch-8 57.9ns ± 1% 43.1ns ± 2% -25.64% (p=0.000 n=8+9) AnchoredLongMatch-8 143ns ±12% 43ns ± 1% -70.15% (p=0.000 n=10+8) OnePassShortA-8 286ns ± 2% 215ns ± 2% -24.82% (p=0.000 n=10+10) NotOnePassShortA-8 390ns ±29% 282ns ±38% -27.70% (p=0.001 n=10+10) OnePassShortB-8 211ns ± 2% 176ns ± 1% -16.76% (p=0.000 n=10+10) NotOnePassShortB-8 235ns ±20% 175ns ± 1% -25.32% (p=0.000 n=10+10) OnePassLongNotPrefix-8 166ns ± 3% 124ns ± 2% -25.02% (p=0.000 n=9+10) MatchParallelShared-8 53.1ns ± 1% 39.2ns ± 5% -26.07% (p=0.000 n=8+8) MatchParallelCopied-8 42.0ns ±25% 52.4ns ±46% ~ (p=0.063 n=10+10) QuoteMetaAll-8 69.2ns ±25% 59.1ns ± 2% ~ (p=0.968 n=10+9) QuoteMetaNone-8 31.9ns ± 2% 43.0ns ±24% +34.55% (p=0.000 n=9+10) Compile/Onepass-8 3.61µs ±18% 3.53µs ±25% ~ (p=0.739 n=10+10) Compile/Medium-8 5.70µs ± 2% 9.31µs ± 1% +63.16% (p=0.000 n=10+8) Compile/Hard-8 52.5µs ±24% 50.5µs ±27% ~ (p=0.739 n=10+10) Match/Easy0/16-8 2.87ns ±38% 2.43ns ± 1% -15.41% (p=0.005 n=10+10) Match/Easy0/32-8 29.9ns ± 1% 29.3ns ± 1% -2.06% (p=0.000 n=8+8) Match/Easy0/1K-8 191ns ± 5% 192ns ± 1% ~ (p=0.175 n=10+9) Match/Easy0/32K-8 2.54µs ± 1% 2.52µs ± 1% -0.67% (p=0.004 n=10+10) Match/Easy0/1M-8 159µs ± 7% 148µs ± 1% -7.06% (p=0.000 n=10+10) Match/Easy0/32M-8 5.94ms ± 0% 5.40ms ± 1% -9.01% (p=0.000 n=9+10) Match/Easy0i/16-8 2.49ns ± 1% 2.56ns ± 5% ~ (p=0.083 n=9+10) Match/Easy0i/32-8 515ns ± 1% 61ns ± 7% -88.08% (p=0.000 n=9+10) Match/Easy0i/1K-8 15.3µs ± 4% 7.4µs ± 1% -51.46% (p=0.000 n=10+10) Match/Easy0i/32K-8 634µs ± 1% 275µs ± 1% -56.68% (p=0.000 n=9+10) Match/Easy0i/1M-8 21.7ms ±17% 8.9ms ± 1% -58.96% (p=0.000 n=10+10) Match/Easy0i/32M-8 686ms ± 2% 285ms ± 0% -58.47% (p=0.000 n=9+8) Match/Easy1/16-8 2.54ns ± 3% 2.46ns ± 1% -3.12% (p=0.016 n=10+10) Match/Easy1/32-8 28.5ns ± 5% 26.3ns ± 1% -7.70% (p=0.000 n=8+8) Match/Easy1/1K-8 375ns ± 3% 385ns ±11% ~ (p=0.888 n=9+10) Match/Easy1/32K-8 19.2µs ± 1% 19.8µs ± 2% +3.30% (p=0.000 n=9+9) Match/Easy1/1M-8 730µs ±15% 677µs ± 5% -7.25% (p=0.002 n=9+10) Match/Easy1/32M-8 23.9ms ± 0% 21.9ms ± 2% -8.36% (p=0.000 n=8+8) Match/Medium/16-8 2.60ns ± 1% 2.46ns ± 1% -5.60% (p=0.000 n=9+10) Match/Medium/32-8 401ns ± 1% 410ns ± 2% +2.18% (p=0.000 n=10+7) Match/Medium/1K-8 16.0µs ± 8% 15.0µs ± 7% -5.74% (p=0.013 n=10+9) Match/Medium/32K-8 755µs ±18% 683µs ± 1% -9.64% (p=0.000 n=10+8) Match/Medium/1M-8 22.6ms ± 1% 24.7ms ±13% ~ (p=1.000 n=9+10) Match/Medium/32M-8 767ms ± 1% 699ms ± 1% -8.95% (p=0.000 n=8+9) Match/Hard/16-8 2.60ns ± 1% 2.46ns ± 1% -5.60% (p=0.000 n=9+10) Match/Hard/32-8 770ns ± 5% 739ns ±29% ~ (p=0.083 n=8+10) Match/Hard/1K-8 25.2µs ±24% 23.9µs ±22% -5.35% (p=0.029 n=10+10) Match/Hard/32K-8 1.40ms ±67% 0.97ms ± 6% -31.04% (p=0.004 n=10+8) Match/Hard/1M-8 30.9ms ± 2% 30.7ms ± 2% ~ (p=0.167 n=8+9) Match/Hard/32M-8 1.08s ± 4% 1.02s ±15% -6.12% (p=0.040 n=9+9) Match/Hard1/16-8 2.29µs ± 5% 1.93µs ± 1% -15.73% (p=0.000 n=9+9) Match/Hard1/32-8 4.25µs ± 5% 4.51µs ±24% ~ (p=0.515 n=8+10) Match/Hard1/1K-8 124µs ± 1% 122µs ± 1% -2.26% (p=0.000 n=8+9) Match/Hard1/32K-8 5.85ms ±30% 4.84ms ± 3% ~ (p=0.146 n=10+8) Match/Hard1/1M-8 192ms ±37% 152ms ± 2% ~ (p=0.083 n=10+8) Match/Hard1/32M-8 5.02s ± 4% 4.99s ± 5% ~ (p=0.605 n=9+9) Match_onepass_regex/16-8 207ns ± 3% 164ns ± 6% -20.52% (p=0.000 n=10+10) Match_onepass_regex/32-8 367ns ± 2% 270ns ± 1% -26.53% (p=0.000 n=9+10) Match_onepass_regex/1K-8 9.81µs ± 1% 7.39µs ± 1% -24.67% (p=0.000 n=9+10) Match_onepass_regex/32K-8 313µs ± 1% 235µs ± 1% -24.88% (p=0.000 n=10+10) Match_onepass_regex/1M-8 10.8ms ± 2% 7.5ms ± 1% -30.34% (p=0.000 n=8+10) Match_onepass_regex/32M-8 339ms ± 1% 259ms ± 2% -23.76% (p=0.000 n=10+10) pkg:regexp/syntax goos:linux goarch:amd64 EmptyOpContext-8 93.3ns ± 1% 93.3ns ± 1% ~ (p=0.986 n=10+10) ```

Alloc

``` name old alloc/op new alloc/op delta pkg:regexp goos:linux goarch:amd64 Find-8 0.00B 0.00B ~ (all equal) FindAllNoMatches-8 0.00B 0.00B ~ (all equal) FindString-8 0.00B 0.00B ~ (all equal) FindSubmatch-8 48.0B ± 0% 48.0B ± 0% ~ (all equal) FindStringSubmatch-8 32.0B ± 0% 32.0B ± 0% ~ (all equal) Literal-8 0.00B 0.00B ~ (all equal) NotLiteral-8 0.00B 0.00B ~ (all equal) MatchClass-8 0.00B 0.00B ~ (all equal) MatchClass_InRange-8 0.00B 0.00B ~ (all equal) ReplaceAll-8 96.0B ± 0% 96.0B ± 0% ~ (all equal) AnchoredLiteralShortNonMatch-8 0.00B 0.00B ~ (all equal) AnchoredLiteralLongNonMatch-8 0.00B 0.00B ~ (all equal) AnchoredShortMatch-8 0.00B 0.00B ~ (all equal) AnchoredLongMatch-8 0.00B 0.00B ~ (all equal) OnePassShortA-8 0.00B 0.00B ~ (all equal) NotOnePassShortA-8 0.00B 0.00B ~ (all equal) OnePassShortB-8 0.00B 0.00B ~ (all equal) NotOnePassShortB-8 0.00B 0.00B ~ (all equal) OnePassLongNotPrefix-8 0.00B 0.00B ~ (all equal) MatchParallelShared-8 0.00B 0.00B ~ (all equal) MatchParallelCopied-8 0.00B 0.00B ~ (all equal) QuoteMetaAll-8 64.0B ± 0% 64.0B ± 0% ~ (all equal) QuoteMetaNone-8 0.00B 0.00B ~ (all equal) Compile/Onepass-8 4.02kB ± 0% 4.04kB ± 0% +0.40% (p=0.000 n=10+10) Compile/Medium-8 9.39kB ± 0% 9.41kB ± 0% +0.17% (p=0.000 n=10+10) Compile/Hard-8 84.7kB ± 0% 84.7kB ± 0% +0.02% (p=0.000 n=10+10) Match/Easy0/16-8 0.00B 0.00B ~ (all equal) Match/Easy0/32-8 0.00B 0.00B ~ (all equal) Match/Easy0/1K-8 0.00B 0.00B ~ (all equal) Match/Easy0/32K-8 0.00B 0.00B ~ (all equal) Match/Easy0/1M-8 0.00B 0.00B ~ (all equal) Match/Easy0/32M-8 18.2B ±76% 18.8B ±79% ~ (p=0.125 n=10+10) Match/Easy0i/16-8 0.00B 0.00B ~ (all equal) Match/Easy0i/32-8 0.00B 0.00B ~ (all equal) Match/Easy0i/1K-8 0.00B 0.00B ~ (all equal) Match/Easy0i/32K-8 1.20B ±150% 0.40B ±150% ~ (p=0.626 n=10+10) Match/Easy0i/1M-8 76.7B ±79% 35.2B ±80% ~ (p=0.096 n=10+10) Match/Easy0i/32M-8 2.44kB ±79% 1.06kB ±76% -56.37% (p=0.009 n=10+10) Match/Easy1/16-8 0.00B 0.00B ~ (all equal) Match/Easy1/32-8 0.00B 0.00B ~ (all equal) Match/Easy1/1K-8 0.00B 0.00B ~ (all equal) Match/Easy1/32K-8 0.00B 0.00B ~ (all equal) Match/Easy1/1M-8 3.70B ±19% 1.90B ±111% -48.65% (p=0.005 n=10+10) Match/Easy1/32M-8 67.6B ±132% 118.7B ± 3% ~ (p=0.476 n=10+9) Match/Medium/16-8 0.00B 0.00B ~ (all equal) Match/Medium/32-8 0.00B 0.00B ~ (all equal) Match/Medium/1K-8 0.00B 0.00B ~ (all equal) Match/Medium/32K-8 1.90B ±111% 1.20B ±150% ~ (p=0.465 n=10+10) Match/Medium/1M-8 81.7B ±78% 68.0B ±76% ~ (p=0.165 n=10+10) Match/Medium/32M-8 2.16kB ±76% 1.62kB ±102% ~ (p=0.656 n=10+10) Match/Hard/16-8 0.00B 0.00B ~ (all equal) Match/Hard/32-8 0.00B 0.00B ~ (all equal) Match/Hard/1K-8 0.00B 0.00B ~ (all equal) Match/Hard/32K-8 0.25B ±300% 3.00B ±100% ~ (p=0.056 n=8+10) Match/Hard/1M-8 87.5B ±130% 98.7B ±77% ~ (p=0.814 n=10+10) Match/Hard/32M-8 4.97kB ±79% 2.64kB ±152% -46.88% (p=0.027 n=10+10) Match/Hard1/16-8 0.00B 0.00B ~ (all equal) Match/Hard1/32-8 0.00B 0.00B ~ (all equal) Match/Hard1/1K-8 0.00B 2.00B ±100% +Inf% (p=0.023 n=8+10) Match/Hard1/32K-8 20.0B ±130% 16.4B ±83% ~ (p=0.535 n=10+10) Match/Hard1/1M-8 607B ±76% 772B ±81% ~ (p=0.650 n=10+10) Match/Hard1/32M-8 1.04kB ± 4% 5.44kB ±81% +424.01% (p=0.008 n=8+10) Match_onepass_regex/16-8 0.00B 0.00B ~ (all equal) Match_onepass_regex/32-8 0.00B 0.00B ~ (all equal) Match_onepass_regex/1K-8 0.00B 0.00B ~ (all equal) Match_onepass_regex/32K-8 0.00B 0.00B ~ (all equal) Match_onepass_regex/1M-8 10.7B ±16% 7.0B ± 0% -34.38% (p=0.000 n=9+8) Match_onepass_regex/32M-8 363B ± 5% 269B ±16% -25.91% (p=0.000 n=10+10) pkg:regexp/syntax goos:linux goarch:amd64 EmptyOpContext-8 0.00B 0.00B ~ (all equal) name old allocs/op new allocs/op delta pkg:regexp goos:linux goarch:amd64 Find-8 0.00 0.00 ~ (all equal) FindAllNoMatches-8 0.00 0.00 ~ (all equal) FindString-8 0.00 0.00 ~ (all equal) FindSubmatch-8 1.00 ± 0% 1.00 ± 0% ~ (all equal) FindStringSubmatch-8 1.00 ± 0% 1.00 ± 0% ~ (all equal) Literal-8 0.00 0.00 ~ (all equal) NotLiteral-8 0.00 0.00 ~ (all equal) MatchClass-8 0.00 0.00 ~ (all equal) MatchClass_InRange-8 0.00 0.00 ~ (all equal) ReplaceAll-8 5.00 ± 0% 5.00 ± 0% ~ (all equal) AnchoredLiteralShortNonMatch-8 0.00 0.00 ~ (all equal) AnchoredLiteralLongNonMatch-8 0.00 0.00 ~ (all equal) AnchoredShortMatch-8 0.00 0.00 ~ (all equal) AnchoredLongMatch-8 0.00 0.00 ~ (all equal) OnePassShortA-8 0.00 0.00 ~ (all equal) NotOnePassShortA-8 0.00 0.00 ~ (all equal) OnePassShortB-8 0.00 0.00 ~ (all equal) NotOnePassShortB-8 0.00 0.00 ~ (all equal) OnePassLongNotPrefix-8 0.00 0.00 ~ (all equal) MatchParallelShared-8 0.00 0.00 ~ (all equal) MatchParallelCopied-8 0.00 0.00 ~ (all equal) QuoteMetaAll-8 2.00 ± 0% 2.00 ± 0% ~ (all equal) QuoteMetaNone-8 0.00 0.00 ~ (all equal) Compile/Onepass-8 52.0 ± 0% 52.0 ± 0% ~ (all equal) Compile/Medium-8 112 ± 0% 112 ± 0% ~ (all equal) Compile/Hard-8 424 ± 0% 424 ± 0% ~ (all equal) Match/Easy0/16-8 0.00 0.00 ~ (all equal) Match/Easy0/32-8 0.00 0.00 ~ (all equal) Match/Easy0/1K-8 0.00 0.00 ~ (all equal) Match/Easy0/32K-8 0.00 0.00 ~ (all equal) Match/Easy0/1M-8 0.00 0.00 ~ (all equal) Match/Easy0/32M-8 0.00 0.00 ~ (all equal) Match/Easy0i/16-8 0.00 0.00 ~ (all equal) Match/Easy0i/32-8 0.00 0.00 ~ (all equal) Match/Easy0i/1K-8 0.00 0.00 ~ (all equal) Match/Easy0i/32K-8 0.00 0.00 ~ (all equal) Match/Easy0i/1M-8 0.00 0.00 ~ (all equal) Match/Easy0i/32M-8 5.20 ±81% 1.20 ±100% -76.92% (p=0.009 n=10+10) Match/Easy1/16-8 0.00 0.00 ~ (all equal) Match/Easy1/32-8 0.00 0.00 ~ (all equal) Match/Easy1/1K-8 0.00 0.00 ~ (all equal) Match/Easy1/32K-8 0.00 0.00 ~ (all equal) Match/Easy1/1M-8 0.00 0.00 ~ (all equal) Match/Easy1/32M-8 0.00 0.00 ~ (all equal) Match/Medium/16-8 0.00 0.00 ~ (all equal) Match/Medium/32-8 0.00 0.00 ~ (all equal) Match/Medium/1K-8 0.00 0.00 ~ (all equal) Match/Medium/32K-8 0.00 0.00 ~ (all equal) Match/Medium/1M-8 0.00 0.00 ~ (all equal) Match/Medium/32M-8 4.60 ±78% 3.40 ±106% ~ (p=0.656 n=10+10) Match/Hard/16-8 0.00 0.00 ~ (all equal) Match/Hard/32-8 0.00 0.00 ~ (all equal) Match/Hard/1K-8 0.00 0.00 ~ (all equal) Match/Hard/32K-8 0.00 0.00 ~ (all equal) Match/Hard/1M-8 0.00 0.00 ~ (all equal) Match/Hard/32M-8 13.9 ±86% 7.1 ±168% -48.92% (p=0.027 n=10+10) Match/Hard1/16-8 0.00 0.00 ~ (all equal) Match/Hard1/32-8 0.00 0.00 ~ (all equal) Match/Hard1/1K-8 0.00 0.00 ~ (all equal) Match/Hard1/32K-8 0.00 0.00 ~ (all equal) Match/Hard1/1M-8 2.50 ±100% 3.50 ±100% ~ (p=0.650 n=10+10) Match/Hard1/32M-8 2.25 ±78% 29.30 ±93% +1202.22% (p=0.008 n=8+10) Match_onepass_regex/16-8 0.00 0.00 ~ (all equal) Match_onepass_regex/32-8 0.00 0.00 ~ (all equal) Match_onepass_regex/1K-8 0.00 0.00 ~ (all equal) Match_onepass_regex/32K-8 0.00 0.00 ~ (all equal) Match_onepass_regex/1M-8 0.00 0.00 ~ (all equal) Match_onepass_regex/32M-8 0.60 ±100% 0.00 -100.00% (p=0.011 n=10+10) pkg:regexp/syntax goos:linux goarch:amd64 EmptyOpContext-8 0.00 0.00 ~ (all equal) ```

Speed

``` name old speed new speed delta pkg:regexp goos:linux goarch:amd64 QuoteMetaAll-8 211MB/s ±27% 237MB/s ± 2% ~ (p=0.968 n=10+9) QuoteMetaNone-8 814MB/s ± 2% 640MB/s ±24% -21.36% (p=0.000 n=9+10) Match/Easy0/16-8 5.80GB/s ±30% 6.60GB/s ± 1% +13.75% (p=0.007 n=10+10) Match/Easy0/32-8 1.07GB/s ± 1% 1.09GB/s ± 1% +2.09% (p=0.000 n=8+8) Match/Easy0/1K-8 5.36GB/s ± 4% 5.33GB/s ± 1% ~ (p=0.182 n=10+9) Match/Easy0/32K-8 12.9GB/s ± 1% 13.0GB/s ± 1% +0.68% (p=0.004 n=10+10) Match/Easy0/1M-8 6.59GB/s ± 7% 7.08GB/s ± 1% +7.46% (p=0.000 n=10+10) Match/Easy0/32M-8 5.65GB/s ± 0% 6.21GB/s ± 1% +9.90% (p=0.000 n=9+10) Match/Easy0i/16-8 6.44GB/s ± 1% 6.25GB/s ± 5% ~ (p=0.079 n=9+10) Match/Easy0i/32-8 62.2MB/s ± 1% 522.6MB/s ± 7% +740.58% (p=0.000 n=9+10) Match/Easy0i/1K-8 67.1MB/s ± 4% 138.1MB/s ± 1% +105.87% (p=0.000 n=10+10) Match/Easy0i/32K-8 51.7MB/s ± 1% 119.4MB/s ± 1% +130.83% (p=0.000 n=9+10) Match/Easy0i/1M-8 48.7MB/s ±15% 117.9MB/s ± 1% +142.15% (p=0.000 n=10+10) Match/Easy0i/32M-8 48.9MB/s ± 2% 117.9MB/s ± 0% +140.78% (p=0.000 n=9+8) Match/Easy1/16-8 6.31GB/s ± 3% 6.51GB/s ± 1% +3.14% (p=0.019 n=10+10) Match/Easy1/32-8 1.10GB/s ±14% 1.22GB/s ± 1% +10.11% (p=0.000 n=9+8) Match/Easy1/1K-8 2.73GB/s ± 3% 2.67GB/s ±11% ~ (p=0.905 n=9+10) Match/Easy1/32K-8 1.71GB/s ± 1% 1.66GB/s ± 2% -3.19% (p=0.000 n=9+9) Match/Easy1/1M-8 1.42GB/s ±14% 1.55GB/s ± 5% +9.12% (p=0.001 n=10+10) Match/Easy1/32M-8 1.41GB/s ± 0% 1.53GB/s ± 2% +9.13% (p=0.000 n=8+8) Match/Medium/16-8 6.15GB/s ± 1% 6.51GB/s ± 1% +5.94% (p=0.000 n=9+10) Match/Medium/32-8 79.8MB/s ± 1% 78.1MB/s ± 2% -2.12% (p=0.000 n=10+7) Match/Medium/1K-8 64.3MB/s ± 8% 68.1MB/s ± 6% +5.93% (p=0.013 n=10+9) Match/Medium/32K-8 43.7MB/s ±16% 48.0MB/s ± 1% +9.83% (p=0.000 n=10+8) Match/Medium/1M-8 46.4MB/s ± 1% 43.1MB/s ±13% ~ (p=1.000 n=9+10) Match/Medium/32M-8 43.7MB/s ± 1% 48.0MB/s ± 1% +9.83% (p=0.000 n=8+9) Match/Hard/16-8 6.15GB/s ± 1% 6.51GB/s ± 1% +5.93% (p=0.000 n=9+10) Match/Hard/32-8 41.6MB/s ± 5% 44.0MB/s ±24% ~ (p=0.083 n=8+10) Match/Hard/1K-8 41.5MB/s ±21% 43.7MB/s ±20% +5.24% (p=0.028 n=10+10) Match/Hard/32K-8 25.5MB/s ±45% 33.2MB/s ±17% +30.12% (p=0.008 n=10+9) Match/Hard/1M-8 33.9MB/s ± 2% 34.2MB/s ± 2% ~ (p=0.145 n=8+9) Match/Hard/32M-8 31.0MB/s ± 4% 32.3MB/s ±24% ~ (p=0.133 n=9+10) Match/Hard1/16-8 6.98MB/s ± 5% 8.27MB/s ± 1% +18.62% (p=0.000 n=9+9) Match/Hard1/32-8 7.53MB/s ± 5% 7.29MB/s ±21% ~ (p=0.500 n=8+10) Match/Hard1/1K-8 8.23MB/s ± 1% 8.42MB/s ± 1% +2.28% (p=0.000 n=8+9) Match/Hard1/32K-8 5.83MB/s ±26% 6.78MB/s ± 3% ~ (p=0.152 n=10+8) Match/Hard1/1M-8 5.69MB/s ±30% 6.91MB/s ± 2% ~ (p=0.064 n=10+8) Match/Hard1/32M-8 6.69MB/s ± 4% 6.74MB/s ± 5% ~ (p=0.649 n=9+9) Match_onepass_regex/16-8 77.4MB/s ± 3% 97.4MB/s ± 6% +25.93% (p=0.000 n=10+10) Match_onepass_regex/32-8 87.2MB/s ± 2% 118.7MB/s ± 1% +36.10% (p=0.000 n=9+10) Match_onepass_regex/1K-8 104MB/s ± 1% 139MB/s ± 1% +32.75% (p=0.000 n=9+10) Match_onepass_regex/32K-8 105MB/s ± 1% 139MB/s ± 1% +33.12% (p=0.000 n=10+10) Match_onepass_regex/1M-8 96.9MB/s ± 2% 139.1MB/s ± 1% +43.54% (p=0.000 n=8+10) Match_onepass_regex/32M-8 98.9MB/s ± 1% 129.8MB/s ± 2% +31.19% (p=0.000 n=10+10) ```

[zikaeroh]

CL 355789 (the "exceptionally small" yet powerful CL mentioned previously) has been merged for Go 1.19! 🎉

(The CL didn't mention this issue, so the commit didn't trigger a thread update, hence me mentioning since so many are following this thread. The other 4 CLs are still pending review.)

[stevekm]

are there other significant performance increases in the works, or is the current 1.19 release considered "good enough" compared to other languages that speed is no longer an issue?

[zikaeroh]

Of the CLs I listed in https://github.com/golang/go/issues/26623#issuecomment-1033158328, only one has been reviewed and merged; the rest remain unreviewed. There are certainly a few boosts in there.

(I can't answer a question about what defines "good enough".)

[junyer]

https://github.com/golang/go/issues/11646 isn't "in the works" anymore, evidently, which is unfortunate, but unsurprising due to its complexity.

[AndrewSav]

Just out of curiosity updated the versions and ran it today:

Language	Email(ms)	URI(ms)	IP(ms)	Total(ms)
Rust	2.02	1.67	2.46	6.15
C++ SRELL	3.35	3.68	10.08	17.10
C# .Net Core	6.46	3.79	19.35	29.59
Nim Regex	0.94	24.68	6.52	32.14
PHP	15.03	17.70	3.50	36.23
Nim	15.74	16.17	4.99	36.89
Julia	36.72	35.87	3.81	76.39
C++ Boost	35.97	35.17	11.78	82.91
Javascript	47.19	35.78	1.02	84.00
Perl	89.80	58.62	15.88	164.30
Crystal	83.45	72.39	8.89	164.74
C PCRE2	89.19	81.06	10.35	180.59
Dart	68.68	67.70	51.04	187.43
D dmd	137.56	143.07	4.91	285.54
D ldc	180.59	136.11	4.46	321.16
Ruby	187.45	166.59	35.49	389.53
Python PyPy2	119.10	98.73	176.11	393.94
Java	120.06	162.12	206.36	488.54
Kotlin	116.40	183.73	206.46	506.59
Python PyPy3	180.68	155.52	174.64	510.84
Python 2	175.05	122.20	238.39	535.64
Dart Native	268.49	297.90	4.43	570.81
Go	184.79	176.84	270.63	632.26
Python 3	235.18	179.36	265.39	679.94
C++ STL	338.12	269.98	183.98	792.08
C# Mono	1994.57	1725.52	96.81	3816.91