Skip to content

Ruby: Rework getConstantValue implementation#8484

Merged
hvitved merged 3 commits intogithub:mainfrom
hvitved:ruby/constant-value-rework
Mar 24, 2022
Merged

Ruby: Rework getConstantValue implementation#8484
hvitved merged 3 commits intogithub:mainfrom
hvitved:ruby/constant-value-rework

Conversation

@hvitved
Copy link
Contributor

@hvitved hvitved commented Mar 18, 2022

This PR rewrites the getConstantValue implementation, to avoid bad performance arising from unnecessary recursion through newtype constructors. Previously, we had predicates

ConstantValue ExprCfgNode::getConstantValue();
ConstantValue Expr::getConstantValue();

defined (mutually) recursively by virtual dispatch. However, this meant we had to populate the newtype underlying ConstantValue as part of the recursion, since QL does not permit unbound newtypes, which in turn adds artificial (non-linear) recursion through the constructors in each predicate.

In the new implementation, we instead define the following three predicates, for each type T of ConstantValue:

predicate isT(ExprCfgNode n, T v);
predicate isTExprNoCfg(Expr e, T v);
predicate isTExpr(Expr e, T v);

and then the result of those is used to define the newtype, and the user-facing getConstantValue predicates, but only after the recursive constant propagation computation. (The isTExprNoCfg is not related to the performance optimization.)

One down-side of this approach is that we have to replicate logic for each type T, for example, isInt and isString both have to replicate how constants propagate through assignments. We may be able to get rid of some of this duplication using parameterized modules, though.

@github-actions github-actions bot added the Ruby label Mar 18, 2022
@hvitved hvitved force-pushed the ruby/constant-value-rework branch 3 times, most recently from 649fa28 to eee4941 Compare March 21, 2022 20:32
@hvitved hvitved force-pushed the ruby/constant-value-rework branch from eee4941 to 99ddfb4 Compare March 22, 2022 09:07
@hvitved hvitved marked this pull request as ready for review March 22, 2022 13:17
@hvitved hvitved requested a review from a team as a code owner March 22, 2022 13:17
@hvitved hvitved added the no-change-note-required This PR does not need a change note label Mar 22, 2022
@nickrolfe
Copy link
Contributor

This will conflict with #7985, if we decide that's a change we want. It should be easy to resolve the conflicts, but we might want to consider the consequences for predicate names in this PR (e.g. getNonSymbolValue would probably be better named something like getStringValue).

Copy link
Contributor

@nickrolfe nickrolfe left a comment

Choose a reason for hiding this comment

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

I'm only half-way through reviewing, but what I've seen so far makes sense, and it looks like the test output shows only improvements.

The isT/isTExprNoCfg/isTExpr predicates do seem quite boilerplatey, but they're also reasonably straightforward.

Copy link
Contributor

@nickrolfe nickrolfe left a comment

Choose a reason for hiding this comment

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

Looks good to me, other than addressing my comment about future-proofing for tracking regexp values separately from strings.

@hvitved
Copy link
Contributor Author

hvitved commented Mar 24, 2022

Performance numbers:

source a_m a_std b_m b_std diff relative
Median (excl. partials) -1 -0.0197
Overall (excl. partials) 5656 5141 -515.5 -0.0911
hahwul__mad-metasploit 294.7 23.86 243.3 21.01 -51.33 -0.174
opal__opal 1366 131.5 1186 43.13 -180.8 -0.132
aws__aws-sdk-ruby 509.7 66.98 446.3 46.46 -63.33 -0.124
googleapis__google-cloud-ruby 562.7 22.81 495.7 22.37 -67 -0.119
ruby__ruby 1194 108.7 1064 74.27 -130 -0.109
rubyreferences__rubyref 21 0 20 0 -1 -0.0476
diaspora__diaspora 50 0 48 0 -2 -0.0400
gitlabhq__gitlabhq 649 0 625 0 -24 -0.0370
errbit__errbit 29 0 28 0 -1 -0.0345
heartcombo__devise 29 0 28 0 -1 -0.0345
activeadmin__activeadmin 32 0 31 0 -1 -0.0313
fastlane__fastlane 75 0 73 0 -2 -0.0267
rails__rails 152 0 149 0 -3 -0.0197
jeremyevans__sequel 79 0 78 0 -1 -0.0127
spinkham__Hacme-Casino 19 0 19 0 0 0
rest-client__rest-client 21 0 21 0 0 0
backup__backup 30 0 30 0 0 0
opf__openproject 131 0 131 0 0 0
discourse__discourse 227 0 227 0 0 0
microsoft__OMS-Agent-for-Linux 32 0 33 0 1 0.0313
OWASP__railsgoat 23 0 24 0 1 0.0435
iknowjason__hammer 20 0 21 0 1 0.0500
thedeadrobots__bwa_cyclone_transfers 18 0 19 0 1 0.0556
doorkeeper-gem__doorkeeper 25 0 27 0 2 0.0800
spree__spree 67 0 74 0 7 0.104

Copy link
Contributor

@nickrolfe nickrolfe left a comment

Choose a reason for hiding this comment

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

LGTM! 🎉

@nickrolfe
Copy link
Contributor

The failing Code Scanning check is spurious, and is being investigated. So we should be good to merge.

@hvitved hvitved merged commit e12b6df into github:main Mar 24, 2022
@hvitved hvitved deleted the ruby/constant-value-rework branch March 24, 2022 13:32
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

no-change-note-required This PR does not need a change note Ruby

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants