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

internal/gogrep: make simple call patterns match faster #277

Merged
merged 1 commit into from Oct 13, 2021

Conversation

quasilyte
Copy link
Owner

When func call pattern contains no $* inside arguments list,
we can compile it to a more efficient program than a
generic one we're currently using.

For instance, in f($x, $y) pattern the desired number
of arguments is known, it's 2, so we can encode that
into pattern directly and check for the args slice length
instead of doing a variadic matching until we reach opEnd.

The performance gains for gogrep are significant (only relevant benchmarks):

name                           old time/op    new time/op    delta
Match/failCall-8                  653ns ±21%     425ns ± 0%  -34.88%  (p=0.008 n=5+5)
Match/simpleCall-8                674ns ±21%     359ns ± 0%  -46.74%  (p=0.008 n=5+5)
Match/anyCall-8                   827ns ±10%     794ns ± 2%     ~     (p=0.690 n=5+5)
Match/variadicCall-8              491ns ± 4%     289ns ± 0%  -41.13%  (p=0.016 n=5+4)
Match/capture1-8                  220ns ± 3%     212ns ± 1%   -3.62%  (p=0.008 n=5+5)
Match/capture2-8                  328ns ± 2%     312ns ± 0%   -4.97%  (p=0.008 n=5+5)
Match/capture8-8                 1.52µs ± 2%    1.14µs ± 1%  -25.01%  (p=0.008 n=5+5)
Match/capture2same-8              372ns ± 3%     350ns ± 1%   -6.01%  (p=0.008 n=5+5)
Match/capture8same-8             1.70µs ±10%    1.22µs ± 1%  -28.20%  (p=0.008 n=5+5)
Match/captureBacktrackLeft-8     2.23µs ±10%    2.01µs ± 0%   -9.79%  (p=0.008 n=5+5)
Match/captureBacktrackRight-8    1.18µs ± 0%    1.14µs ± 0%   -3.27%  (p=0.008 n=5+5)

name                           old alloc/op   new alloc/op   delta
Match/failCall-8                  48.0B ± 0%     24.0B ± 0%  -50.00%  (p=0.008 n=5+5)
Match/simpleCall-8                72.0B ± 0%     24.0B ± 0%  -66.67%  (p=0.008 n=5+5)
Match/anyCall-8                    136B ± 0%      136B ± 0%     ~     (all equal)
Match/variadicCall-8              72.0B ± 0%     24.0B ± 0%  -66.67%  (p=0.008 n=5+5)
Match/capture1-8                  24.0B ± 0%     24.0B ± 0%     ~     (all equal)
Match/capture2-8                  24.0B ± 0%     24.0B ± 0%     ~     (all equal)
Match/capture8-8                  72.0B ± 0%     24.0B ± 0%  -66.67%  (p=0.008 n=5+5)
Match/capture2same-8              24.0B ± 0%     24.0B ± 0%     ~     (all equal)
Match/capture8same-8              72.0B ± 0%     24.0B ± 0%  -66.67%  (p=0.008 n=5+5)
Match/captureBacktrackLeft-8       280B ± 0%      280B ± 0%     ~     (all equal)
Match/captureBacktrackRight-8      160B ± 0%      160B ± 0%     ~     (all equal)

Copy link
Collaborator

@cristaloleg cristaloleg left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

🚀

@@ -529,6 +529,22 @@ func (m *matcher) matchNode(n ast.Node) bool {
return m.matchNodeWithInst(m.nextInst(), n)
}

func (m *matcher) matchArgList(exprs []ast.Expr) bool {
inst := m.nextInst()
if inst.op == opSimpleArgList {
Copy link
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

looks like inverted version is slightly simpler

Copy link
Owner Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Fixed.

@quasilyte quasilyte force-pushed the quasilyte/optimize_gogrep_call_matching branch from a4bab66 to d05b9ad Compare October 13, 2021 10:48
When func call pattern contains no `$*` inside arguments list,
we can compile it to a more efficient program than a
generic one we're currently using.

For instance, in `f($x, $y)` pattern the desired number
of arguments is known, it's 2, so we can encode that
into pattern directly and check for the args slice length
instead of doing a variadic matching until we reach `opEnd`.

The performance gains for gogrep are significant (only relevant benchmarks):

	name                           old time/op    new time/op    delta
	Match/failCall-8                  653ns ±21%     425ns ± 0%  -34.88%  (p=0.008 n=5+5)
	Match/simpleCall-8                674ns ±21%     359ns ± 0%  -46.74%  (p=0.008 n=5+5)
	Match/anyCall-8                   827ns ±10%     794ns ± 2%     ~     (p=0.690 n=5+5)
	Match/variadicCall-8              491ns ± 4%     289ns ± 0%  -41.13%  (p=0.016 n=5+4)
	Match/capture1-8                  220ns ± 3%     212ns ± 1%   -3.62%  (p=0.008 n=5+5)
	Match/capture2-8                  328ns ± 2%     312ns ± 0%   -4.97%  (p=0.008 n=5+5)
	Match/capture8-8                 1.52µs ± 2%    1.14µs ± 1%  -25.01%  (p=0.008 n=5+5)
	Match/capture2same-8              372ns ± 3%     350ns ± 1%   -6.01%  (p=0.008 n=5+5)
	Match/capture8same-8             1.70µs ±10%    1.22µs ± 1%  -28.20%  (p=0.008 n=5+5)
	Match/captureBacktrackLeft-8     2.23µs ±10%    2.01µs ± 0%   -9.79%  (p=0.008 n=5+5)
	Match/captureBacktrackRight-8    1.18µs ± 0%    1.14µs ± 0%   -3.27%  (p=0.008 n=5+5)

	name                           old alloc/op   new alloc/op   delta
	Match/failCall-8                  48.0B ± 0%     24.0B ± 0%  -50.00%  (p=0.008 n=5+5)
	Match/simpleCall-8                72.0B ± 0%     24.0B ± 0%  -66.67%  (p=0.008 n=5+5)
	Match/anyCall-8                    136B ± 0%      136B ± 0%     ~     (all equal)
	Match/variadicCall-8              72.0B ± 0%     24.0B ± 0%  -66.67%  (p=0.008 n=5+5)
	Match/capture1-8                  24.0B ± 0%     24.0B ± 0%     ~     (all equal)
	Match/capture2-8                  24.0B ± 0%     24.0B ± 0%     ~     (all equal)
	Match/capture8-8                  72.0B ± 0%     24.0B ± 0%  -66.67%  (p=0.008 n=5+5)
	Match/capture2same-8              24.0B ± 0%     24.0B ± 0%     ~     (all equal)
	Match/capture8same-8              72.0B ± 0%     24.0B ± 0%  -66.67%  (p=0.008 n=5+5)
	Match/captureBacktrackLeft-8       280B ± 0%      280B ± 0%     ~     (all equal)
	Match/captureBacktrackRight-8      160B ± 0%      160B ± 0%     ~     (all equal)
@quasilyte quasilyte force-pushed the quasilyte/optimize_gogrep_call_matching branch from d05b9ad to face0fe Compare October 13, 2021 10:49
@quasilyte quasilyte merged commit dcc5e92 into master Oct 13, 2021
@quasilyte quasilyte deleted the quasilyte/optimize_gogrep_call_matching branch October 13, 2021 10:57
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

2 participants