Skip to content

Ruby: Eliminate unnecessary recursion through RealNode#7141

Merged
hvitved merged 2 commits into
github:mainfrom
hvitved:ruby/synthesis-realnode-recursion
Nov 17, 2021
Merged

Ruby: Eliminate unnecessary recursion through RealNode#7141
hvitved merged 2 commits into
github:mainfrom
hvitved:ruby/synthesis-realnode-recursion

Conversation

@hvitved
Copy link
Copy Markdown
Contributor

@hvitved hvitved commented Nov 15, 2021 •
edited
Loading

When investigating the (minor) performance regression introduced by #7098, I realized that we have unnecessary recursion through the newtype constructor RealNode in the synthesis framework. This PR splits up RealNode into RealNodeRef and SynthNodeRef, where the former is restricted to real nodes (no recursion), and the latter to synthesized nodes (recursion). This makes a big difference because the recursion in Synthesis::child/3 is non-linear.

The changes in this PR will conflict with #7098, so I suggest we rebase that PR once this PR is merged, and then rerun performance checks.

@github-actions github-actions Bot added the Ruby label Nov 15, 2021
@hvitved hvitved force-pushed the ruby/synthesis-realnode-recursion branch from ad9035c to ed883a8 Compare November 16, 2021 11:16
@hvitved hvitved force-pushed the ruby/synthesis-realnode-recursion branch from ed883a8 to e7b0910 Compare November 16, 2021 11:24
@hvitved hvitved mentioned this pull request Nov 16, 2021
Merged
@hvitved hvitved marked this pull request as ready for review November 16, 2021 15:03
@hvitved hvitved requested a review from a team as a code owner November 16, 2021 15:03
@hvitved
Copy link
Copy Markdown
Contributor Author

hvitved commented Nov 16, 2021

Here are some performance numbers:

Before:

[2021-11-16 16:13:20] (204s) Timings for last stage:
[2021-11-16 16:13:20] (204s) 	- Extensionals: 0ms
[2021-11-16 16:13:20] (204s) 	- Intensionals: 3min24.752s ... of which ...
[2021-11-16 16:13:20] (204s) 		- Nonrecursive intensionals: 1min32.37s
[2021-11-16 16:13:20] (204s) 		- Recursive intensionals: 1min52.381s
[2021-11-16 16:13:20] (204s) 	- Building results: 0ms
[2021-11-16 16:13:20] CSV_QUERY_PROFILES: ReDoS.ql-5,0,204752,92370,112381,0
[2021-11-16 16:13:20] (204s) Clause timing report:
[2021-11-16 16:13:20] (204s) 
[2021-11-16 16:13:20] 
	ReDoS.ql-5:Call::MethodCallImpl::getReceiverImpl_dispred#ff#reorder_1_0 ..................................................................................................................................................................................................................................................................................................................................... 14.3s (41 evaluations with max 900ms in Call::MethodCallImpl::getReceiverImpl_dispred#ff#reorder_1_0/2@i3#17f93f)
	ReDoS.ql-5:Call::CallImpl::getArgumentImpl_dispred#fff#reorder_2_0_1 ........................................................................................................................................................................................................................................................................................................................................ 13.7s (41 evaluations with max 1.8s in Call::CallImpl::getArgumentImpl_dispred#fff#reorder_2_0_1/3@i3#17f934)
	ReDoS.ql-5:Operation::AssignmentImpl::getRightOperandImpl_dispred#ff ........................................................................................................................................................................................................................................................................................................................................ 12s (39 evaluations with max 2.5s in Operation::AssignmentImpl::getRightOperandImpl_dispred#ff/2@i3#17f93d)
	ReDoS.ql-5:Operation::UnaryOperationImpl::getOperandImpl_dispred#ff ......................................................................................................................................................................................................................................................................................................................................... 11.4s (36 evaluations with max 2.2s in Operation::UnaryOperationImpl::getOperandImpl_dispred#ff/2@i3#17f93e)
	ReDoS.ql-5:AST::AstNode_not_AliasStmt_ArgumentList_ArrayLiteral_Block_BlockArgument_Call_Callable_CaseExpr_ConditionalExpr_ConstantAccess_HashLiteral_Loop_MethodBase_NamedParameter_Namespace_Operation_Pair_RangeLiteral_RescueClause_RescueModifierExpr_ReturningStmt_SingletonClass_StmtSequence_StringConcatenation_StringlikeLiteral_Toplevel_TuplePattern_TuplePatternParameter_UndefStmt_WhenExpr#f . 6.7s
	ReDoS.ql-5:Operation::BinaryOperationImpl::getLeftOperandImpl_dispred#ff .................................................................................................................................................................................................................................................................................................................................... 6.2s (39 evaluations with max 1.6s in Operation::BinaryOperationImpl::getLeftOperandImpl_dispred#ff/2@i7#17f93b)
	ReDoS.ql-5:Operation::BinaryOperationImpl::getRightOperandImpl_dispred#ff#reorder_1_0 ....................................................................................................................................................................................................................................................................................................................... 6.1s (38 evaluations with max 1.6s in Operation::BinaryOperationImpl::getRightOperandImpl_dispred#ff#reorder_1_0/2@i7#17f93a)
	ReDoS.ql-5:ruby_tokeninfo_120#join_rhs ...................................................................................................................................................................................................................................................................................................................................................................... 6s
	ReDoS.ql-5:Synthesis::ImplicitSelfSynthesis::regularMethodCallSelfSynthesis#fff ............................................................................................................................................................................................................................................................................................................................. 4.3s (9 evaluations with max 1.3s in Synthesis::ImplicitSelfSynthesis::regularMethodCallSelfSynthesis#fff/3@i2#17f93x)
	ReDoS.ql-5:ruby_tokeninfo_102#join_rhs ...................................................................................................................................................................................................................................................................................................................................................................... 4.3s
	ReDoS.ql-5:AST::AstNode::getAChild_dispred#2#fff ............................................................................................................................................................................................................................................................................................................................................................ 4.2s
	ReDoS.ql-5:ruby_tokeninfo_10#join_rhs ....................................................................................................................................................................................................................................................................................................................................................................... 3.7s
	ReDoS.ql-5:AST::Cached::synthChild#fff ...................................................................................................................................................................................................................................................................................................................................................................... 3.6s (43 evaluations with max 1.3s in AST::Cached::synthChild#fff/3@i6#17f939)

After

[2021-11-16 16:16:27] (142s) Timings for last stage:
[2021-11-16 16:16:27] (142s) 	- Extensionals: 0ms
[2021-11-16 16:16:27] (142s) 	- Intensionals: 2min27.697s ... of which ...
[2021-11-16 16:16:27] (142s) 		- Nonrecursive intensionals: 1min33.368s
[2021-11-16 16:16:27] (142s) 		- Recursive intensionals: 54.328s
[2021-11-16 16:16:27] (142s) 	- Building results: 0ms
[2021-11-16 16:16:27] CSV_QUERY_PROFILES: ReDoS.ql-5,0,147697,93368,54328,0
[2021-11-16 16:16:27] (142s) Clause timing report:
[2021-11-16 16:16:27] (142s) 
[2021-11-16 16:16:27] 
	ReDoS.ql-5:Operation::UnaryOperationImpl::getOperandImpl_dispred#ff ......................................................................................................................................................................................................................................................................................................................................... 8.3s (31 evaluations with max 3s in Operation::UnaryOperationImpl::getOperandImpl_dispred#ff/2@i12#7e8868)
	ReDoS.ql-5:AST::AstNode_not_AliasStmt_ArgumentList_ArrayLiteral_Block_BlockArgument_Call_Callable_CaseExpr_ConditionalExpr_ConstantAccess_HashLiteral_Loop_MethodBase_NamedParameter_Namespace_Operation_Pair_RangeLiteral_RescueClause_RescueModifierExpr_ReturningStmt_SingletonClass_StmtSequence_StringConcatenation_StringlikeLiteral_Toplevel_TuplePattern_TuplePatternParameter_UndefStmt_WhenExpr#f . 6s
	ReDoS.ql-5:ruby_tokeninfo_120#join_rhs ...................................................................................................................................................................................................................................................................................................................................................................... 5.8s
	ReDoS.ql-5:Call::MethodCallImpl::getReceiverImpl_dispred#ff#reorder_1_0 ..................................................................................................................................................................................................................................................................................................................................... 4.4s (37 evaluations with max 464ms in Call::MethodCallImpl::getReceiverImpl_dispred#ff#reorder_1_0/2@i3#7e8869)
	ReDoS.ql-5:Operation::AssignmentImpl::getRightOperandImpl_dispred#ff ........................................................................................................................................................................................................................................................................................................................................ 3.9s (34 evaluations with max 2s in Operation::AssignmentImpl::getRightOperandImpl_dispred#ff/2@i3#7e8865)
	ReDoS.ql-5:ruby_tokeninfo_102#join_rhs ...................................................................................................................................................................................................................................................................................................................................................................... 3.9s
	ReDoS.ql-5:Operation::BinaryOperationImpl::getRightOperandImpl_dispred#ff#reorder_1_0 ....................................................................................................................................................................................................................................................................................................................... 3.7s (34 evaluations with max 1.8s in Operation::BinaryOperationImpl::getRightOperandImpl_dispred#ff#reorder_1_0/2@i12#7e8866)
	ReDoS.ql-5:Operation::BinaryOperationImpl::getLeftOperandImpl_dispred#ff .................................................................................................................................................................................................................................................................................................................................... 3.7s (35 evaluations with max 1.8s in Operation::BinaryOperationImpl::getLeftOperandImpl_dispred#ff/2@i12#7e8867)

aibaars
aibaars approved these changes Nov 16, 2021
View reviewed changes
Copy link
Copy Markdown
Contributor

@aibaars aibaars left a comment

Choose a reason for hiding this comment

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

Looks great to me.

@hvitved hvitved merged commit 7cfc696 into github:main Nov 17, 2021
@hvitved hvitved deleted the ruby/synthesis-realnode-recursion branch November 17, 2021 08:03
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

1 more reviewer

@aibaars aibaars aibaars approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

Ruby

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@hvitved @aibaars