Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

regexp: investigate further performance improvements #26623

Open
hsluoyz opened this Issue Jul 26, 2018 · 15 comments

Comments

Projects
None yet
@hsluoyz
Copy link

commented Jul 26, 2018

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: #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 ianlancetaylor changed the title Go's regex is even slower than Python regexp: Go's regex is even slower than Python Jul 26, 2018

@ianlancetaylor

This comment has been minimized.

Copy link
Contributor

commented Jul 26, 2018

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?

@andybons andybons added this to the Unplanned milestone Jul 26, 2018

@mvdan

This comment has been minimized.

Copy link
Member

commented Jul 26, 2018

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

This comment has been minimized.

Copy link

commented Jul 27, 2018

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

This comment has been minimized.

Copy link

commented Jul 27, 2018

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.

mariomka/regex-benchmark#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

This comment has been minimized.

Copy link
Member

commented Jul 27, 2018

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

This comment has been minimized.

Copy link
Contributor

commented Aug 9, 2018

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

This comment has been minimized.

Copy link
Contributor

commented Aug 18, 2018

My comments on #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

This comment has been minimized.

Copy link

commented Aug 22, 2018

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

gopherbot pushed a commit that referenced this issue Aug 22, 2018

regexp/syntax: don't do both linear and binary sesarch in MatchRunePos
MatchRunePos is a significant element of regexp performance, so some
attention to optimization is appropriate. Before this CL, a
non-matching rune would do both a linear search in the first four
entries, and a binary search over all the entries. Change the code to
optimize for the common case of two runes, to only do a linear search
when there are up to four entries, and to only do a binary search when
there are more than four entries.

Updates #26623

name                             old time/op    new time/op    delta
Find-12                             260ns ± 1%     275ns ± 7%   +5.84%  (p=0.000 n=8+10)
FindAllNoMatches-12                 144ns ± 9%     143ns ±12%     ~     (p=0.187 n=10+10)
FindString-12                       256ns ± 4%     254ns ± 1%     ~     (p=0.357 n=9+8)
FindSubmatch-12                     587ns ±12%     593ns ±11%     ~     (p=0.516 n=10+10)
FindStringSubmatch-12               534ns ±12%     525ns ±14%     ~     (p=0.565 n=10+10)
Literal-12                          104ns ±14%     106ns ±11%     ~     (p=0.145 n=10+10)
NotLiteral-12                      1.51µs ± 8%    1.47µs ± 2%     ~     (p=0.508 n=10+9)
MatchClass-12                      2.47µs ± 1%    2.26µs ± 6%   -8.55%  (p=0.000 n=8+10)
MatchClass_InRange-12              2.18µs ± 5%    2.25µs ±11%   +2.85%  (p=0.009 n=9+10)
ReplaceAll-12                      2.35µs ± 6%    2.08µs ±23%  -11.59%  (p=0.010 n=9+10)
AnchoredLiteralShortNonMatch-12    93.2ns ± 9%    93.2ns ±11%     ~     (p=0.716 n=10+10)
AnchoredLiteralLongNonMatch-12      118ns ±10%     117ns ± 9%     ~     (p=0.802 n=10+10)
AnchoredShortMatch-12               142ns ± 1%     141ns ± 1%   -0.53%  (p=0.007 n=8+8)
AnchoredLongMatch-12                303ns ± 9%     304ns ± 6%     ~     (p=0.724 n=10+10)
OnePassShortA-12                    620ns ± 1%     618ns ± 9%     ~     (p=0.162 n=8+10)
NotOnePassShortA-12                 599ns ± 8%     568ns ± 1%   -5.21%  (p=0.000 n=10+8)
OnePassShortB-12                    525ns ± 7%     489ns ± 1%   -6.93%  (p=0.000 n=10+8)
NotOnePassShortB-12                 449ns ± 9%     431ns ±11%   -4.05%  (p=0.033 n=10+10)
OnePassLongPrefix-12                119ns ± 6%     114ns ± 0%   -3.88%  (p=0.006 n=10+9)
OnePassLongNotPrefix-12             420ns ± 9%     410ns ± 7%     ~     (p=0.645 n=10+9)
MatchParallelShared-12              376ns ± 0%     375ns ± 0%   -0.45%  (p=0.003 n=8+10)
MatchParallelCopied-12             39.4ns ± 1%    39.1ns ± 0%   -0.55%  (p=0.004 n=10+9)
QuoteMetaAll-12                     139ns ± 7%     142ns ± 7%     ~     (p=0.445 n=10+10)
QuoteMetaNone-12                   56.7ns ± 0%    61.3ns ± 7%   +8.03%  (p=0.001 n=8+10)
Match/Easy0/32-12                  83.4ns ± 7%    83.1ns ± 8%     ~     (p=0.541 n=10+10)
Match/Easy0/1K-12                   417ns ± 8%     394ns ± 6%     ~     (p=0.059 n=10+9)
Match/Easy0/32K-12                 7.05µs ± 8%    7.30µs ± 9%     ~     (p=0.190 n=10+10)
Match/Easy0/1M-12                   291µs ±17%     284µs ±10%     ~     (p=0.481 n=10+10)
Match/Easy0/32M-12                 9.89ms ± 4%   10.27ms ± 8%     ~     (p=0.315 n=10+10)
Match/Easy0i/32-12                 1.13µs ± 1%    1.14µs ± 1%   +1.51%  (p=0.000 n=8+8)
Match/Easy0i/1K-12                 35.7µs ±11%    36.8µs ±10%     ~     (p=0.143 n=10+10)
Match/Easy0i/32K-12                1.70ms ± 7%    1.72ms ± 7%     ~     (p=0.776 n=9+6)

name                             old alloc/op   new alloc/op   delta
Find-12                             0.00B          0.00B          ~     (all equal)
FindAllNoMatches-12                 0.00B          0.00B          ~     (all equal)
FindString-12                       0.00B          0.00B          ~     (all equal)
FindSubmatch-12                     48.0B ± 0%     48.0B ± 0%     ~     (all equal)
FindStringSubmatch-12               32.0B ± 0%     32.0B ± 0%     ~     (all equal)

name                             old allocs/op  new allocs/op  delta
Find-12                              0.00           0.00          ~     (all equal)
FindAllNoMatches-12                  0.00           0.00          ~     (all equal)
FindString-12                        0.00           0.00          ~     (all equal)
FindSubmatch-12                      1.00 ± 0%      1.00 ± 0%     ~     (all equal)
FindStringSubmatch-12                1.00 ± 0%      1.00 ± 0%     ~     (all equal)

name                             old speed      new speed      delta
QuoteMetaAll-12                   101MB/s ± 8%    99MB/s ± 7%     ~     (p=0.529 n=10+10)
QuoteMetaNone-12                  458MB/s ± 0%   425MB/s ± 8%   -7.22%  (p=0.003 n=8+10)
Match/Easy0/32-12                 385MB/s ± 7%   386MB/s ± 7%     ~     (p=0.579 n=10+10)
Match/Easy0/1K-12                2.46GB/s ± 8%  2.60GB/s ± 6%     ~     (p=0.065 n=10+9)
Match/Easy0/32K-12               4.66GB/s ± 7%  4.50GB/s ±10%     ~     (p=0.190 n=10+10)
Match/Easy0/1M-12                3.63GB/s ±15%  3.70GB/s ± 9%     ~     (p=0.481 n=10+10)
Match/Easy0/32M-12               3.40GB/s ± 4%  3.28GB/s ± 8%     ~     (p=0.315 n=10+10)
Match/Easy0i/32-12               28.4MB/s ± 1%  28.0MB/s ± 1%   -1.50%  (p=0.000 n=8+8)
Match/Easy0i/1K-12               28.8MB/s ±10%  27.9MB/s ±11%     ~     (p=0.143 n=10+10)
Match/Easy0i/32K-12              19.0MB/s ±14%  19.1MB/s ± 8%     ~     (p=1.000 n=10+6)

Change-Id: I238a451b36ad84b0f5534ff0af5c077a0d52d73a
Reviewed-on: https://go-review.googlesource.com/130417
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
@gopherbot

This comment has been minimized.

Copy link

commented Aug 26, 2018

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

@gopherbot gopherbot closed this Aug 26, 2018

@josharian

This comment has been minimized.

Copy link
Contributor

commented Aug 26, 2018

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

@josharian josharian reopened this Aug 26, 2018

@gopherbot gopherbot closed this Aug 26, 2018

@mvdan mvdan removed the WaitingForInfo label Aug 26, 2018

@mvdan mvdan reopened this Aug 26, 2018

@mvdan

This comment has been minimized.

Copy link
Member

commented Aug 26, 2018

I think @gopherbot needs to be taught some manners.

@agnivade

This comment has been minimized.

Copy link
Member

commented Nov 15, 2018

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.

@agnivade agnivade changed the title regexp: Go's regex is even slower than Python regexp: investigate further performance improvements Nov 15, 2018

@junyer

This comment has been minimized.

Copy link
Contributor

commented Nov 27, 2018

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

This comment has been minimized.

Copy link
Contributor

commented Nov 27, 2018

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

@junyer

This comment has been minimized.

Copy link
Contributor

commented Nov 27, 2018

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.