Skip to content

C++: Speed up non-linear recursion in GVN library #12737

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.

Sign up for GitHub

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

Jump to bottom
Merged
jketema merged 2 commits into from
Apr 3, 2023
Merged

C++: Speed up non-linear recursion in GVN library #12737

jketema merged 2 commits into from
Apr 3, 2023

Conversation

@MathiasVP
Copy link
Contributor

@MathiasVP MathiasVP commented Mar 31, 2023

During the work on range analysis I learnt how to structure non-linear recursion so that it's as efficient as possible: ensure that as many tuples as possible are filtered away before the recursive result is joined onto the pipeline. In practice, this is done by transforming code such as:

predicate nonlinear(a) {
  condition(a) and
  nonlinear(a.getFirst()) and
  nonlinear(a.getSecond())
}

into

pragma[nomagic]
predicate nonlinear0(a, isFirst) {
  condition(a) and
  (
    isFirst = true and
    nonlinear(a.getFirst())
    or
    isFirst = false and
    nonlinear(a.getSecond())
  )
}

predicate nonlinear(a) {
  nonlinear0(a, true) and
  nonlinear0(a, false)
}

this ensures that we only join the a's for which condition(a) holds onto the pipeline. This trick is used all throughout the new range analysis library to achieve good performance, and there's no reason why our GVN library shouldn't use the same tricks.

Finally, I also ran Schacks magic regexp to find bad early joins with #prev and applied the standard fix for those.

Since GVN is generally quite fast already, I don't expect this PR to have a super big impact.

@MathiasVP MathiasVP added the no-change-note-required This PR does not need a change note label Mar 31, 2023
@MathiasVP MathiasVP requested review from a team as code owners March 31, 2023 20:21
jketema
jketema approved these changes Apr 3, 2023
View reviewed changes
Copy link
Contributor

@jketema jketema left a comment

Choose a reason for hiding this comment

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

LGTM

@jketema jketema merged commit e5c7c88 into github:main Apr 3, 2023
@hvitved
Copy link
Contributor

hvitved commented Apr 11, 2023

Actually, it is better to do

pragma[nomagic]
predicate nonlinearFirst(a) {
  condition(a) and
  nonlinear(a.getFirst())
}

pragma[nomagic]
predicate nonlinearSecond(a) {
  condition(a) and
  nonlinear(a.getSecond())
}

predicate nonlinear(a) {
  nonlinearFirst(a) and
  nonlinearSecond(a)
}

since otherwise, the prev relation will include a row for each of the two children.

@MathiasVP
Copy link
Contributor Author

MathiasVP commented Apr 11, 2023

Shouldn't that (hopefully) be handled by the optimizer? As in: I would hope that the optimizer did a join with prev where the isFirst column was the constant true for the first join, and the constant false for the second join?

@hvitved
Copy link
Contributor

hvitved commented Apr 11, 2023

Shouldn't that (hopefully) be handled by the optimizer? As in: I would hope that the optimizer did a join with prev where the isFirst column was the constant true for the first join, and the constant false for the second join?

Maybe it is OK, perhaps worth checking out the DIL. I would normally structure the code as in my example to make sure that the prev relations become as small as possible for non-linear recursion.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@jketema jketema jketema approved these changes

Assignees

No one assigned

Labels

C# C++ no-change-note-required This PR does not need a change note

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@MathiasVP @hvitved @jketema