Skip to content

Rust: Fix bad joins #19250

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

Merged
merged 2 commits into from
Apr 9, 2025
Merged

Rust: Fix bad joins #19250

merged 2 commits into from
Apr 9, 2025

Conversation

hvitved
Copy link
Contributor

@hvitved hvitved commented Apr 8, 2025

Fixes two bad joins, reported by DCA's Join-order badness report. DCA shows an average 3% analysis time speedup.

hvitved added 2 commits April 8, 2025 13:10
Before
```
Pipeline standard for PathResolution::unqualifiedPathLookup/2#6b171b76#reorder_2_0_1@822d53wq was evaluated in 61 iterations totaling 118ms (delta sizes total: 131072).
          606491   ~0%    {4} r1 = SCAN `PathResolution::getASuccessor/3#febac7bd#prev_delta` OUTPUT In.1, In.2, In.0, In.3
          106457   ~1%    {3}    | JOIN WITH `PathResolution::unqualifiedPathLookup/4#e32cdfce_1230#join_rhs` ON FIRST 3 OUTPUT Lhs.3, Rhs.3, Lhs.1

          606491   ~2%    {4} r2 = SCAN `PathResolution::getASuccessor/3#febac7bd#prev_delta` OUTPUT In.0, In.2, In.3, In.1

           19261   ~0%    {4} r3 = JOIN r2 WITH `PathResolution::ModuleLikeNode.isRoot/0#dispred#21662e64` ON FIRST 1 OUTPUT Lhs.3, Lhs.0, Lhs.1, Lhs.2

        42776643   ~1%    {4} r4 = JOIN r2 WITH `doublyBoundedFastTC@PathResolution::hasChild/2#6b318d51#2@PathResolution::isRoot/1#a01ce5c3#1@PathResolution::hasCratePath/1#73ea688d#1` ON FIRST 1 OUTPUT Lhs.3, Rhs.1, Lhs.1, Lhs.2

        42795904   ~1%    {4} r5 = r3 UNION r4
           24921   ~6%    {3}    | JOIN WITH `PathResolution::RelevantPath.isCratePath/2#e595e892_120#join_rhs` ON FIRST 2 OUTPUT Lhs.3, Rhs.2, Lhs.2

          131378   ~2%    {3} r6 = r1 UNION r5
          131072   ~2%    {3}    | AND NOT `PathResolution::unqualifiedPathLookup/2#6b171b76#reorder_2_0_1#prev`(FIRST 3)
                          return r6
```

After
```
Pipeline standard for PathResolution::unqualifiedPathLookup/2#6b171b76#reorder_2_0_1@0553a4wi was evaluated in 66 iterations totaling 10ms (delta sizes total: 131072).
        610251  ~0%    {4} r1 = SCAN `PathResolution::getASuccessor/3#febac7bd#prev_delta` OUTPUT In.1, In.2, In.0, In.3
        131378  ~0%    {3}    | JOIN WITH `PathResolution::unqualifiedPathLookup1/4#781de0cd_1230#join_rhs` ON FIRST 3 OUTPUT Lhs.3, Rhs.3, Lhs.1
        131072  ~0%    {3}    | AND NOT `PathResolution::unqualifiedPathLookup/2#6b171b76#reorder_2_0_1#prev`(FIRST 3)
                       return r1
```
Before
```
Pipeline standard for PathResolution::getAPrivateVisibleModule/1#3829a5ee@822d5hwq was evaluated in 24 iterations totaling 16ms (delta sizes total: 4843).
         105047   ~63652%    {2} r1 = SCAN `PathResolution::resolvePathPrivate/3#56db2cdf#reorder_1_2_0_3#prev_delta` OUTPUT In.0, In.0

             69       ~0%    {2} r2 = JOIN `#PathResolution::ItemNode.getImmediateParentModule/0#dispred#57c4c6d5Plus#bf#reorder_1_0#prev_delta` WITH `PathResolution::resolvePathPrivate/3#56db2cdf#reorder_1_2_0_3#prev` ON FIRST 1 OUTPUT Lhs.0, Lhs.1

        5766690  ~148309%    {2} r3 = JOIN `PathResolution::resolvePathPrivate/3#56db2cdf#reorder_1_2_0_3#prev_delta` WITH `#PathResolution::ItemNode.getImmediateParentModule/0#dispred#57c4c6d5Plus#bf#reorder_1_0#prev` ON FIRST 1 OUTPUT Lhs.0, Rhs.1

        5871806  ~143984%    {2} r4 = r1 UNION r2 UNION r3
           6859     ~148%    {2}    | AND NOT `PathResolution::getAPrivateVisibleModule/1#3829a5ee#prev`(FIRST 2)
                             return r4
```

After
```
Pipeline standard for PathResolution::getAPrivateVisibleModule/1#3829a5ee@5edefhwp was evaluated in 12 iterations totaling 0ms (delta sizes total: 3515).
         339   ~1%    {2} r1 = SCAN `PathResolution::isItemParent/1#d5e587d6#prev_delta` OUTPUT In.0, In.0

        3130   ~0%    {2} r2 = JOIN `PathResolution::isItemParent/1#d5e587d6#prev_delta` WITH `#PathResolution::ItemNode.getImmediateParentModule/0#dispred#57c4c6d5Plus#bf#reorder_1_0#prev` ON FIRST 1 OUTPUT Lhs.0, Rhs.1

          46   ~0%    {2} r3 = JOIN `#PathResolution::ItemNode.getImmediateParentModule/0#dispred#57c4c6d5Plus#bf#reorder_1_0#prev_delta` WITH `PathResolution::isItemParent/1#d5e587d6#prev` ON FIRST 1 OUTPUT Lhs.0, Lhs.1

        3515   ~2%    {2} r4 = r1 UNION r2 UNION r3
        3515   ~2%    {2}    | AND NOT `PathResolution::getAPrivateVisibleModule/1#3829a5ee#prev`(FIRST 2)
                      return r4
```
@github-actions github-actions bot added the Rust Pull requests that update Rust code label Apr 8, 2025
@hvitved hvitved marked this pull request as ready for review April 9, 2025 06:45
@Copilot Copilot AI review requested due to automatic review settings April 9, 2025 06:45
Copy link
Contributor

@Copilot Copilot AI left a comment

Choose a reason for hiding this comment

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

Copilot wasn't able to review any files in this pull request.

Files not reviewed (1)
  • rust/ql/lib/codeql/rust/internal/PathResolution.qll: Language not supported

@hvitved hvitved requested a review from paldepind April 9, 2025 07:53
Copy link
Contributor

@paldepind paldepind left a comment

Choose a reason for hiding this comment

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

Nice!

@hvitved hvitved merged commit 9323f1a into github:main Apr 9, 2025
16 checks passed
@hvitved hvitved deleted the rust/fix-bad-joins branch April 9, 2025 11:36
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Rust Pull requests that update Rust code
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants