Elide bounds checks for partial array/span iteration

The JIT currently removes bounds checks when looping over an array normally.

public static int Sum(ReadOnlySpan<int> span)
{
    int acc = 0;

    for (int i = 0; i < span.Length; i++)
        acc += span[i];

    return acc;
}

And when the iteration doesn't begin at 0.

for (int i = 4; i < span.Length; i++)
    acc += span[i];

However, it does not remove them when the iteration ends before the end of the array.

for (int i = 0; i < span.Length - 1; i++)
    acc += span[i];

In a similar pattern often used when parsing data, the bounds checks are not removed when it can be proven there will be no OOB accesses. (Simple example for illustrative purposes)

public static bool HasRepeat(ReadOnlySpan<int> span)
{
    for (int i = 0; i < span.Length - 1; i++)
    {
        if (span[i] == span[i + 1])
            return true;
    }

    return false;
}

for (int i = 1; i < span.Length; i++)
{
    if (span[i - 1] == span[i])
        return true;
}

Since these patterns often appear in tight loops, eliding the bounds checks might result in a noticeable performance increase in certain situations.

category:cq
theme:bounds-checks
skill-level:intermediate
cost:medium
impact:medium

#9505 partially related

@AndyAyersMS

@AndyAyersMS @erozenfeld

Hmm, seems like we ought to be able to handle cases like these.

Marking as 5.0 -- we should at drill in and figure out where we get confused, and see how difficult this would be to fix.

@AndyAyersMS

@AndyAyersMS I have a quick prototype to remove bound checks for for (int i=0; i<array.Length - C; i++): EgorBo@6085b6a (allows array cloning for loops with ARR_LEN + INT_CNS conditions)

static void Test(int[] array)
{
    for (int i = 0; i < array.Length - 1; i++)
    {
        array[i] = 42;
    }
}

; Method Test(System.Int32[])
G_M55902_IG01:
G_M55902_IG02:
       33C0                 xor      eax, eax
       8B5108               mov      edx, dword ptr [rcx+8]
       FFCA                 dec      edx
       85D2                 test     edx, edx
       7E12                 jle      SHORT G_M55902_IG04
G_M55902_IG03:
       4C63C0               movsxd   r8, eax
       42C74481102A000000   mov      dword ptr [rcx+4*r8+16], 42
       FFC0                 inc      eax
       3BD0                 cmp      edx, eax
       7FEE                 jg       SHORT G_M55902_IG03
G_M55902_IG04:
       C3                   ret      
; Total bytes of code: 30

@EgorBo

I took a shot at this at #36263 (Apologies if I stepped on your toes @EgorBo, I didn't see your comment when I started on it).

It deals with the first two cases here fine. The last one is a bit trickier. We see the i - 1 and give up when we hit the check here:

runtime/src/coreclr/src/jit/rangecheck.cpp

Line 351 in 751a10e

    
           return (op2->AsIntConCommon()->IconValue() >= 0) && IsMonotonicallyIncreasing(op1, false);

I'd have to look at it more to see if there's an easy way of relaxing that conditional.

@EgorBo

Apologies if I stepped on your toes @EgorBo

You did not 🙂

@nathan-moore

With the first 2 cases fixed by @nathan-moore I am goind to change the milestone for the third to "Future". The last case requires more changes and it probably won't be done in 5.0.

Vote to move this to .Net 8 milestone. In real code, we often access the previous or next element of an array.

Sure, I'll put it in 8.0 for now.

Seems like all code snippets elide bounds checks in Main

Navigation Menu

Repository navigation

Elide bounds checks for partial array/span iteration #31638

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Elide bounds checks for partial array/span iteration #31638

Description

Activity

EgorBo commented on Feb 3, 2020

BruceForstall commented on Feb 6, 2020

AndyAyersMS commented on May 6, 2020

EgorBo commented on May 8, 2020

nathan-moore commented on May 12, 2020

EgorBo commented on May 12, 2020

sandreenko commented on Jun 22, 2020

iSazonov commented on Dec 1, 2022

BruceForstall commented on Dec 1, 2022

EgorBo commented on Mar 19, 2025

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions