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: needless allocations when compiling onepass regex #19735

Closed
haya14busa opened this issue Mar 28, 2017 · 3 comments
Closed

regexp: needless allocations when compiling onepass regex #19735

haya14busa opened this issue Mar 28, 2017 · 3 comments

Comments

@haya14busa
Copy link
Contributor

@haya14busa haya14busa commented Mar 28, 2017

What did you do?

I ran benchmark of my program which contains compiling onepass regex and noticed that we can specify onePassProg.Inst capacity.

go/src/regexp/onepass.go

Lines 222 to 228 in 73912a1

p := &onePassProg{
Start: prog.Start,
NumCap: prog.NumCap,
}
for _, inst := range prog.Inst {
p.Inst = append(p.Inst, onePassInst{Inst: inst})
}

What did you expect to see?

Allocation by append() will be reduced by specifying cap.

What did you see instead?

cap is not specified and it leads needless allocation.

System details

go version go1.8 linux/amd64
GOARCH="amd64"
GOBIN="/home/haya14busa/go/bin"
GOEXE=""
GOHOSTARCH="amd64"
GOHOSTOS="linux"
GOOS="linux"
GOPATH="/home/haya14busa"
GORACE=""
GOROOT="/usr/lib/go"
GOTOOLDIR="/usr/lib/go/pkg/tool/linux_amd64"
GCCGO="gccgo"
CC="gcc"
GOGCCFLAGS="-fPIC -m64 -pthread -fmessage-length=0 -fdebug-prefix-map=/tmp/go-build567867684=/tmp/go-build -gno-record-gcc-switches"
CXX="g++"
CGO_ENABLED="1"
PKG_CONFIG="pkg-config"
CGO_CFLAGS="-g -O2"
CGO_CPPFLAGS=""
CGO_CXXFLAGS="-g -O2"
CGO_FFLAGS="-g -O2"
CGO_LDFLAGS="-g -O2"
GOROOT/bin/go version: go version go1.8 linux/amd64
GOROOT/bin/go tool compile -V: compile version go1.8 X:framepointer
uname -sr: Linux 4.4.48-1-MANJARO
LSB Version:	n/a
Distributor ID:	ManjaroLinux
Description:	Manjaro Linux
Release:	16.10
Codename:	Fringilla
/usr/lib/libc.so.6: GNU C Library (GNU libc) stable release version 2.24, by Roland McGrath et al.
gdb --version: GNU gdb (GDB) 7.12.1

Also, go version devel +73912a1 Mon Mar 27 23:36:36 2017 +0000 linux/amd64

I'll send a CL soon.

@gopherbot
Copy link

@gopherbot gopherbot commented Mar 28, 2017

CL https://golang.org/cl/38750 mentions this issue.

@gopherbot
Copy link

@gopherbot gopherbot commented Mar 28, 2017

CL https://golang.org/cl/38751 mentions this issue.

@dongweigogo
Copy link

@dongweigogo dongweigogo commented Mar 28, 2017

Great, the Go regex engine does need improvements. Its current performance is too weak.

@gopherbot gopherbot closed this in f5c1926 Mar 28, 2017
gopherbot pushed a commit that referenced this issue Mar 29, 2017
It reduces needless allocations on compiling onepass regex.

Following CL 38750

name                                      old time/op    new time/op    delta
CompileOnepass/^(?:(?:(?:.(?:$))?))...-4    5.75µs ± 1%    5.51µs ± 2%   -4.25%  (p=0.008 n=5+5)
CompileOnepass/^abcd$-4                     4.76µs ± 0%    4.52µs ± 1%   -5.06%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a{0,})*?)$-4          5.56µs ± 0%    5.56µs ± 3%     ~     (p=0.524 n=5+5)
CompileOnepass/^(?:(?:a+)*)$-4              5.09µs ± 0%    5.15µs ± 5%     ~     (p=0.690 n=5+5)
CompileOnepass/^(?:(?:a|(?:aa)))$-4         6.53µs ± 0%    6.43µs ± 5%     ~     (p=0.151 n=5+5)
CompileOnepass/^(?:[^\s\S])$-4              4.05µs ± 1%    4.00µs ± 2%     ~     (p=0.095 n=5+5)
CompileOnepass/^(?:(?:(?:a*)+))$-4          5.47µs ± 0%    5.36µs ± 1%   -1.91%  (p=0.008 n=5+5)
CompileOnepass/^[a-c]+$-4                   4.13µs ± 1%    4.05µs ± 0%   -2.07%  (p=0.008 n=5+5)
CompileOnepass/^[a-c]*$-4                   4.59µs ± 2%    4.93µs ± 7%   +7.30%  (p=0.016 n=5+5)
CompileOnepass/^(?:a*)$-4                   4.67µs ± 1%    4.82µs ± 8%     ~     (p=0.730 n=4+5)
CompileOnepass/^(?:(?:aa)|a)$-4             6.43µs ± 1%    6.18µs ± 1%   -3.91%  (p=0.008 n=5+5)
CompileOnepass/^...$-4                      4.71µs ± 0%    4.31µs ± 1%   -8.51%  (p=0.008 n=5+5)
CompileOnepass/^(?:a|(?:aa))$-4             6.37µs ± 0%    6.17µs ± 0%   -3.23%  (p=0.008 n=5+5)
CompileOnepass/^a((b))c$-4                  6.85µs ± 1%    6.50µs ± 1%   -5.15%  (p=0.008 n=5+5)
CompileOnepass/^a.[l-nA-Cg-j]?e$-4          6.99µs ± 1%    6.66µs ± 1%   -4.81%  (p=0.008 n=5+5)
CompileOnepass/^a((b))$-4                   6.15µs ± 1%    5.87µs ± 0%   -4.57%  (p=0.008 n=5+5)
CompileOnepass/^a(?:(b)|(c))c$-4            8.62µs ± 1%    8.21µs ± 1%   -4.77%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b|c)$-4                 5.76µs ±42%    4.42µs ± 1%  -23.35%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c)$-4                7.17µs ± 6%    6.86µs ± 0%   -4.39%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c+)$-4               8.08µs ± 2%    7.67µs ± 2%   -4.97%  (p=0.008 n=5+5)
CompileOnepass/^a(?:bc)+$-4                 5.53µs ± 3%    5.35µs ± 1%   -3.34%  (p=0.008 n=5+5)
CompileOnepass/^a(?:[bcd])+$-4              5.08µs ± 1%    4.98µs ± 0%   -2.02%  (p=0.008 n=5+5)
CompileOnepass/^a((?:[bcd])+)$-4            6.49µs ± 1%    6.29µs ± 1%   -3.03%  (p=0.008 n=5+5)
CompileOnepass/^a(:?b|c)*d$-4               11.8µs ± 1%    11.4µs ± 3%   -3.98%  (p=0.008 n=5+5)
CompileOnepass/^.bc(d|e)*$-4                8.02µs ± 1%    7.54µs ± 1%   -6.00%  (p=0.008 n=5+5)
CompileOnepass/^loooooooooooooooooo...-4     228µs ±18%     196µs ± 0%  -14.02%  (p=0.016 n=5+4)

name                                      old alloc/op   new alloc/op   delta
CompileOnepass/^(?:(?:(?:.(?:$))?))...-4    3.41kB ± 0%    3.38kB ± 0%   -0.94%  (p=0.008 n=5+5)
CompileOnepass/^abcd$-4                     2.75kB ± 0%    2.74kB ± 0%   -0.29%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a{0,})*?)$-4          3.34kB ± 0%    3.34kB ± 0%     ~     (all equal)
CompileOnepass/^(?:(?:a+)*)$-4              2.95kB ± 0%    2.95kB ± 0%     ~     (all equal)
CompileOnepass/^(?:(?:a|(?:aa)))$-4         3.75kB ± 0%    3.74kB ± 0%   -0.43%  (p=0.008 n=5+5)
CompileOnepass/^(?:[^\s\S])$-4              2.46kB ± 0%    2.45kB ± 0%   -0.49%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:(?:a*)+))$-4          3.13kB ± 0%    3.13kB ± 0%     ~     (all equal)
CompileOnepass/^[a-c]+$-4                   2.48kB ± 0%    2.48kB ± 0%     ~     (all equal)
CompileOnepass/^[a-c]*$-4                   2.52kB ± 0%    2.52kB ± 0%     ~     (all equal)
CompileOnepass/^(?:a*)$-4                   2.63kB ± 0%    2.63kB ± 0%     ~     (all equal)
CompileOnepass/^(?:(?:aa)|a)$-4             3.64kB ± 0%    3.62kB ± 0%   -0.44%  (p=0.008 n=5+5)
CompileOnepass/^...$-4                      2.91kB ± 0%    2.87kB ± 0%   -1.37%  (p=0.008 n=5+5)
CompileOnepass/^(?:a|(?:aa))$-4             3.64kB ± 0%    3.62kB ± 0%   -0.44%  (p=0.008 n=5+5)
CompileOnepass/^a((b))c$-4                  4.39kB ± 0%    4.38kB ± 0%   -0.18%  (p=0.008 n=5+5)
CompileOnepass/^a.[l-nA-Cg-j]?e$-4          4.32kB ± 0%    4.30kB ± 0%   -0.56%  (p=0.008 n=5+5)
CompileOnepass/^a((b))$-4                   4.06kB ± 0%    4.05kB ± 0%   -0.39%  (p=0.008 n=5+5)
CompileOnepass/^a(?:(b)|(c))c$-4            5.31kB ± 0%    5.30kB ± 0%   -0.15%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b|c)$-4                 2.88kB ± 0%    2.87kB ± 0%   -0.28%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c)$-4                4.36kB ± 0%    4.35kB ± 0%   -0.18%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c+)$-4               4.59kB ± 0%    4.58kB ± 0%   -0.17%  (p=0.008 n=5+5)
CompileOnepass/^a(?:bc)+$-4                 3.15kB ± 0%    3.15kB ± 0%     ~     (all equal)
CompileOnepass/^a(?:[bcd])+$-4              2.94kB ± 0%    2.94kB ± 0%     ~     (all equal)
CompileOnepass/^a((?:[bcd])+)$-4            4.09kB ± 0%    4.08kB ± 0%   -0.20%  (p=0.008 n=5+5)
CompileOnepass/^a(:?b|c)*d$-4               6.15kB ± 0%    6.10kB ± 0%   -0.78%  (p=0.008 n=5+5)
CompileOnepass/^.bc(d|e)*$-4                4.47kB ± 0%    4.46kB ± 0%   -0.36%  (p=0.008 n=5+5)
CompileOnepass/^loooooooooooooooooo...-4     135kB ± 0%     135kB ± 0%     ~     (p=0.810 n=5+5)

name                                      old allocs/op  new allocs/op  delta
CompileOnepass/^(?:(?:(?:.(?:$))?))...-4      49.0 ± 0%      47.0 ± 0%   -4.08%  (p=0.008 n=5+5)
CompileOnepass/^abcd$-4                       41.0 ± 0%      41.0 ± 0%     ~     (all equal)
CompileOnepass/^(?:(?:a{0,})*?)$-4            49.0 ± 0%      49.0 ± 0%     ~     (all equal)
CompileOnepass/^(?:(?:a+)*)$-4                44.0 ± 0%      44.0 ± 0%     ~     (all equal)
CompileOnepass/^(?:(?:a|(?:aa)))$-4           54.0 ± 0%      54.0 ± 0%     ~     (all equal)
CompileOnepass/^(?:[^\s\S])$-4                33.0 ± 0%      33.0 ± 0%     ~     (all equal)
CompileOnepass/^(?:(?:(?:a*)+))$-4            46.0 ± 0%      46.0 ± 0%     ~     (all equal)
CompileOnepass/^[a-c]+$-4                     36.0 ± 0%      36.0 ± 0%     ~     (all equal)
CompileOnepass/^[a-c]*$-4                     41.0 ± 0%      41.0 ± 0%     ~     (all equal)
CompileOnepass/^(?:a*)$-4                     42.0 ± 0%      42.0 ± 0%     ~     (all equal)
CompileOnepass/^(?:(?:aa)|a)$-4               53.0 ± 0%      53.0 ± 0%     ~     (all equal)
CompileOnepass/^...$-4                        43.0 ± 0%      39.0 ± 0%   -9.30%  (p=0.008 n=5+5)
CompileOnepass/^(?:a|(?:aa))$-4               53.0 ± 0%      53.0 ± 0%     ~     (all equal)
CompileOnepass/^a((b))c$-4                    53.0 ± 0%      53.0 ± 0%     ~     (all equal)
CompileOnepass/^a.[l-nA-Cg-j]?e$-4            58.0 ± 0%      56.0 ± 0%   -3.45%  (p=0.008 n=5+5)
CompileOnepass/^a((b))$-4                     47.0 ± 0%      47.0 ± 0%     ~     (all equal)
CompileOnepass/^a(?:(b)|(c))c$-4              65.0 ± 0%      65.0 ± 0%     ~     (all equal)
CompileOnepass/^a(?:b|c)$-4                   40.0 ± 0%      40.0 ± 0%     ~     (all equal)
CompileOnepass/^a(?:b?|c)$-4                  57.0 ± 0%      57.0 ± 0%     ~     (all equal)
CompileOnepass/^a(?:b?|c+)$-4                 63.0 ± 0%      63.0 ± 0%     ~     (all equal)
CompileOnepass/^a(?:bc)+$-4                   46.0 ± 0%      46.0 ± 0%     ~     (all equal)
CompileOnepass/^a(?:[bcd])+$-4                43.0 ± 0%      43.0 ± 0%     ~     (all equal)
CompileOnepass/^a((?:[bcd])+)$-4              49.0 ± 0%      49.0 ± 0%     ~     (all equal)
CompileOnepass/^a(:?b|c)*d$-4                  105 ± 0%       101 ± 0%   -3.81%  (p=0.008 n=5+5)
CompileOnepass/^.bc(d|e)*$-4                  62.0 ± 0%      60.0 ± 0%   -3.23%  (p=0.008 n=5+5)
CompileOnepass/^loooooooooooooooooo...-4     1.09k ± 0%     1.09k ± 0%     ~     (all equal)

Fixes #19735

Change-Id: Ib90e18e1b06166407b26b2a68b88afbb1f486024
Reviewed-on: https://go-review.googlesource.com/38751
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
lparth added a commit to lparth/go that referenced this issue Apr 13, 2017
It reduces needless allocations on compiling onepass regex.

name                                      old time/op    new time/op    delta
CompileOnepass/^(?:(?:(?:.(?:$))?))...-4    6.31µs ± 3%    6.11µs ± 3%     ~     (p=0.056 n=5+5)
CompileOnepass/^abcd$-4                     5.69µs ±12%    4.93µs ± 4%  -13.42%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a{0,})*?)$-4          7.10µs ±12%    5.82µs ± 5%  -17.95%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a+)*)$-4              5.99µs ±10%    6.07µs ±11%     ~     (p=1.000 n=5+5)
CompileOnepass/^(?:(?:a|(?:aa)))$-4         7.36µs ± 4%    7.81µs ±19%     ~     (p=0.310 n=5+5)
CompileOnepass/^(?:[^\s\S])$-4              4.71µs ± 3%    4.71µs ± 5%     ~     (p=1.000 n=5+5)
CompileOnepass/^(?:(?:(?:a*)+))$-4          6.06µs ± 2%    6.23µs ± 9%     ~     (p=0.310 n=5+5)
CompileOnepass/^[a-c]+$-4                   4.74µs ± 4%    4.64µs ± 6%     ~     (p=0.421 n=5+5)
CompileOnepass/^[a-c]*$-4                   5.17µs ± 2%    4.68µs ± 0%   -9.57%  (p=0.016 n=5+4)
CompileOnepass/^(?:a*)$-4                   5.34µs ± 3%    5.08µs ±12%     ~     (p=0.151 n=5+5)
CompileOnepass/^(?:(?:aa)|a)$-4             7.24µs ± 5%    7.33µs ±12%     ~     (p=0.841 n=5+5)
CompileOnepass/^...$-4                      5.28µs ± 3%    4.99µs ± 9%     ~     (p=0.095 n=5+5)
CompileOnepass/^(?:a|(?:aa))$-4             7.20µs ± 4%    7.24µs ±10%     ~     (p=0.841 n=5+5)
CompileOnepass/^a((b))c$-4                  7.99µs ± 3%    7.76µs ± 8%     ~     (p=0.151 n=5+5)
CompileOnepass/^a.[l-nA-Cg-j]?e$-4          8.30µs ± 5%    7.29µs ± 4%  -12.08%  (p=0.008 n=5+5)
CompileOnepass/^a((b))$-4                   7.34µs ± 4%    7.24µs ±19%     ~     (p=0.690 n=5+5)
CompileOnepass/^a(?:(b)|(c))c$-4            9.80µs ± 6%    9.49µs ±18%     ~     (p=0.151 n=5+5)
CompileOnepass/^a(?:b|c)$-4                 5.23µs ± 3%    4.80µs ±10%     ~     (p=0.056 n=5+5)
CompileOnepass/^a(?:b?|c)$-4                8.26µs ± 3%    7.30µs ± 3%  -11.62%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c+)$-4               9.18µs ± 2%    8.16µs ± 2%  -11.06%  (p=0.008 n=5+5)
CompileOnepass/^a(?:bc)+$-4                 6.16µs ± 3%    6.41µs ±13%     ~     (p=0.548 n=5+5)
CompileOnepass/^a(?:[bcd])+$-4              5.75µs ± 5%    5.50µs ±12%     ~     (p=0.151 n=5+5)
CompileOnepass/^a((?:[bcd])+)$-4            7.65µs ± 5%    6.93µs ± 9%     ~     (p=0.056 n=5+5)
CompileOnepass/^a(:?b|c)*d$-4               13.0µs ± 1%    12.1µs ± 2%   -6.91%  (p=0.008 n=5+5)
CompileOnepass/^.bc(d|e)*$-4                9.20µs ± 4%    8.25µs ± 3%  -10.38%  (p=0.008 n=5+5)
CompileOnepass/^loooooooooooooooooo...-4     254µs ± 2%     220µs ± 6%  -13.47%  (p=0.008 n=5+5)

name                                      old alloc/op   new alloc/op   delta
CompileOnepass/^(?:(?:(?:.(?:$))?))...-4    3.92kB ± 0%    3.41kB ± 0%  -13.06%  (p=0.008 n=5+5)
CompileOnepass/^abcd$-4                     3.20kB ± 0%    2.75kB ± 0%  -14.00%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a{0,})*?)$-4          3.85kB ± 0%    3.34kB ± 0%  -13.31%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a+)*)$-4              3.46kB ± 0%    2.95kB ± 0%  -14.78%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a|(?:aa)))$-4         4.20kB ± 0%    3.75kB ± 0%  -10.67%  (p=0.008 n=5+5)
CompileOnepass/^(?:[^\s\S])$-4              3.10kB ± 0%    2.46kB ± 0%  -20.62%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:(?:a*)+))$-4          3.64kB ± 0%    3.13kB ± 0%  -14.07%  (p=0.008 n=5+5)
CompileOnepass/^[a-c]+$-4                   3.06kB ± 0%    2.48kB ± 0%  -18.85%  (p=0.008 n=5+5)
CompileOnepass/^[a-c]*$-4                   3.10kB ± 0%    2.52kB ± 0%  -18.60%  (p=0.008 n=5+5)
CompileOnepass/^(?:a*)$-4                   3.21kB ± 0%    2.63kB ± 0%  -17.96%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:aa)|a)$-4             4.09kB ± 0%    3.64kB ± 0%  -10.96%  (p=0.008 n=5+5)
CompileOnepass/^...$-4                      3.42kB ± 0%    2.91kB ± 0%  -14.95%  (p=0.008 n=5+5)
CompileOnepass/^(?:a|(?:aa))$-4             4.09kB ± 0%    3.64kB ± 0%  -10.96%  (p=0.008 n=5+5)
CompileOnepass/^a((b))c$-4                  5.67kB ± 0%    4.39kB ± 0%  -22.59%  (p=0.008 n=5+5)
CompileOnepass/^a.[l-nA-Cg-j]?e$-4          5.73kB ± 0%    4.32kB ± 0%  -24.58%  (p=0.008 n=5+5)
CompileOnepass/^a((b))$-4                   5.41kB ± 0%    4.06kB ± 0%  -24.85%  (p=0.008 n=5+5)
CompileOnepass/^a(?:(b)|(c))c$-4            6.40kB ± 0%    5.31kB ± 0%  -17.00%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b|c)$-4                 3.46kB ± 0%    2.88kB ± 0%  -16.67%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c)$-4                5.77kB ± 0%    4.36kB ± 0%  -24.41%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c+)$-4               5.94kB ± 0%    4.59kB ± 0%  -22.64%  (p=0.008 n=5+5)
CompileOnepass/^a(?:bc)+$-4                 3.60kB ± 0%    3.15kB ± 0%  -12.44%  (p=0.008 n=5+5)
CompileOnepass/^a(?:[bcd])+$-4              3.46kB ± 0%    2.94kB ± 0%  -14.81%  (p=0.008 n=5+5)
CompileOnepass/^a((?:[bcd])+)$-4            5.50kB ± 0%    4.09kB ± 0%  -25.62%  (p=0.008 n=5+5)
CompileOnepass/^a(:?b|c)*d$-4               7.24kB ± 0%    6.15kB ± 0%  -15.03%  (p=0.008 n=5+5)
CompileOnepass/^.bc(d|e)*$-4                5.75kB ± 0%    4.47kB ± 0%  -22.25%  (p=0.008 n=5+5)
CompileOnepass/^loooooooooooooooooo...-4     225kB ± 0%     135kB ± 0%  -39.99%  (p=0.008 n=5+5)

name                                      old allocs/op  new allocs/op  delta
CompileOnepass/^(?:(?:(?:.(?:$))?))...-4      52.0 ± 0%      49.0 ± 0%   -5.77%  (p=0.008 n=5+5)
CompileOnepass/^abcd$-4                       44.0 ± 0%      41.0 ± 0%   -6.82%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a{0,})*?)$-4            52.0 ± 0%      49.0 ± 0%   -5.77%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a+)*)$-4                47.0 ± 0%      44.0 ± 0%   -6.38%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a|(?:aa)))$-4           57.0 ± 0%      54.0 ± 0%   -5.26%  (p=0.008 n=5+5)
CompileOnepass/^(?:[^\s\S])$-4                36.0 ± 0%      33.0 ± 0%   -8.33%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:(?:a*)+))$-4            49.0 ± 0%      46.0 ± 0%   -6.12%  (p=0.008 n=5+5)
CompileOnepass/^[a-c]+$-4                     39.0 ± 0%      36.0 ± 0%   -7.69%  (p=0.008 n=5+5)
CompileOnepass/^[a-c]*$-4                     44.0 ± 0%      41.0 ± 0%   -6.82%  (p=0.008 n=5+5)
CompileOnepass/^(?:a*)$-4                     45.0 ± 0%      42.0 ± 0%   -6.67%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:aa)|a)$-4               56.0 ± 0%      53.0 ± 0%   -5.36%  (p=0.008 n=5+5)
CompileOnepass/^...$-4                        46.0 ± 0%      43.0 ± 0%   -6.52%  (p=0.008 n=5+5)
CompileOnepass/^(?:a|(?:aa))$-4               56.0 ± 0%      53.0 ± 0%   -5.36%  (p=0.008 n=5+5)
CompileOnepass/^a((b))c$-4                    57.0 ± 0%      53.0 ± 0%   -7.02%  (p=0.008 n=5+5)
CompileOnepass/^a.[l-nA-Cg-j]?e$-4            62.0 ± 0%      58.0 ± 0%   -6.45%  (p=0.008 n=5+5)
CompileOnepass/^a((b))$-4                     51.0 ± 0%      47.0 ± 0%   -7.84%  (p=0.008 n=5+5)
CompileOnepass/^a(?:(b)|(c))c$-4              69.0 ± 0%      65.0 ± 0%   -5.80%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b|c)$-4                   43.0 ± 0%      40.0 ± 0%   -6.98%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c)$-4                  61.0 ± 0%      57.0 ± 0%   -6.56%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c+)$-4                 67.0 ± 0%      63.0 ± 0%   -5.97%  (p=0.008 n=5+5)
CompileOnepass/^a(?:bc)+$-4                   49.0 ± 0%      46.0 ± 0%   -6.12%  (p=0.008 n=5+5)
CompileOnepass/^a(?:[bcd])+$-4                46.0 ± 0%      43.0 ± 0%   -6.52%  (p=0.008 n=5+5)
CompileOnepass/^a((?:[bcd])+)$-4              53.0 ± 0%      49.0 ± 0%   -7.55%  (p=0.008 n=5+5)
CompileOnepass/^a(:?b|c)*d$-4                  109 ± 0%       105 ± 0%   -3.67%  (p=0.008 n=5+5)
CompileOnepass/^.bc(d|e)*$-4                  66.0 ± 0%      62.0 ± 0%   -6.06%  (p=0.008 n=5+5)
CompileOnepass/^loooooooooooooooooo...-4     1.10k ± 0%     1.09k ± 0%   -0.91%  (p=0.008 n=5+5)

Fixes golang#19735

Change-Id: Ic68503aaa08e42fafcf7e11cf1f584d674f5ea7b
Reviewed-on: https://go-review.googlesource.com/38750
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
lparth added a commit to lparth/go that referenced this issue Apr 13, 2017
It reduces needless allocations on compiling onepass regex.

Following CL 38750

name                                      old time/op    new time/op    delta
CompileOnepass/^(?:(?:(?:.(?:$))?))...-4    5.75µs ± 1%    5.51µs ± 2%   -4.25%  (p=0.008 n=5+5)
CompileOnepass/^abcd$-4                     4.76µs ± 0%    4.52µs ± 1%   -5.06%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a{0,})*?)$-4          5.56µs ± 0%    5.56µs ± 3%     ~     (p=0.524 n=5+5)
CompileOnepass/^(?:(?:a+)*)$-4              5.09µs ± 0%    5.15µs ± 5%     ~     (p=0.690 n=5+5)
CompileOnepass/^(?:(?:a|(?:aa)))$-4         6.53µs ± 0%    6.43µs ± 5%     ~     (p=0.151 n=5+5)
CompileOnepass/^(?:[^\s\S])$-4              4.05µs ± 1%    4.00µs ± 2%     ~     (p=0.095 n=5+5)
CompileOnepass/^(?:(?:(?:a*)+))$-4          5.47µs ± 0%    5.36µs ± 1%   -1.91%  (p=0.008 n=5+5)
CompileOnepass/^[a-c]+$-4                   4.13µs ± 1%    4.05µs ± 0%   -2.07%  (p=0.008 n=5+5)
CompileOnepass/^[a-c]*$-4                   4.59µs ± 2%    4.93µs ± 7%   +7.30%  (p=0.016 n=5+5)
CompileOnepass/^(?:a*)$-4                   4.67µs ± 1%    4.82µs ± 8%     ~     (p=0.730 n=4+5)
CompileOnepass/^(?:(?:aa)|a)$-4             6.43µs ± 1%    6.18µs ± 1%   -3.91%  (p=0.008 n=5+5)
CompileOnepass/^...$-4                      4.71µs ± 0%    4.31µs ± 1%   -8.51%  (p=0.008 n=5+5)
CompileOnepass/^(?:a|(?:aa))$-4             6.37µs ± 0%    6.17µs ± 0%   -3.23%  (p=0.008 n=5+5)
CompileOnepass/^a((b))c$-4                  6.85µs ± 1%    6.50µs ± 1%   -5.15%  (p=0.008 n=5+5)
CompileOnepass/^a.[l-nA-Cg-j]?e$-4          6.99µs ± 1%    6.66µs ± 1%   -4.81%  (p=0.008 n=5+5)
CompileOnepass/^a((b))$-4                   6.15µs ± 1%    5.87µs ± 0%   -4.57%  (p=0.008 n=5+5)
CompileOnepass/^a(?:(b)|(c))c$-4            8.62µs ± 1%    8.21µs ± 1%   -4.77%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b|c)$-4                 5.76µs ±42%    4.42µs ± 1%  -23.35%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c)$-4                7.17µs ± 6%    6.86µs ± 0%   -4.39%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c+)$-4               8.08µs ± 2%    7.67µs ± 2%   -4.97%  (p=0.008 n=5+5)
CompileOnepass/^a(?:bc)+$-4                 5.53µs ± 3%    5.35µs ± 1%   -3.34%  (p=0.008 n=5+5)
CompileOnepass/^a(?:[bcd])+$-4              5.08µs ± 1%    4.98µs ± 0%   -2.02%  (p=0.008 n=5+5)
CompileOnepass/^a((?:[bcd])+)$-4            6.49µs ± 1%    6.29µs ± 1%   -3.03%  (p=0.008 n=5+5)
CompileOnepass/^a(:?b|c)*d$-4               11.8µs ± 1%    11.4µs ± 3%   -3.98%  (p=0.008 n=5+5)
CompileOnepass/^.bc(d|e)*$-4                8.02µs ± 1%    7.54µs ± 1%   -6.00%  (p=0.008 n=5+5)
CompileOnepass/^loooooooooooooooooo...-4     228µs ±18%     196µs ± 0%  -14.02%  (p=0.016 n=5+4)

name                                      old alloc/op   new alloc/op   delta
CompileOnepass/^(?:(?:(?:.(?:$))?))...-4    3.41kB ± 0%    3.38kB ± 0%   -0.94%  (p=0.008 n=5+5)
CompileOnepass/^abcd$-4                     2.75kB ± 0%    2.74kB ± 0%   -0.29%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a{0,})*?)$-4          3.34kB ± 0%    3.34kB ± 0%     ~     (all equal)
CompileOnepass/^(?:(?:a+)*)$-4              2.95kB ± 0%    2.95kB ± 0%     ~     (all equal)
CompileOnepass/^(?:(?:a|(?:aa)))$-4         3.75kB ± 0%    3.74kB ± 0%   -0.43%  (p=0.008 n=5+5)
CompileOnepass/^(?:[^\s\S])$-4              2.46kB ± 0%    2.45kB ± 0%   -0.49%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:(?:a*)+))$-4          3.13kB ± 0%    3.13kB ± 0%     ~     (all equal)
CompileOnepass/^[a-c]+$-4                   2.48kB ± 0%    2.48kB ± 0%     ~     (all equal)
CompileOnepass/^[a-c]*$-4                   2.52kB ± 0%    2.52kB ± 0%     ~     (all equal)
CompileOnepass/^(?:a*)$-4                   2.63kB ± 0%    2.63kB ± 0%     ~     (all equal)
CompileOnepass/^(?:(?:aa)|a)$-4             3.64kB ± 0%    3.62kB ± 0%   -0.44%  (p=0.008 n=5+5)
CompileOnepass/^...$-4                      2.91kB ± 0%    2.87kB ± 0%   -1.37%  (p=0.008 n=5+5)
CompileOnepass/^(?:a|(?:aa))$-4             3.64kB ± 0%    3.62kB ± 0%   -0.44%  (p=0.008 n=5+5)
CompileOnepass/^a((b))c$-4                  4.39kB ± 0%    4.38kB ± 0%   -0.18%  (p=0.008 n=5+5)
CompileOnepass/^a.[l-nA-Cg-j]?e$-4          4.32kB ± 0%    4.30kB ± 0%   -0.56%  (p=0.008 n=5+5)
CompileOnepass/^a((b))$-4                   4.06kB ± 0%    4.05kB ± 0%   -0.39%  (p=0.008 n=5+5)
CompileOnepass/^a(?:(b)|(c))c$-4            5.31kB ± 0%    5.30kB ± 0%   -0.15%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b|c)$-4                 2.88kB ± 0%    2.87kB ± 0%   -0.28%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c)$-4                4.36kB ± 0%    4.35kB ± 0%   -0.18%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c+)$-4               4.59kB ± 0%    4.58kB ± 0%   -0.17%  (p=0.008 n=5+5)
CompileOnepass/^a(?:bc)+$-4                 3.15kB ± 0%    3.15kB ± 0%     ~     (all equal)
CompileOnepass/^a(?:[bcd])+$-4              2.94kB ± 0%    2.94kB ± 0%     ~     (all equal)
CompileOnepass/^a((?:[bcd])+)$-4            4.09kB ± 0%    4.08kB ± 0%   -0.20%  (p=0.008 n=5+5)
CompileOnepass/^a(:?b|c)*d$-4               6.15kB ± 0%    6.10kB ± 0%   -0.78%  (p=0.008 n=5+5)
CompileOnepass/^.bc(d|e)*$-4                4.47kB ± 0%    4.46kB ± 0%   -0.36%  (p=0.008 n=5+5)
CompileOnepass/^loooooooooooooooooo...-4     135kB ± 0%     135kB ± 0%     ~     (p=0.810 n=5+5)

name                                      old allocs/op  new allocs/op  delta
CompileOnepass/^(?:(?:(?:.(?:$))?))...-4      49.0 ± 0%      47.0 ± 0%   -4.08%  (p=0.008 n=5+5)
CompileOnepass/^abcd$-4                       41.0 ± 0%      41.0 ± 0%     ~     (all equal)
CompileOnepass/^(?:(?:a{0,})*?)$-4            49.0 ± 0%      49.0 ± 0%     ~     (all equal)
CompileOnepass/^(?:(?:a+)*)$-4                44.0 ± 0%      44.0 ± 0%     ~     (all equal)
CompileOnepass/^(?:(?:a|(?:aa)))$-4           54.0 ± 0%      54.0 ± 0%     ~     (all equal)
CompileOnepass/^(?:[^\s\S])$-4                33.0 ± 0%      33.0 ± 0%     ~     (all equal)
CompileOnepass/^(?:(?:(?:a*)+))$-4            46.0 ± 0%      46.0 ± 0%     ~     (all equal)
CompileOnepass/^[a-c]+$-4                     36.0 ± 0%      36.0 ± 0%     ~     (all equal)
CompileOnepass/^[a-c]*$-4                     41.0 ± 0%      41.0 ± 0%     ~     (all equal)
CompileOnepass/^(?:a*)$-4                     42.0 ± 0%      42.0 ± 0%     ~     (all equal)
CompileOnepass/^(?:(?:aa)|a)$-4               53.0 ± 0%      53.0 ± 0%     ~     (all equal)
CompileOnepass/^...$-4                        43.0 ± 0%      39.0 ± 0%   -9.30%  (p=0.008 n=5+5)
CompileOnepass/^(?:a|(?:aa))$-4               53.0 ± 0%      53.0 ± 0%     ~     (all equal)
CompileOnepass/^a((b))c$-4                    53.0 ± 0%      53.0 ± 0%     ~     (all equal)
CompileOnepass/^a.[l-nA-Cg-j]?e$-4            58.0 ± 0%      56.0 ± 0%   -3.45%  (p=0.008 n=5+5)
CompileOnepass/^a((b))$-4                     47.0 ± 0%      47.0 ± 0%     ~     (all equal)
CompileOnepass/^a(?:(b)|(c))c$-4              65.0 ± 0%      65.0 ± 0%     ~     (all equal)
CompileOnepass/^a(?:b|c)$-4                   40.0 ± 0%      40.0 ± 0%     ~     (all equal)
CompileOnepass/^a(?:b?|c)$-4                  57.0 ± 0%      57.0 ± 0%     ~     (all equal)
CompileOnepass/^a(?:b?|c+)$-4                 63.0 ± 0%      63.0 ± 0%     ~     (all equal)
CompileOnepass/^a(?:bc)+$-4                   46.0 ± 0%      46.0 ± 0%     ~     (all equal)
CompileOnepass/^a(?:[bcd])+$-4                43.0 ± 0%      43.0 ± 0%     ~     (all equal)
CompileOnepass/^a((?:[bcd])+)$-4              49.0 ± 0%      49.0 ± 0%     ~     (all equal)
CompileOnepass/^a(:?b|c)*d$-4                  105 ± 0%       101 ± 0%   -3.81%  (p=0.008 n=5+5)
CompileOnepass/^.bc(d|e)*$-4                  62.0 ± 0%      60.0 ± 0%   -3.23%  (p=0.008 n=5+5)
CompileOnepass/^loooooooooooooooooo...-4     1.09k ± 0%     1.09k ± 0%     ~     (all equal)

Fixes golang#19735

Change-Id: Ib90e18e1b06166407b26b2a68b88afbb1f486024
Reviewed-on: https://go-review.googlesource.com/38751
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
Run-TryBot: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
@golang golang locked and limited conversation to collaborators Mar 28, 2018
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
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.