Performance improvements since upgrade to 2.16.6

[lcartey]

Description

Addresses some performance issues noted in the upgrade to 2.16.6:

• Determination of compatible function types was slow across multiple queries. This has been addressed by standardizing on the Compatible.qll library, and ensuring all predicates are appropriately bound.
• In some cases the isExcluded mechanism was causing bad join orders. These have been addressed on a case-by-base basis.
• RULE-9-4 has been modified to perform a top-down, rather than bottom-up, detection of pairs of expressions initializing the same element in an array aggregate literal. This reduces the cases significantly.

The performance logs for 2.16.6 still note some increases, particularly in the calculation of standard library features such as the IR. I suggest we re-trigger performance analysis on this PR and see whether they replicate.

Change request type

• [ ] Release or process automation (GitHub workflows, internal scripts)
• [ ] Internal documentation
• [ ] External documentation
• [x] Query files (.ql, .qll, .qls or unit tests)
• [ ] External scripts (analysis report or other code shipped as part of a release)

Rules with added or modified queries

• [ ] No rules added
• [ ] Queries have been added for the following rules:
  • rule number here
• [x] Queries have been modified for the following rules:
  • DCL40-C
  • RULE-5-1
  • RULE-8-3
  • RULE-8-4
  • MSC39-C

Release change checklist

A change note (development_handbook.md#change-notes) is required for any pull request which modifies:

• The structure or layout of the release artifacts.
• The evaluation performance (memory, execution time) of an existing query.
• The results of an existing query in any circumstance.

If you are only adding new rule queries, a change note is not required.

Author: Is a change note required?

• [x] Yes
• [ ] No

🚨🚨🚨 Reviewer: Confirm that format of shared queries (not the .qll file, the .ql file that imports it) is valid by running them within VS Code.

• [x] Confirmed

Reviewer: Confirm that either a change note is not required or the change note is required and has been added.

• [x] Confirmed

Query development review checklist

For PRs that add new queries or modify existing queries, the following checklist should be completed by both the author and reviewer:

Author

• [x] Have all the relevant rule package description files been checked in?
• [x] Have you verified that the metadata properties of each new query is set appropriately?
• [x] Do all the unit tests contain both "COMPLIANT" and "NON_COMPLIANT" cases?
• [x] Are the alert messages properly formatted and consistent with the style guide?
• [x] Have you run the queries on OpenPilot and verified that the performance and results are acceptable?
  As a rule of thumb, predicates specific to the query should take no more than 1 minute, and for simple queries be under 10 seconds. If this is not the case, this should be highlighted and agreed in the code review process.
• [x] Does the query have an appropriate level of in-query comments/documentation?
• [x] Have you considered/identified possible edge cases?
• [x] Does the query not reinvent features in the standard library?
• [x] Can the query be simplified further (not golfed!)

Reviewer

• [x] Have all the relevant rule package description files been checked in?
• [x] Have you verified that the metadata properties of each new query is set appropriately?
• [x] Do all the unit tests contain both "COMPLIANT" and "NON_COMPLIANT" cases?
• [x] Are the alert messages properly formatted and consistent with the style guide?
• [x] Have you run the queries on OpenPilot and verified that the performance and results are acceptable?
  As a rule of thumb, predicates specific to the query should take no more than 1 minute, and for simple queries be under 10 seconds. If this is not the case, this should be highlighted and agreed in the code review process.
• [x] Does the query have an appropriate level of in-query comments/documentation?
• [x] Have you considered/identified possible edge cases?
• [x] Does the query not reinvent features in the standard library?
• [x] Can the query be simplified further (not golfed!)

[lcartey]

/test-performance

[github-actions[bot]]

🏁 Beep Boop! Performance testing for this PR has been initiated. Please check back later for results. Note that the query package generation step must complete before testing will start so it might be a minute.

:bulb: If you do not hear back from me please check my status! I will report even if I fail!

[codeql-coding-standards-automation[bot]]

🏁 Beep Boop! Performance testing complete! See below for performance of the last 3 runs vs your PR. Times are based on predicate performance. You can find full graphs and stats in the PR that was created for this test in the release engineering repo.

Release                            : v2.35.0
Platform                           : x86-linux
Language                           : c
Total_Serialized_Execution_Time_Ms : 4397696
Mean_Predicate_Execution_Time_Ms   : 114.38333289983612
Median_Predicate_Execution_Time_Ms : 1.0
Standard_Deviation_Ms              : 2125.1712718811877
Total_Serialized_Execution_Time_s  : 4397.696
Mean_Query_Execution_Time_s        : 0.1143833328998361
Median_Predicate_Execution_Time_s  : 0.001
Percentile95_Ms                    : 274.0
Number_of_Predicates               : 38447

Release                            : v2.35.0
Platform                           : x86-linux
Language                           : cpp
Total_Serialized_Execution_Time_Ms : 5283229
Mean_Predicate_Execution_Time_Ms   : 123.28150740870376
Median_Predicate_Execution_Time_Ms : 2.0
Standard_Deviation_Ms              : 1186.327155939601
Total_Serialized_Execution_Time_s  : 5283.229
Mean_Query_Execution_Time_s        : 0.1232815074087037
Median_Predicate_Execution_Time_s  : 0.002
Percentile95_Ms                    : 290.0
Number_of_Predicates               : 42855

Release                            : v2.35.0
Platform                           : x86-windows
Language                           : c
Total_Serialized_Execution_Time_Ms : 6332025
Mean_Predicate_Execution_Time_Ms   : 164.07185240846786
Median_Predicate_Execution_Time_Ms : 3.0
Standard_Deviation_Ms              : 2309.541856304362
Total_Serialized_Execution_Time_s  : 6332.025
Mean_Query_Execution_Time_s        : 0.1640718524084678
Median_Predicate_Execution_Time_s  : 0.003
Percentile95_Ms                    : 489.0
Number_of_Predicates               : 38593

Release                            : v2.35.0
Platform                           : x86-windows
Language                           : cpp
Total_Serialized_Execution_Time_Ms : 7299920
Mean_Predicate_Execution_Time_Ms   : 168.56601856555673
Median_Predicate_Execution_Time_Ms : 4.0
Standard_Deviation_Ms              : 1341.6973819978125
Total_Serialized_Execution_Time_s  : 7299.92
Mean_Query_Execution_Time_s        : 0.1685660185655567
Median_Predicate_Execution_Time_s  : 0.004
Percentile95_Ms                    : 472.75
Number_of_Predicates               : 43306

Release                            : v2.36.0
Platform                           : x86-windows
Language                           : cpp
Total_Serialized_Execution_Time_Ms : 4565606
Mean_Predicate_Execution_Time_Ms   : 100.34739988570928
Median_Predicate_Execution_Time_Ms : 2.0
Standard_Deviation_Ms              : 544.7653788145617
Total_Serialized_Execution_Time_s  : 4565.606
Mean_Query_Execution_Time_s        : 0.1003473998857092
Median_Predicate_Execution_Time_s  : 0.002
Percentile95_Ms                    : 347.0
Number_of_Predicates               : 45498

Release                            : v2.36.0
Platform                           : x86-windows
Language                           : c
Total_Serialized_Execution_Time_Ms : 3957536
Mean_Predicate_Execution_Time_Ms   : 94.59868531134218
Median_Predicate_Execution_Time_Ms : 2.0
Standard_Deviation_Ms              : 558.0527014506762
Total_Serialized_Execution_Time_s  : 3957.536
Mean_Query_Execution_Time_s        : 0.0945986853113421
Median_Predicate_Execution_Time_s  : 0.002
Percentile95_Ms                    : 344.0
Number_of_Predicates               : 41835

Release                            : v2.36.0
Platform                           : x86-linux
Language                           : cpp
Total_Serialized_Execution_Time_Ms : 4154858
Mean_Predicate_Execution_Time_Ms   : 91.33764206731296
Median_Predicate_Execution_Time_Ms : 2.0
Standard_Deviation_Ms              : 630.2504007516633
Total_Serialized_Execution_Time_s  : 4154.858
Mean_Query_Execution_Time_s        : 0.0913376420673129
Median_Predicate_Execution_Time_s  : 0.002
Percentile95_Ms                    : 245.0
Number_of_Predicates               : 45489

Release                            : v2.36.0
Platform                           : x86-linux
Language                           : c
Total_Serialized_Execution_Time_Ms : 2707846
Mean_Predicate_Execution_Time_Ms   : 65.13629365919368
Median_Predicate_Execution_Time_Ms : 1.0
Standard_Deviation_Ms              : 466.2819432351967
Total_Serialized_Execution_Time_s  : 2707.846
Mean_Query_Execution_Time_s        : 0.0651362936591936
Median_Predicate_Execution_Time_s  : 0.001
Percentile95_Ms                    : 197.0
Number_of_Predicates               : 41572

Release                            : 781
Platform                           : x86-linux
Language                           : cpp
Total_Serialized_Execution_Time_Ms : 3731220
Mean_Predicate_Execution_Time_Ms   : 82.6588391670359
Median_Predicate_Execution_Time_Ms : 2.0
Standard_Deviation_Ms              : 648.4685746979167
Total_Serialized_Execution_Time_s  : 3731.22
Mean_Query_Execution_Time_s        : 0.0826588391670359
Median_Predicate_Execution_Time_s  : 0.002
Percentile95_Ms                    : 217.0
Number_of_Predicates               : 45140

Release                            : 781
Platform                           : x86-linux
Language                           : c
Total_Serialized_Execution_Time_Ms : 2600100
Mean_Predicate_Execution_Time_Ms   : 62.28530362917715
Median_Predicate_Execution_Time_Ms : 1.0
Standard_Deviation_Ms              : 508.9199149475738
Total_Serialized_Execution_Time_s  : 2600.1
Mean_Query_Execution_Time_s        : 0.0622853036291771
Median_Predicate_Execution_Time_s  : 0.001
Percentile95_Ms                    : 189.0
Number_of_Predicates               : 41745

🏁 Below are the slowest predicates for the last 2 releases vs this PR.

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-linux
Language          : cpp
Suite             : autosar-default
Predicate         : HardwareOrProtocolInterface::HardwareOrProtocolInterfaceClass#class#7f026171
Execution_Time_Ms : 25745

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-linux
Language          : cpp
Suite             : autosar-default
Predicate         : ___@element#b_Deviations::DeviationRecord.getACodeIdentifierComment/0#dispred#10d8760b_10#join_rhs_D__#shared
Execution_Time_Ms : 31533

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-linux
Language          : cpp
Suite             : autosar-default
Predicate         : CheckedException::CheckedException#b0aa5ec8
Execution_Time_Ms : 32446

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-linux
Language          : cpp
Suite             : autosar-default
Predicate         : CharacterOutsideTheLanguageStandardBasicSourceCharacterSetUsedInTheSourceCode::getUniversalCharacterName/1#36dbaa42
Execution_Time_Ms : 33747

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-windows
Language          : c
Suite             : misra-default
Predicate         : _Expr::Expr.getValueText/0#dispred#a49585d4#bf#antijoin_rhs
Execution_Time_Ms : 17061

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-windows
Language          : c
Suite             : misra-default
Predicate         : OutOfBounds::OOB::libraryFunctionNameParamTableSimpleString/5#6de8614f#cpe#1236
Execution_Time_Ms : 30801

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-windows
Language          : c
Suite             : misra-default
Predicate         : OutOfBounds::OOB::libraryFunctionNameParamTable/5#79217c12
Execution_Time_Ms : 22507

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-windows
Language          : cpp
Suite             : autosar-default
Predicate         : CheckedException::CheckedException#b0aa5ec8
Execution_Time_Ms : 16245

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-windows
Language          : cpp
Suite             : autosar-default
Predicate         : SSAConstruction::DefUse::defUseRank/4#b00da839
Execution_Time_Ms : 14286

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-windows
Language          : cpp
Suite             : autosar-default
Predicate         : CheckedException::CheckedException#b0aa5ec8
Execution_Time_Ms : 21772

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-windows
Language          : c
Suite             : misra-default
Predicate         : QualifiedName::getUserTypeNameWithoutArgs/1#8cfc98e9
Execution_Time_Ms : 24620

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-windows
Language          : c
Suite             : misra-default
Predicate         : RepeatedInitializationOfAggregateObjectElement::hasMultipleInitializerExprsForSameIndexInternal/4#a4626bc8_3012#join_rhs
Execution_Time_Ms : 15124

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-windows
Language          : cpp
Suite             : autosar-default
Predicate         : Dependency::dependsOnTransitive/2#cbda84a0
Execution_Time_Ms : 18059

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-linux
Language          : cpp
Suite             : autosar-default
Predicate         : QualifiedName::getUserTypeNameWithoutArgs/1#8cfc98e9
Execution_Time_Ms : 32674

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-windows
Language          : cpp
Suite             : autosar-default
Predicate         : ___@element#b_Deviations::DeviationRecord.getACodeIdentifierComment/0#dispred#10d8760b_10#join_rhs_D__#shared
Execution_Time_Ms : 16357

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-linux
Language          : c
Suite             : misra-default
Predicate         : QualifiedName::getUserTypeNameWithoutArgs/1#8cfc98e9
Execution_Time_Ms : 22815

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-linux
Language          : c
Suite             : misra-default
Predicate         : OutOfBounds::OOB::libraryFunctionNameParamTableSimpleString/5#6de8614f#cpe#1236
Execution_Time_Ms : 35361

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-linux
Language          : c
Suite             : cert-default
Predicate         : OutOfBounds::OOB::libraryFunctionNameParamTable/5#79217c12
Execution_Time_Ms : 15487

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-linux
Language          : c
Suite             : cert-default
Predicate         : OutOfBounds::OOB::libraryFunctionNameParamTable/5#79217c12
Execution_Time_Ms : 21324

Release           : v2.36.0
Run               : 2024-10-18_14-06-09
Platform          : x86-linux
Language          : c
Suite             : misra-default
Predicate         : _Expr::Expr.getValueText/0#dispred#a49585d4#bf#antijoin_rhs
Execution_Time_Ms : 18015

Release           : 781
Run               : 2024-10-24_11-19-51
Platform          : x86-linux
Language          : cpp
Suite             : autosar-default
Predicate         : CharacterOutsideTheLanguageStandardBasicSourceCharacterSetUsedInTheSourceCode::getUniversalCharacterName/1#36dbaa42
Execution_Time_Ms : 31295

Release           : 781
Run               : 2024-10-24_11-19-51
Platform          : x86-linux
Language          : cpp
Suite             : autosar-default
Predicate         : CheckedException::CheckedException#b0aa5ec8
Execution_Time_Ms : 30865

Release           : 781
Run               : 2024-10-24_11-19-51
Platform          : x86-linux
Language          : cpp
Suite             : autosar-default
Predicate         : QualifiedName::getUserTypeNameWithoutArgs/1#8cfc98e9
Execution_Time_Ms : 30261

Release           : 781
Run               : 2024-10-24_11-19-51
Platform          : x86-linux
Language          : cpp
Suite             : autosar-default
Predicate         : HardwareOrProtocolInterface::HardwareOrProtocolInterfaceClass#class#7f026171
Execution_Time_Ms : 27121

Release           : 781
Run               : 2024-10-24_11-19-51
Platform          : x86-linux
Language          : cpp
Suite             : autosar-default
Predicate         : ___@element#b_Deviations::DeviationRecord.getACodeIdentifierComment/0#dispred#10d8760b_10#join_rhs_D__#shared
Execution_Time_Ms : 23658

Release           : 781
Run               : 2024-10-24_11-19-51
Platform          : x86-linux
Language          : c
Suite             : misra-default
Predicate         : _Macro::Macro.getName/0#dispred#e28b3699_Preprocessor::PreprocessorBranchDirective#bcd2bde4#b_Prepro__#antijoin_rhs
Execution_Time_Ms : 46160

Release           : 781
Run               : 2024-10-24_11-19-51
Platform          : x86-linux
Language          : c
Suite             : cert-default
Predicate         : OutOfBounds::OOB::libraryFunctionNameParamTable/5#79217c12
Execution_Time_Ms : 21710

Release           : 781
Run               : 2024-10-24_11-19-51
Platform          : x86-linux
Language          : c
Suite             : misra-default
Predicate         : QualifiedName::getUserTypeNameWithoutArgs/1#8cfc98e9
Execution_Time_Ms : 21892

Release           : 781
Run               : 2024-10-24_11-19-51
Platform          : x86-linux
Language          : c
Suite             : misra-default
Predicate         : OutOfBounds::OOB::libraryFunctionNameParamTable/5#79217c12
Execution_Time_Ms : 20440

Release           : 781
Run               : 2024-10-24_11-19-51
Platform          : x86-linux
Language          : c
Suite             : misra-default
Predicate         : OutOfBounds::OOB::libraryFunctionNameParamTableSimpleString/5#6de8614f#cpe#1236
Execution_Time_Ms : 34747

[lcartey]

Publishing a re-formatted table of total serialized time (in seconds) for easier review:

Version	x86-linux-c	x86-linux-cpp
v2.35.0	5283.229	5283.229
v2.36.0	2707.846	4154.858
#781	2600.1	3731.22

With these changes performance is slightly improved for C (4% decrease) and a more significant improvement for C++ (10% decrease) vs. the last release (and a significant performance improvement on both since v2.35.0).

@knewbury01 this should address the slow performance we saw in the 2.37.0 release candidate.