dotnet/runtime

Joseph Musser

@jnm2

@Joe4evr I believe @webczat showed sample code a couple weeks ago showing that bounds checks are elided for Span<T>

IIRC when we looked at it, it appeared to be a result of bounds check elimination on the underlying array though. So it might only kick in for certain situations.

Joe4evr

@Joe4evr

are they even elided with a normal front-to-back access, or only back-to-front?

Joseph Musser

@jnm2

I think this example was just accessing [0]

I forget though. sharplab.io will tell you.

webczat @webczat tries to recall...

Joe4evr

@Joe4evr

idk.... sharplab really isn't telling me much about this

Michał Zegan

@webczat

I don't have that, I don't save stuff. but, hmm, I believe I was just accessing each element using a for (not foreach) loop, front to back

trying with Span, with ArraySegment, and I believe I was also trying to play with some unsafe stuff but I am not sure.

it was never eliding bounds check on array segment or similar struct that I made myself I believe, but it was for span. also there are some span specific intrinsics. I lost most memory of what I was doing

Joseph Musser

@jnm2

@Joe4evr Bounds check looks like the difference between A and B

So something roughly like this right before the access:

mov ecx, 0xa
cmp ecx, 0xa
jbe L004d

Joe4evr

@Joe4evr

right, and [0] doesn't get checked because that's always considered a valid index (even on an empty array as long as you don't dereference the location)

Joseph Musser

@jnm2

That would surprise me. They had to jump through hoops to get a reference to [0] on an empty array IIRC

Yeah, https://source.dot.net/#System.Private.CoreLib/src/System/Runtime/InteropServices/MemoryMarshal.CoreCLR.cs,0a97cbc893e44c76

ref array[0] doesn't dereference the location but C# still demands that the bounds are checked

Joe4evr

@Joe4evr

https://github.com/dotnet/runtime/issues/34989#issuecomment-614068909

Joseph Musser

@jnm2

So in your link it looks like forward has no bounds check but reverse has a bounds check. I noticed that only one of them has a jump to a call right before int3

@Joe4evr I don't think Toub is talking about array/span element access there

Joe4evr

@Joe4evr

yea, just realized that

anyway, I'm just thinking, I have an 8k buffer passed as a span and looping over it 2 bytes at a time, so not having 4000 bounds checks per pass would be very favorable

Joseph Musser

@jnm2

Here you go: dotnet/runtime#9505

Similar genre dotnet/runtime#10950

Zoltan Varga

@vargaz

if you want good perf, its better to use common code patterns i.e. forward instead of backwards, compilers are more likely to be able to optimize those.

Joseph Musser

@jnm2

I would strongly have expected reverse iteration to be common enough to be optimized

Joe4evr

@Joe4evr

so forward iterating a span is actually better?

Joseph Musser

@jnm2

The only difference I'm aware of is that forward iterating avoids an additional bounds check, so yes based on that

follow dotnet/runtime#9505 to find out when this is no longer true

Andy Ayers

@AndyAyersMS

@Joe4evr from your sharplab, look for the loop -- backward has a bounds check

;; forward
L004e: mov ecx, [esi+ebx4]
L0051: call System.Console.WriteLine(Int32)
L0056: inc ebx
L0057: cmp ebx, edi
L0059: jl L004e
;; backward
L004f: cmp ebx, edi
L0051: jae L0065
L0053: mov ecx, [esi+ebx4]
L0056: call System.Console.WriteLine(Int32)
L005b: dec ebx
L005c: test ebx, ebx
L005e: jge L004f

Clinton Ingram

@saucecontrol

that dec/test thing makes me sad every time I see it

Andy Ayers

@AndyAyersMS

The jit modelling of flag state is pretty clunky, but we should be able to fix that.

Clinton Ingram

@saucecontrol

I've been wondering how difficult it is to fix. I keep seeing @EgorBo's peephole optimizations and thinking I should learn that part of the JIT

Joe4evr

@Joe4evr

so is that a regression of some kind? because not even a year ago I read about a case where a pretty hot code path was sped up by doing a back-to-front array fill because it allowed the JIT to elide bounds checks

Joe4evr

@Joe4evr

something to the same effect is even mentioned in the implementation of Guid.TryWriteBytes: https://github.com/dotnet/runtime/blob/master/src/libraries/System.Private.CoreLib/src/System/Guid.cs#L753

Clinton Ingram

@saucecontrol

if the indexes are constant and you check the highest constant first, the JIT can elide the rest

Joe4evr

@Joe4evr

oooooooooh....

I see....

Joseph Musser

@jnm2

Now I'm upset: https://twitter.com/Nick_Craver/status/1254380728382640130

Start menu without web results has been such bliss. Zero distractions.

Joe4evr

@Joe4evr

the answer is Start10, but the fact a 3rd party program needs to exist in the first place illustrates the problem

Joseph Musser

@jnm2

Oh, I remember Stardock

I'm more likely to block bing.com to be honest

Joe4evr

@Joe4evr

yeah, that's probably also a good one

but the Win7-styled menu from Start10 is 100% worth

Andy Ayers

@AndyAyersMS

@saucecontrol this is somewhat different than Egor's cases as the two expressions are not in the same tree -- I would probably modify the xarch CodeGen::genCompareInt to special case compares vs zero and look back at the previous instruction to see if it already set the same flags that the compare would set. If so, don't emit the compare. You would need to build in support for "sets the same flags" determination based on instrDesc.

For the bounds check, in the forward case, elimination happens during RangeCheck, it has a notion of monotonically increasing, but not monotonically decreasing. So it is biased in favor of up-counting loops.

Clinton Ingram

@saucecontrol

Thanks for the hints, @AndyAyersMS. I found the issue for that (dotnet/runtime#10742), and it was marked as skill-level beginner, but I had no idea where to start. I'll give it a try in the next couple weeks

Andy Ayers

@AndyAyersMS

You can look at xarch emitter::AreUpper32BitsZero for a similar late peephole (see dotnet/coreclr#22454)

Clinton Ingram

@saucecontrol

Nice, thanks!

Egor Bogatov

@EgorBo

I wonder how profitable to remove empty/dead loops in Jit :thinking_face:

Where communities thrive

People

Repo info

Activity