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: MatchString run time could be independent of the string length #39480

Closed
opennota opened this issue Jun 9, 2020 · 2 comments
Closed

regexp: MatchString run time could be independent of the string length #39480

opennota opened this issue Jun 9, 2020 · 2 comments

Comments

@opennota
Copy link

@opennota opennota commented Jun 9, 2020

What version of Go are you using (go version)?

$ go version
go version go1.14.4 linux/amd64

Does this issue reproduce with the latest release?

Yes.

What operating system and processor architecture are you using (go env)?

go env Output
$ go env
GO111MODULE=""
GOARCH="amd64"
GOBIN=""
GOCACHE="/home/xxx/.cache/go-build"
GOENV="/home/xxx/.config/go/env"
GOEXE=""
GOFLAGS=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOINSECURE=""
GONOPROXY=""
GONOSUMDB=""
GOOS="linux"
GOPATH="/home/xxx/gocode"
GOPRIVATE=""
GOPROXY="direct"
GOROOT="/home/xxx/go"
GOSUMDB="off"
GOTMPDIR=""
GOTOOLDIR="/home/xxx/go/pkg/tool/linux_amd64"
GCCGO="gccgo"
AR="ar"
CC="gcc"
CXX="g++"
CGO_ENABLED="1"
GOMOD="/home/xxx/gocode/src/gitlab.com/opennota/tl/go.mod"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
PKG_CONFIG="pkg-config"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build900652540=/tmp/go-build -gno-record-gcc-switches"

What did you do?

go test -bench=.

https://play.golang.org/p/VD6DFGlxha-

What did you expect to see?

Both benchmarks show about the same ns/op.

What did you see instead?

BenchmarkLength1-4      13320451                89.7 ns/op
BenchmarkLength1M-4      8138482               143 ns/op

The difference seems to be constant, but it's a bit surprising.

@randall77
Copy link
Contributor

@randall77 randall77 commented Jun 9, 2020

Run the CPU profiler and see where the extra time is going.

@opennota
Copy link
Author

@opennota opennota commented Jun 16, 2020

It looks like the regexp package uses backtracking for strings which are short enough, and does not for longer ones. So this difference in speed is probably expected.

@opennota opennota closed this Jun 16, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
3 participants
You can’t perform that action at this time.