Skip to content

[Perf] Regressions in IndexOf #54165

Closed
Closed
[Perf] Regressions in IndexOf#54165
Assignees
AndyAyersMS
Labels
arch-x64area-CodeGen-coreclrCLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMIos-windowstenet-performancePerformance related issuetenet-performance-benchmarksIssue from performance benchmark
Milestone
8.0.0

Description

@DrewScoggins
DrewScoggins
opened on Jun 14, 2021

Run Information

Architecture x64
OS Windows 10.0.18362
Baseline 4a73cb9af55814e26b78f22d30bd35faa60c31a3
Compare 6ab1cee00ba41b308009c88864aba46b0f61f061
Diff Diff

Regressions in System.Globalization.Tests.StringSearch

Benchmark Baseline Test Test/Base Test Quality Baseline IR Compare IR IR Ratio Baseline ETL Compare ETL
LastIndexOf_Word_NotFound - Duration of single invocation 556.53 ns 592.84 ns 1.07 0.01
LastIndexOf_Word_NotFound - Duration of single invocation 556.77 ns 592.91 ns 1.06 0.00
IndexOf_Word_NotFound - Duration of single invocation 560.81 ns 594.70 ns 1.06 0.00
LastIndexOf_Word_NotFound - Duration of single invocation 556.54 ns 590.50 ns 1.06 0.00
IndexOf_Word_NotFound - Duration of single invocation 560.67 ns 596.84 ns 1.06 0.00
IndexOf_Word_NotFound - Duration of single invocation 560.08 ns 596.92 ns 1.07 0.00

graph
graph
graph
graph
graph
graph
Historical Data in Reporting System

Repro

git clone https://github.com/dotnet/performance.git
py .\performance\scripts\benchmarks_ci.py -f netcoreapp5.0 --filter 'System.Globalization.Tests.StringSearch*'
Details

Payloads

Baseline
Compare

Histogram

System.Globalization.Tests.StringSearch.LastIndexOf_Word_NotFound(Options: (en-US, IgnoreNonSpace, False))

System.Globalization.Tests.StringSearch.LastIndexOf_Word_NotFound(Options: (en-US, None, False))

System.Globalization.Tests.StringSearch.IndexOf_Word_NotFound(Options: (, None, False))

System.Globalization.Tests.StringSearch.LastIndexOf_Word_NotFound(Options: (, None, False))

System.Globalization.Tests.StringSearch.IndexOf_Word_NotFound(Options: (en-US, IgnoreNonSpace, False))

System.Globalization.Tests.StringSearch.IndexOf_Word_NotFound(Options: (en-US, None, False))

Docs

Profiling workflow for dotnet/runtime repository
Benchmarking workflow for dotnet/runtime repository

### Run Information
Architecture x64
OS Windows 10.0.18362
Baseline 4a73cb9af55814e26b78f22d30bd35faa60c31a3
Compare 6ab1cee00ba41b308009c88864aba46b0f61f061
Diff Diff

Regressions in System.Memory.ReadOnlySpan

Benchmark Baseline Test Test/Base Test Quality Baseline IR Compare IR IR Ratio Baseline ETL Compare ETL
IndexOfString - Duration of single invocation 231.36 ns 245.69 ns 1.06 0.00

graph
Historical Data in Reporting System

Repro

git clone https://github.com/dotnet/performance.git
py .\performance\scripts\benchmarks_ci.py -f netcoreapp5.0 --filter 'System.Memory.ReadOnlySpan*'
Details

Payloads

Baseline
Compare

Histogram

System.Memory.ReadOnlySpan.IndexOfString(input: "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAXAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", value: "x", comparisonType: InvariantCultureIgnoreCase)

Docs

Profiling workflow for dotnet/runtime repository
Benchmarking workflow for dotnet/runtime repository

Activity

  1. DrewScoggins
    added
    os-windows
    tenet-performancePerformance related issue
    tenet-performance-benchmarksIssue from performance benchmark
    arch-x64
    on Jun 14, 2021
  2. ghost added
    area-System.Globalization
    on Jun 14, 2021
  3. ghost added
    untriagedNew issue has not been triaged by the area owner
    on Jun 14, 2021
  5. DrewScoggins
    changed the title [-][Perf] Changes at 5/19/2021 3:09:27 AM[/-] [+][Perf] Regressions in IndexOf[/+] on Jun 14, 2021
  6. tarekgh
    added
    area-CodeGen-coreclrCLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI
    and removed
    area-System.Globalization
    on Jun 15, 2021

  7. tarekgh commented on Jun 15, 2021

    @tarekgh
    tarekgh
    on Jun 15, 2021
    Member

    @EgorBo @kunalspathak, I have looked at the merged commits around the regression time, I am not seeing anything can be related to cause this issue except the following two commits:

    commit 8868e97a3e69f43e7e97f1b7da463185de9300bf
Author: Kunal Pathak <Kunal.Pathak@microsoft.com>
Date:   Wed May 19 10:01:26 2021 +0530

    Refactor LSRA's heuristics selection (#52832)


commit 0e1adc01d16393c0212c389580e1b788caae5b03
Author: Egor Bogatov <egorbo@gmail.com>
Date:   Wed May 19 09:15:32 2021 +0300

    JIT: Convert some of the old-style intrinsics to NamedIntrinsics (#52156)

    We don't have any code globalization code changes at all around that time. Could you please have a look?

    CC @jkotas

  8. kunalspathak commented on Jun 15, 2021

    @kunalspathak
    kunalspathak
    on Jun 15, 2021
    Contributor

    It seems to be coming from #52827 - @AndyAyersMS

  9. JulieLeeMSFT
    assigned
    AndyAyersMS
    on Jun 16, 2021
  10. JulieLeeMSFT
    removed
    untriagedNew issue has not been triaged by the area owner
    on Jun 16, 2021
  11. JulieLeeMSFT
    added this to the 6.0.0 milestone on Jun 16, 2021

  12. 3 remaining items

  13. AndyAyersMS commented on Aug 10, 2021

    @AndyAyersMS
    AndyAyersMS
    on Aug 10, 2021
    Member

    Need to use a net5.0 host for BDN to avoid some SDK skew trying to run older bits. Hopefully this is ok. Looks like per that my change indeed introduced a regression, but not from the switch peeling. Instead it may be here:

    runtime/src/coreclr/jit/fgopt.cpp

    Lines 1778 to 1783 in 705bbfd

    // If either block or bNext has a profile weight
    // or if both block and bNext have non-zero weights
    // then we will use the max weight for the block.
    //
    const bool hasProfileWeight = block->hasProfileWeight() || bNext->hasProfileWeight();
    const bool hasNonZeroWeight = (block->bbWeight > BB_ZERO_WEIGHT) || (bNext->bbWeight > BB_ZERO_WEIGHT);

    The old logic effectively had && for that second condition, not ||. Am seeing what fixing this does....

  14. AndyAyersMS commented on Aug 10, 2021

    @AndyAyersMS
    AndyAyersMS
    on Aug 10, 2021
    Member

    Hmm, not that. Maybe I'll try reverting more in the area of this change. The old logic seemed wonky but perhaps it had merit at times.

  15. AndyAyersMS commented on Aug 10, 2021

    @AndyAyersMS
    AndyAyersMS
    on Aug 10, 2021
    Member

    Yep, that seems to do the trick:

    Method Jit Version Options Mean
    IndexOf_Word_NotFound main + wonky part restored (, None, False) 376.9 ns
    IndexOf_Word_NotFound main (, None, False) 425.6 ns
    IndexOf_Word_NotFound 6ec2fba (, None, False) 430.7 ns
    IndexOf_Word_NotFound 6ec2fba~1 (, None, False) 393.6 ns

    Time to look at what this older logic actually did. Perhaps it is more sensible than I realized.

  16. AndyAyersMS commented on Aug 10, 2021

    @AndyAyersMS
    AndyAyersMS
    on Aug 10, 2021
    Member

    The significant diff is in CompareInfo:IndexOfOrdinalHelper(ReadOnlySpan`1,ReadOnlySpan`1,int,long,bool):int:this

    ;;; main

       44897528             mov      dword ptr [rbp+28H], r14d
       4C63E7               movsxd   r12, edi
       4C8965A8             mov      qword ptr [rbp-58H], r12
       49BC78CA6E70FB7F0000 mov      r12, 0x7FFB706ECA78
       4C8B75A8             mov      r14, qword ptr [rbp-58H]
       43803C2600           cmp      byte  ptr [r14+r12], 0
       751D                 jne      SHORT G_M22056_IG25

;;; main + wonky part restored

       44897528             mov      dword ptr [rbp+28H], r14d
       4C63E7               movsxd   r12, edi
       49BE78CA6E70FB7F0000 mov      r14, 0x7FFB706ECA78
       43803C3400           cmp      byte  ptr [r12+r14], 0
       751D                 jne      SHORT G_M22056_IG19

  17. kunalspathak commented on Aug 10, 2021

    @kunalspathak
    kunalspathak
    on Aug 10, 2021
    Contributor

    The old logic effectively had && for that second condition, not ||. Am seeing what fixing this does....

    At least from the comments (that were not changed in #52827) it looks like if either block or bbNext had zero weight, we would make block as rarely used, but with your change, that logic got flipped and we are now marking block as being used more frequently.

  18. AndyAyersMS commented on Aug 10, 2021

    @AndyAyersMS
    AndyAyersMS
    on Aug 10, 2021
    Member

    In this method there's are a mixuture of blocks with and without PGO data. The diff is that the new logic marks some merged blocks as having IBC, where the old logic did not.

    Flow graph is identical before these merges. Here's a sample merge: the bNext block BB05has PGO data, but since the count exactly matches the count in BB04, the old logic does not mark BB04 has as having PGO, while the new logic does...

    and that is enough to perturb LSRA and introduce a spill.

BB04 [0002]  1       BB03                  1           [036..04C)                                     i bwd 
BB05 [0039]  1       BB04                  1    100    [036..037)-> BB07 (always)                     i bwd IBC 

Compacting blocks BB04 and BB05:

;; main

BB04 [0002]  1       BB03                  1    100    [036..04C)-> BB50 ( cond )                     i bwd IBC 

;; main + old

BB04 [0002]  1       BB03                  1           [036..04C)-> BB50 ( cond )                     i bwd

    The general problem of having a method with mixtures of PGO and non PGO method blocks (from inlining, typically) is something we need to work on in .NET 7.

    We could revert this bit of the change but I suspect it would cause regressions elsewhere. So I recommend we leave NET 6 alone and work on this down the road.

  19. AndyAyersMS commented on Aug 10, 2021

    @AndyAyersMS
    AndyAyersMS
    on Aug 10, 2021
    Member

    One last note -- the reason marking a block has having PGO (IBC) is so impactful is that it prevents the simple non-PGO based weight updates when we recognize loops. So later on we end up with this odd weight assignment:

    ;; main

BB17 [0017]  2       BB16,BB20            32         3 [0FA..11C)-> BB33 ( cond )                     i Loop Loop0 bwd bwd-target LIR align 
BB18 [0018]  1       BB17                  0.50  50  3 [11C..12F)-> BB33 ( cond )                     i bwd IBC LIR 
BB19 [0019]  1       BB18                 32         3 [12F..135)-> BB22 ( cond )                     i bwd LIR 
BB20 [0023]  1       BB19                 16         3 [156..16D)-> BB17 ( cond )                     i bwd LIR 

;; main + old

BB17 [0017]  2       BB16,BB20            32     3 [0FA..11C)-> BB33 ( cond )                     i Loop Loop0 bwd bwd-target LIR align 
BB18 [0018]  1       BB17                 32     3 [11C..12F)-> BB33 ( cond )                     i bwd LIR 
BB19 [0019]  1       BB18                 32     3 [12F..135)-> BB22 ( cond )                     i bwd LIR 
BB20 [0023]  1       BB19                 16     3 [156..16D)-> BB17 ( cond )                     i bwd LIR

    and so we end up spilling in a hot block. Logic for this weight update is here:

    runtime/src/coreclr/jit/optimizer.cpp

    Lines 225 to 237 in d01dae4

    if (!curBlk->hasProfileWeight())
    {
    BasicBlock::weight_t scale = BB_LOOP_WEIGHT_SCALE;
    if (!dominates)
    {
    scale = scale / 2;
    }
    curBlk->scaleBBWeight(scale);
    }
    JITDUMP("\n " FMT_BB "(wt=" FMT_WT ")", curBlk->bbNum, curBlk->getBBWeight(this));

    The general fix for this is to treat PGO and non-PGO weights on an even footing, but that requires earlier and more sensible assignments of non-PGO weights.

  20. AndyAyersMS
    modified the milestones: 6.0.0, Future on Aug 10, 2021

  21. kunalspathak commented on Aug 10, 2021

    @kunalspathak
    kunalspathak
    on Aug 10, 2021
    Contributor

    So I recommend we leave NET 6 alone and work on this down the road.

    Makes sense to me.

  22. JulieLeeMSFT
    modified the milestones: Future, 8.0.0 on Oct 5, 2022

  23. AndyAyersMS commented on Nov 1, 2022

    @AndyAyersMS
    AndyAyersMS
    on Nov 1, 2022
    Member

    Looking at this afresh. For the first test, we were at around 560 when the regression happened:

    newplot - 2022-11-01T152340 693

    Now we're at 520 and have been there a while:
    newplot - 2022-11-01T152545 315

    Other tests here look to be similarly improved or at least back to par. So am going to close this.

  24. AndyAyersMS
    closed this as completedon Nov 1, 2022
  25. ghost locked as resolved and limited conversation to collaborators on Dec 2, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

Labels

arch-x64area-CodeGen-coreclrCLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMIos-windowstenet-performancePerformance related issuetenet-performance-benchmarksIssue from performance benchmark

Type

No type

Projects

No projects

    Milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions