delta/go-git.git/src/regexp, branch dev.debug

regexp: example for MatchString function

2017-07-15T21:13:35+00:00

Change-Id: I5ca5a6689f0679154c24820466f5cf0011d0aaa6
Reviewed-on: https://go-review.googlesource.com/48959
Reviewed-by: Brad Fitzpatrick 
Run-TryBot: Brad Fitzpatrick 
TryBot-Result: Gobot Gobot

regexp: clarify example for 'FindString'

2017-07-15T20:38:58+00:00

Clarifying that FindString only provides left-most match

Change-Id: Ic6ecec12cca759fd4b3565ef5901a110843ffd56
Reviewed-on: https://go-review.googlesource.com/48609
Reviewed-by: Ian Lance Taylor 
Run-TryBot: Ian Lance Taylor 
TryBot-Result: Gobot Gobot

regexp: speed up QuoteMeta with a lookup table

2017-04-28T06:43:14+00:00

This is the same technique used in CL 24466. By adding a little bit of
size to the binary, we can remove a function call and gain a lot of
performance.

A raw array ([128]bool) would be faster, but is also be 128 bytes
instead of 16.

Running tip on a Mac:

name             old time/op    new time/op     delta
QuoteMetaAll-4      192ns ±12%      120ns ±11%   -37.27%  (p=0.000 n=10+10)
QuoteMetaNone-4     186ns ± 6%       64ns ± 6%   -65.52%  (p=0.000 n=10+10)

name             old speed      new speed       delta
QuoteMetaAll-4   73.2MB/s ±11%  116.6MB/s ±10%   +59.21%  (p=0.000 n=10+10)
QuoteMetaNone-4   139MB/s ± 6%    405MB/s ± 6%  +190.74%  (p=0.000 n=10+10)

Change-Id: I68ce9fe2ef1c28e2274157789b35b0dd6ae3efb5
Reviewed-on: https://go-review.googlesource.com/41495
Run-TryBot: Kevin Burke 
TryBot-Result: Gobot Gobot 
Reviewed-by: Brad Fitzpatrick

regexp: remove redundant break

2017-04-25T15:00:06+00:00

Breaks are implicit, and since there is no outer loop this one could not
mean a loop break that was missing a label.

Change-Id: Ie91018db1825aa8285c1aa55c9d28fc7ec7148af
Reviewed-on: https://go-review.googlesource.com/39691
Run-TryBot: Daniel Martí 
TryBot-Result: Gobot Gobot 
Reviewed-by: Brad Fitzpatrick

regexp: Use []bool instead of map[uint32]bool in makeOnePass

2017-04-16T15:24:48+00:00

Variable m is accessed like variable onePassRunes.
So, we can use array instead of map for variable m.

Onepass compile performance is improved 10~20%.

name                                      old time/op    new time/op    delta
CompileOnepass/^(?:(?:(?:.(?:$))?))...-4    4.60µs ± 1%    4.10µs ± 1%  -10.98%  (p=0.008 n=5+5)
CompileOnepass/^abcd$-4                     3.76µs ± 2%    3.33µs ± 1%  -11.43%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a{0,})*?)$-4          4.47µs ± 1%    4.14µs ± 1%   -7.49%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a+)*)$-4              4.07µs ± 1%    3.81µs ± 2%   -6.60%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a|(?:aa)))$-4         5.21µs ± 1%    4.80µs ± 2%   -7.90%  (p=0.008 n=5+5)
CompileOnepass/^(?:[^\s\S])$-4              3.26µs ± 1%    3.06µs ± 1%   -6.15%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:(?:a*)+))$-4          4.33µs ± 0%    4.04µs ± 3%   -6.78%  (p=0.008 n=5+5)
CompileOnepass/^[a-c]+$-4                   3.33µs ± 1%    3.06µs ± 4%   -8.24%  (p=0.008 n=5+5)
CompileOnepass/^[a-c]*$-4                   3.69µs ± 1%    3.39µs ± 4%   -8.26%  (p=0.008 n=5+5)
CompileOnepass/^(?:a*)$-4                   3.78µs ± 2%    3.36µs ± 0%  -11.09%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:aa)|a)$-4             5.11µs ± 1%    4.60µs ± 1%   -9.85%  (p=0.008 n=5+5)
CompileOnepass/^...$-4                      3.51µs ± 1%    3.25µs ± 1%   -7.37%  (p=0.008 n=5+5)
CompileOnepass/^(?:a|(?:aa))$-4             5.05µs ± 1%    4.59µs ± 1%   -9.13%  (p=0.008 n=5+5)
CompileOnepass/^a((b))c$-4                  5.24µs ± 1%    4.66µs ± 1%  -11.16%  (p=0.008 n=5+5)
CompileOnepass/^a.[l-nA-Cg-j]?e$-4          5.94µs ± 7%    5.02µs ± 1%  -15.62%  (p=0.008 n=5+5)
CompileOnepass/^a((b))$-4                   5.34µs ± 7%    4.21µs ± 2%  -21.05%  (p=0.008 n=5+5)
CompileOnepass/^a(?:(b)|(c))c$-4            7.25µs ± 7%    5.86µs ± 1%  -19.17%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b|c)$-4                 4.13µs ± 9%    3.35µs ± 1%  -18.99%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c)$-4                6.48µs ± 4%    5.05µs ± 1%  -22.16%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c+)$-4               7.05µs ± 7%    5.48µs ± 1%  -22.21%  (p=0.008 n=5+5)
CompileOnepass/^a(?:bc)+$-4                 4.71µs ± 4%    3.85µs ± 0%  -18.14%  (p=0.008 n=5+5)
CompileOnepass/^a(?:[bcd])+$-4              4.10µs ± 2%    3.69µs ± 1%   -9.98%  (p=0.008 n=5+5)
CompileOnepass/^a((?:[bcd])+)$-4            5.20µs ± 1%    4.59µs ± 0%  -11.72%  (p=0.008 n=5+5)
CompileOnepass/^a(:?b|c)*d$-4               9.29µs ± 2%    8.23µs ± 1%  -11.43%  (p=0.008 n=5+5)
CompileOnepass/^.bc(d|e)*$-4                6.33µs ± 3%    5.51µs ± 5%  -12.95%  (p=0.008 n=5+5)
CompileOnepass/^loooooooooooooooooo...-4     162µs ± 0%     138µs ± 2%  -14.70%  (p=0.008 n=5+5)

name                                      old alloc/op   new alloc/op   delta
CompileOnepass/^(?:(?:(?:.(?:$))?))...-4    3.38kB ± 0%    3.27kB ± 0%   -3.08%  (p=0.008 n=5+5)
CompileOnepass/^abcd$-4                     2.74kB ± 0%    2.59kB ± 0%   -5.54%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a{0,})*?)$-4          3.34kB ± 0%    3.23kB ± 0%   -3.12%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a+)*)$-4              2.95kB ± 0%    2.85kB ± 0%   -3.52%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a|(?:aa)))$-4         3.74kB ± 0%    3.58kB ± 0%   -4.07%  (p=0.008 n=5+5)
CompileOnepass/^(?:[^\s\S])$-4              2.45kB ± 0%    2.35kB ± 0%   -4.20%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:(?:a*)+))$-4          3.13kB ± 0%    3.02kB ± 0%   -3.32%  (p=0.008 n=5+5)
CompileOnepass/^[a-c]+$-4                   2.48kB ± 0%    2.38kB ± 0%   -4.19%  (p=0.008 n=5+5)
CompileOnepass/^[a-c]*$-4                   2.52kB ± 0%    2.42kB ± 0%   -4.13%  (p=0.008 n=5+5)
CompileOnepass/^(?:a*)$-4                   2.63kB ± 0%    2.53kB ± 0%   -3.95%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:aa)|a)$-4             3.62kB ± 0%    3.47kB ± 0%   -4.19%  (p=0.008 n=5+5)
CompileOnepass/^...$-4                      2.87kB ± 0%    2.78kB ± 0%   -3.34%  (p=0.008 n=5+5)
CompileOnepass/^(?:a|(?:aa))$-4             3.62kB ± 0%    3.47kB ± 0%   -4.19%  (p=0.008 n=5+5)
CompileOnepass/^a((b))c$-4                  4.38kB ± 0%    4.23kB ± 0%   -3.33%  (p=0.008 n=5+5)
CompileOnepass/^a.[l-nA-Cg-j]?e$-4          4.30kB ± 0%    4.15kB ± 0%   -3.35%  (p=0.008 n=5+5)
CompileOnepass/^a((b))$-4                   4.05kB ± 0%    3.90kB ± 0%   -3.56%  (p=0.008 n=5+5)
CompileOnepass/^a(?:(b)|(c))c$-4            5.30kB ± 0%    5.05kB ± 0%   -4.83%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b|c)$-4                 2.87kB ± 0%    2.77kB ± 0%   -3.62%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c)$-4                4.35kB ± 0%    4.21kB ± 0%   -3.31%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c+)$-4               4.58kB ± 0%    4.44kB ± 0%   -3.14%  (p=0.008 n=5+5)
CompileOnepass/^a(?:bc)+$-4                 3.15kB ± 0%    3.00kB ± 0%   -4.82%  (p=0.008 n=5+5)
CompileOnepass/^a(?:[bcd])+$-4              2.94kB ± 0%    2.84kB ± 0%   -3.53%  (p=0.008 n=5+5)
CompileOnepass/^a((?:[bcd])+)$-4            4.08kB ± 0%    3.94kB ± 0%   -3.53%  (p=0.008 n=5+5)
CompileOnepass/^a(:?b|c)*d$-4               6.10kB ± 0%    5.85kB ± 0%   -4.19%  (p=0.008 n=5+5)
CompileOnepass/^.bc(d|e)*$-4                4.46kB ± 0%    4.31kB ± 0%   -3.28%  (p=0.008 n=5+5)
CompileOnepass/^loooooooooooooooooo...-4     135kB ± 0%     127kB ± 0%   -5.88%  (p=0.008 n=5+5)

name                                      old allocs/op  new allocs/op  delta
CompileOnepass/^(?:(?:(?:.(?:$))?))...-4      47.0 ± 0%      46.0 ± 0%   -2.13%  (p=0.008 n=5+5)
CompileOnepass/^abcd$-4                       41.0 ± 0%      40.0 ± 0%   -2.44%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a{0,})*?)$-4            49.0 ± 0%      48.0 ± 0%   -2.04%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a+)*)$-4                44.0 ± 0%      43.0 ± 0%   -2.27%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:a|(?:aa)))$-4           54.0 ± 0%      53.0 ± 0%   -1.85%  (p=0.008 n=5+5)
CompileOnepass/^(?:[^\s\S])$-4                33.0 ± 0%      32.0 ± 0%   -3.03%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:(?:a*)+))$-4            46.0 ± 0%      45.0 ± 0%   -2.17%  (p=0.008 n=5+5)
CompileOnepass/^[a-c]+$-4                     36.0 ± 0%      35.0 ± 0%   -2.78%  (p=0.008 n=5+5)
CompileOnepass/^[a-c]*$-4                     41.0 ± 0%      40.0 ± 0%   -2.44%  (p=0.008 n=5+5)
CompileOnepass/^(?:a*)$-4                     42.0 ± 0%      41.0 ± 0%   -2.38%  (p=0.008 n=5+5)
CompileOnepass/^(?:(?:aa)|a)$-4               53.0 ± 0%      52.0 ± 0%   -1.89%  (p=0.008 n=5+5)
CompileOnepass/^...$-4                        39.0 ± 0%      38.0 ± 0%   -2.56%  (p=0.008 n=5+5)
CompileOnepass/^(?:a|(?:aa))$-4               53.0 ± 0%      52.0 ± 0%   -1.89%  (p=0.008 n=5+5)
CompileOnepass/^a((b))c$-4                    53.0 ± 0%      52.0 ± 0%   -1.89%  (p=0.008 n=5+5)
CompileOnepass/^a.[l-nA-Cg-j]?e$-4            56.0 ± 0%      55.0 ± 0%   -1.79%  (p=0.008 n=5+5)
CompileOnepass/^a((b))$-4                     47.0 ± 0%      46.0 ± 0%   -2.13%  (p=0.008 n=5+5)
CompileOnepass/^a(?:(b)|(c))c$-4              65.0 ± 0%      64.0 ± 0%   -1.54%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b|c)$-4                   40.0 ± 0%      39.0 ± 0%   -2.50%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c)$-4                  57.0 ± 0%      56.0 ± 0%   -1.75%  (p=0.008 n=5+5)
CompileOnepass/^a(?:b?|c+)$-4                 63.0 ± 0%      62.0 ± 0%   -1.59%  (p=0.008 n=5+5)
CompileOnepass/^a(?:bc)+$-4                   46.0 ± 0%      45.0 ± 0%   -2.17%  (p=0.008 n=5+5)
CompileOnepass/^a(?:[bcd])+$-4                43.0 ± 0%      42.0 ± 0%   -2.33%  (p=0.008 n=5+5)
CompileOnepass/^a((?:[bcd])+)$-4              49.0 ± 0%      48.0 ± 0%   -2.04%  (p=0.008 n=5+5)
CompileOnepass/^a(:?b|c)*d$-4                  101 ± 0%       100 ± 0%   -0.99%  (p=0.008 n=5+5)
CompileOnepass/^.bc(d|e)*$-4                  60.0 ± 0%      59.0 ± 0%   -1.67%  (p=0.008 n=5+5)
CompileOnepass/^loooooooooooooooooo...-4     1.09k ± 0%     1.08k ± 0%   -0.74%  (p=0.008 n=5+5)

Fixes #19984

Change-Id: I2268b28d068926a057c62751528de15b6de61a7b
Reviewed-on: https://go-review.googlesource.com/40890
Reviewed-by: Ralph Corderoy 
Reviewed-by: Brad Fitzpatrick 
Run-TryBot: Brad Fitzpatrick 
TryBot-Result: Gobot Gobot

regexp: document that Longest method is not concurrent-safe

2017-04-07T21:12:11+00:00

Change-Id: I9ec137502353e65325087dfb60ee9bd68ffd286d
Reviewed-on: https://go-review.googlesource.com/38447
Reviewed-by: Russ Cox

regexp: reduce allocations at makeOnePass

2017-03-29T20:35:08+00:00

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 
Run-TryBot: Brad Fitzpatrick 
TryBot-Result: Gobot Gobot

regexp: reduce allocations at onePassCopy

2017-03-28T17:58:10+00:00

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 #19735

Change-Id: Ic68503aaa08e42fafcf7e11cf1f584d674f5ea7b
Reviewed-on: https://go-review.googlesource.com/38750
Reviewed-by: Brad Fitzpatrick 
Run-TryBot: Brad Fitzpatrick 
TryBot-Result: Gobot Gobot

regexp: add ASCII fast path for context methods

2017-03-23T00:08:20+00:00

The step method implementations check directly if the next rune
only needs one byte to be decoded and avoid calling utf8.DecodeRune
for such ASCII characters.

Introduce the same fast path optimization for rune decoding
for the context methods.

Results for regexp benchmarks that use the context methods:

name                            old time/op  new time/op  delta
AnchoredLiteralShortNonMatch-4  97.5ns ± 1%  94.8ns ± 2%  -2.80%  (p=0.000 n=45+43)
AnchoredShortMatch-4             163ns ± 1%   160ns ± 1%  -1.84%  (p=0.000 n=46+47)
NotOnePassShortA-4               742ns ± 2%   742ns ± 2%    ~     (p=0.440 n=49+50)
NotOnePassShortB-4               535ns ± 1%   533ns ± 2%  -0.37%  (p=0.005 n=46+48)
OnePassLongPrefix-4              169ns ± 2%   166ns ± 2%  -2.06%  (p=0.000 n=50+49)

Change-Id: Ib302d9e8c63333f02695369fcf9963974362e335
Reviewed-on: https://go-review.googlesource.com/38256
Reviewed-by: Brad Fitzpatrick 
Run-TryBot: Brad Fitzpatrick 
TryBot-Result: Gobot Gobot

regexp: reduce allocs in regexp.Match for onepass regex

2017-03-23T00:02:55+00:00

There were no allocations in regexp.Match for *non* onepass regex
because m.matchcap length is reset to zero (ncap=0 for regexp.Match).

But, as for onepass regex, m.matchcap length remains as it is even when
ncap=0 and it leads needless allocations.

benchmark                                    old ns/op      new ns/op      delta
BenchmarkMatch_onepass_regex/32-4      6465           4628           -28.41%
BenchmarkMatch_onepass_regex/1K-4      208324         151558         -27.25%
BenchmarkMatch_onepass_regex/32K-4     7230259        5834492        -19.30%
BenchmarkMatch_onepass_regex/1M-4      234379810      166310682      -29.04%
BenchmarkMatch_onepass_regex/32M-4     7903529363     4981119950     -36.98%

benchmark                                    old MB/s     new MB/s     speedup
BenchmarkMatch_onepass_regex/32-4      4.95         6.91         1.40x
BenchmarkMatch_onepass_regex/1K-4      4.92         6.76         1.37x
BenchmarkMatch_onepass_regex/32K-4     4.53         5.62         1.24x
BenchmarkMatch_onepass_regex/1M-4      4.47         6.30         1.41x
BenchmarkMatch_onepass_regex/32M-4     4.25         6.74         1.59x

benchmark                                    old allocs     new allocs     delta
BenchmarkMatch_onepass_regex/32-4      32             0              -100.00%
BenchmarkMatch_onepass_regex/1K-4      1024           0              -100.00%
BenchmarkMatch_onepass_regex/32K-4     32768          0              -100.00%
BenchmarkMatch_onepass_regex/1M-4      1048576        0              -100.00%
BenchmarkMatch_onepass_regex/32M-4     104559255      0              -100.00%

benchmark                                    old bytes      new bytes     delta
BenchmarkMatch_onepass_regex/32-4      512            0             -100.00%
BenchmarkMatch_onepass_regex/1K-4      16384          0             -100.00%
BenchmarkMatch_onepass_regex/32K-4     524288         0             -100.00%
BenchmarkMatch_onepass_regex/1M-4      16777216       0             -100.00%
BenchmarkMatch_onepass_regex/32M-4     2019458128     0             -100.00%

Fixes #19573

Change-Id: I033982d0003ebb0360bb40b92eb3941c781ec74d
Reviewed-on: https://go-review.googlesource.com/38270
Run-TryBot: Michael Matloob 
TryBot-Result: Gobot Gobot 
Reviewed-by: Brad Fitzpatrick