Handle more scenarios for loop cloning #67930

kunalspathak · 2022-04-12T21:14:14Z

Increasing loops that are incremented by more than 1 like "i += 2"

runtime/src/coreclr/tools/Common/TypeSystem/Common/TypeHashingAlgorithms.cs

Lines 44 to 49 in 7bac4e8

    
           for (int i = startIndex; i < src.Length; i += 2) 
        
           { 
        
               _hash1 = (_hash1 + _rotl(_hash1, 5)) ^ src[i]; 
        
               if ((i + 1) < src.Length) 
        
                   _hash2 = (_hash2 + _rotl(_hash2, 5)) ^ src[i + 1]; 
        
           }

Decreasing loops like "i--", "i -= 2", etc.

runtime/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/EqualityComparer.cs

Lines 50 to 63 in 7bac4e8

    
                   internal virtual int LastIndexOf(T[] array, T value, int startIndex, int count) 
        
                   { 
        
                       int endIndex = startIndex - count + 1; 
        
                       for (int i = startIndex; i >= endIndex; i--) 
        
                       { 
        
                           if (Equals(array[i], value)) 
        
                           { 
        
                               return i; 
        
                           } 
        
                       } 
        
                       return -1; 
        
                   } 
        
           #endif 
        
               }

PriorityQueue's Heapify method.

runtime/src/libraries/System.Collections/src/System/Collections/Generic/PriorityQueue.cs

Lines 588 to 591 in 7bac4e8

    
           for (int index = lastParentWithChildren; index >= 0; --index) 
        
           { 
        
               MoveDownDefaultComparer(nodes[index], index); 
        
           }

Contributes to #65342

ghost · 2022-04-12T21:14:21Z

Tagging subscribers to this area: @JulieLeeMSFT
See info in area-owners.md if you want to be subscribed.

Issue Details

Increasing loops that are incremented by more than 1 like "i += 2"
Decreasing loops like "i--", "i -= 2", etc.

Author:	kunalspathak
Assignees:	kunalspathak
Labels:	`area-CodeGen-coreclr`
Milestone:	-

kunalspathak · 2022-04-13T22:06:16Z

Failures are related to #67878

kunalspathak · 2022-04-13T22:27:10Z

@dotnet/jit-contrib , @BruceForstall

BruceForstall · 2022-04-14T19:31:31Z

You need to worry about increment/decrement overflowing a 32-bit integer and wrapping. E.g.:

public static int test_up_big(int[] a, int s)
    {
        int r = 0;
        int i;
        for (i = 1; i < s; i += 2147483647)
        {
            r += a[i];
        }
        return r;
    }

with your code will clone, but generate an access violation, not System.IndexOutOfRangeException.

In the case of for ( ; i < x; i += c), c needs to be strictly less than int.MaxValue - (Array.MaxLength - 1) + 1, which is 0x7fffffff - 0x7fffffc7 + 2 = 0x3a = 58. The idea being that if i was the maximum allowed legal array index of 0x7fffffc6 and you added 0x3a, the result is negative (-2,147,483,648).

Similar applies to down counted loops.

kunalspathak · 2022-04-14T19:38:23Z

public static int test_up_big(int[] a, int s)
{
int r = 0;
int i;
for (i = 1; i < s; i += 2147483647)
{
r += a[i];
}
return r;
}

Thanks for pointing that out. Let me try to fix that.

- Increasing loops that are incremented by more than 1 like "i += 2" - Decreasing loops like "i--", "i -= 2"

kunalspathak · 2022-04-19T19:48:41Z

@BruceForstall - I tried measuring some of the benchmarks that showed up in asmdiffs and they all show improvements.

Faster	base/diff	Base Median (ns)	Diff Median (ns)
BilinearTest.Interpol_Scalar	1.23	12591.21	10245.69
BilinearTest.Interpol_Vector	1.08	27857.16	25908.72
BenchmarksGame.FannkuchRedux_5.RunBench(n: 10, expectedSum: 38)	1.06	16428450.00	15492476.47
BenchmarksGame.ReverseComplement_1.RunBench	1.13	1021397.94	903558.01
ByteMark.BenchEmFloatClass	1.05	771413700.00	734018150.00
ByteMark.BenchEmFloat	1.03	3737632200.00	3641513150.00
System.Collections.Tests.Perf_PriorityQueue<String, String>.HeapSort(Size: 100)	10.80	898710.07	83248.11
System.Collections.Tests.Perf_PriorityQueue<String, String>.HeapSort(Size: 10)	10.44	39025.89	3739.26
System.Collections.Tests.Perf_PriorityQueue<String, String>.HeapSort(Size: 1000)	10.34	14949560.00	1445691.48
System.Collections.Tests.Perf_PriorityQueue<Int32, Int32>.HeapSort(Size: 10)	1.04	203.82	195.96
Benchstone.BenchI.HeapSort.Test	1.03	294538.92	287004.51

Slower	diff/base	Base Median (ns)	Diff Median (ns)	Modality
System.Collections.Tests.Perf_PriorityQueue<Guid, Guid>.HeapSort(Size: 100)	1.02	9744.88	9900.55
System.Collections.Tests.Perf_PriorityQueue<Guid, Guid>.HeapSort(Size: 10)	1.01	396.27	401.45

Here is an example asmdiff from Heapify:

kunalspathak · 2022-04-22T06:08:13Z

ping.

src/coreclr/jit/loopcloning.cpp

src/coreclr/jit/compiler.hpp

src/coreclr/jit/loopcloning.cpp

BruceForstall

LGTM.

I think you should run a jitstress job before merging.

kunalspathak · 2022-04-25T19:28:17Z

/azp run runtime-coreclr jitstress

azure-pipelines · 2022-04-25T19:28:33Z

Azure Pipelines successfully started running 1 pipeline(s).

kunalspathak · 2022-05-05T18:06:07Z

Improvements on windows/x64: dotnet/perf-autofiling-issues#5072
Improvements on windows/arm64: dotnet/perf-autofiling-issues#5145
Improvements on windows/x64: dotnet/perf-autofiling-issues#5114 (Reverse complement)
Improvements on Ubuntu/x64: dotnet/perf-autofiling-issues#5092
Improvements on Windows/x86: dotnet/perf-autofiling-issues#5028

ghost added the area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI label Apr 12, 2022

ghost assigned kunalspathak Apr 12, 2022

kunalspathak marked this pull request as ready for review April 13, 2022 22:27

kunalspathak force-pushed the loop_clone branch from f3ca690 to 6320071 Compare April 19, 2022 16:11

kunalspathak added 6 commits April 19, 2022 10:24

Handle following scenarios for loop cloning:

11e21df

- Increasing loops that are incremented by more than 1 like "i += 2" - Decreasing loops like "i--", "i -= 2"

jit format

a21bd23

Make the loop cloning condition tighter

d74d920

check for stride

6830fb9

Add a check for stride edge scenario

c15f325

Add test case

bd47a52

BruceForstall self-requested a review April 22, 2022 21:55

BruceForstall suggested changes Apr 22, 2022

View reviewed changes

ghost added needs-author-action An issue or pull request that requires more info or actions from the author. and removed needs-author-action An issue or pull request that requires more info or actions from the author. labels Apr 22, 2022

Review feedback

32e8320

kunalspathak force-pushed the loop_clone branch from 6320071 to 32e8320 Compare April 23, 2022 01:03

BruceForstall self-requested a review April 25, 2022 18:29

BruceForstall approved these changes Apr 25, 2022

View reviewed changes

kunalspathak merged commit 1bc09e7 into dotnet:main Apr 26, 2022

kunalspathak deleted the loop_clone branch April 26, 2022 15:58

DrewScoggins mentioned this pull request May 3, 2022

[Perf] Regressions in BenchmarksGame.FannkuchRedux_5 #68822

Closed

JulieLeeMSFT mentioned this pull request Jun 3, 2022

What's new in .NET 7 Preview 5 [WIP] dotnet/core#7441

Closed

ghost locked as resolved and limited conversation to collaborators Jun 4, 2022

	for (int i = startIndex; i < src.Length; i += 2)
	{
	_hash1 = (_hash1 + _rotl(_hash1, 5)) ^ src[i];
	if ((i + 1) < src.Length)
	_hash2 = (_hash2 + _rotl(_hash2, 5)) ^ src[i + 1];
	}

	internal virtual int LastIndexOf(T[] array, T value, int startIndex, int count)
	{
	int endIndex = startIndex - count + 1;
	for (int i = startIndex; i >= endIndex; i--)
	{
	if (Equals(array[i], value))
	{
	return i;
	}
	}
	return -1;
	}
	#endif
	}

	for (int index = lastParentWithChildren; index >= 0; --index)
	{
	MoveDownDefaultComparer(nodes[index], index);
	}

Handle more scenarios for loop cloning #67930

Handle more scenarios for loop cloning #67930

Uh oh!

Conversation

kunalspathak commented Apr 12, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ghost commented Apr 12, 2022

Uh oh!

kunalspathak commented Apr 13, 2022

Uh oh!

kunalspathak commented Apr 13, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

BruceForstall commented Apr 14, 2022

Uh oh!

kunalspathak commented Apr 14, 2022

Uh oh!

kunalspathak commented Apr 19, 2022

Uh oh!

kunalspathak commented Apr 22, 2022

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

BruceForstall left a comment

Choose a reason for hiding this comment

Uh oh!

kunalspathak commented Apr 25, 2022

Uh oh!

azure-pipelines bot commented Apr 25, 2022

Uh oh!

kunalspathak commented May 5, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

kunalspathak commented Apr 12, 2022 •

edited

Loading

kunalspathak commented Apr 13, 2022 •

edited

Loading

kunalspathak commented May 5, 2022 •

edited

Loading