KEMBAR78
Optimize better with maximum array length by BruceForstall · Pull Request #69735 · dotnet/runtime · GitHub
Skip to content

Conversation

@BruceForstall
Copy link
Contributor

The maximum array length is 0x7FFFFFC7 (see
#43301), which is slightly less than
the largest 32-bit signed integer. Use this value in range check and assertion
prop to optimize better. This is due do knowing that a value smaller than
the maximum array length plus a small constant will not overflow. This leads
to being able to remove some bounds checks.

The maximum array length is 0x7FFFFFC7 (see
dotnet#43301), which is slightly less than
the largest 32-bit signed integer. Use this value in range check and assertion
prop to optimize better. This is due do knowing that a value smaller than
the maximum array length plus a small constant will not overflow. This leads
to being able to remove some bounds checks.
@ghost ghost assigned BruceForstall May 24, 2022
@ghost ghost added the area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI label May 24, 2022
@ghost
Copy link

ghost commented May 24, 2022

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

Issue Details

The maximum array length is 0x7FFFFFC7 (see
#43301), which is slightly less than
the largest 32-bit signed integer. Use this value in range check and assertion
prop to optimize better. This is due do knowing that a value smaller than
the maximum array length plus a small constant will not overflow. This leads
to being able to remove some bounds checks.

Author: BruceForstall
Assignees: BruceForstall
Labels:

area-CodeGen-coreclr

Milestone: -

@BruceForstall
Copy link
Contributor Author

/azp run runtime-coreclr jitstress

@azure-pipelines
Copy link

Azure Pipelines successfully started running 1 pipeline(s).

@BruceForstall BruceForstall requested a review from AndyAyersMS May 24, 2022 16:54
@BruceForstall
Copy link
Contributor Author

@AndyAyersMS PTAL
cc @SingleAccretion @dotnet/jit-contrib

// See https://github.com/dotnet/runtime/pull/43301, https://msdn.microsoft.com/en-us/windows/apps/hh285054.aspx.
// CLR throws IDS_EE_ARRAY_DIMENSIONS_EXCEEDED if array length is too large. The practical limit is likely smaller
// due to memory fragmentation.
#define ARRLEN_MAX (0x7FFFFFC7)
Copy link
Contributor

Choose a reason for hiding this comment

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

A thing to watch out for with this value is that range check works on arbitrary BOUNDS_CHECK nodes, and in case of spans (and HWIs/SIMDs), the limit is int.MaxValue.

Copy link
Contributor Author

Choose a reason for hiding this comment

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

@SingleAccretion Does this observation imply an issue with this change, or you're just pointing out to be careful with range bounds?

Copy link
Contributor

Choose a reason for hiding this comment

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

Does this observation imply an issue with this change

Yes, it does.

For example, we must not remove a range check in a loop such as below:

private static int Problem(Span<int> a)
{
    int sum = 0;
    for (int i = 0; i < a.Length; i += 2) // 'i' will overflow for "a.Length == int.MaxValue".
    {
        sum += a[i];
    }

    return sum;
}

And I see we do with this change.

Copy link
Contributor Author

Choose a reason for hiding this comment

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

Maybe I'm missing something. When I compile your test (specifically:

using System;
using System.Runtime.CompilerServices;
namespace testns
{
    class testclass
    {
    [MethodImpl(MethodImplOptions.NoInlining)]
    private static int Problem(Span<int> a)
    {
        int sum = 0;
        for (int i = 0; i < a.Length; i += 2) // 'i' will overflow for "a.Length == int.MaxValue".
        {
            sum += a[i];
        }
        return sum;
    }
    static void Main(string[] args)
    {
        int[] a = new int[10] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int s = Problem(a);
        Console.WriteLine(s);
    }
    }
}

), I see a.Length expanded as

CALL int System.Span`1[Int32][System.Int32].get_Length

whereas this PR only affects GT_ARR_LENGTH nodes, and there are none in the test, so I don't see any diff for this case.

Copy link
Contributor

Choose a reason for hiding this comment

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

so I don't see any diff for this case

That is very surprising to me, there should be a diff with the removed check.

As a reference, I have checked out the change locally and obtained two dumps for Problem, one for the baseline and one for the diff: baselog.txt, difflog.txt, and I do see we remove the check in the diff, which corresponds to this change in range check's logic:

            int tmp = GetArrLength(limit.vn);
            if (tmp <= 0)
            {
-               tmp = ARRLEN_MAX;
+               tmp = CORINFO_Array_MaxLength;
            }

Copy link
Contributor Author

Choose a reason for hiding this comment

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

Ok, it was operator error: using a Debug S.P.C.dll prevents cross-module inlining, and I normally use a Debug build (if at all possible). Running with Checked (and a Debug JIT) repros the problem.

Seems like VN/AssertionProp doesn't keep array and non-array GT_BOUNDS_CHECK usage distinct. Maybe I can revert this line for now and come back to it later.

@BruceForstall
Copy link
Contributor Author

Any further comments?

@BruceForstall
Copy link
Contributor Author

@SingleAccretion Take a look at the latest update: it's only using the array max length if we've got a GT_ARR_LENGTH. This preserves most of the wins, but your test case is zero diff.

Copy link
Contributor

@SingleAccretion SingleAccretion left a comment

Choose a reason for hiding this comment

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

LGTM.

@BruceForstall BruceForstall merged commit 02b4f2e into dotnet:main May 28, 2022
@BruceForstall BruceForstall deleted the IntroduceArrayLenMax branch May 28, 2022 00:40
@BruceForstall
Copy link
Contributor Author

@SingleAccretion Thanks for the great feedback!

@ghost ghost locked as resolved and limited conversation to collaborators Jun 27, 2022
@EgorBo
Copy link
Member

EgorBo commented Jun 28, 2022

Improvements on x64: dotnet/perf-autofiling-issues#5618

@stephentoub
Copy link
Member

Improvements on x64: dotnet/perf-autofiling-issues#5618

I suspect most of those improvements are actually due to #69839.

@EgorBo
Copy link
Member

EgorBo commented Jun 28, 2022

Improvements on x64: dotnet/perf-autofiling-issues#5618

I suspect most of those improvements are actually due to #69839.

Oops 🙂

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Labels

area-CodeGen-coreclr CLR JIT compiler in src/coreclr/src/jit and related components such as SuperPMI

Projects

None yet

Development

Successfully merging this pull request may close these issues.

4 participants