DMD emits a lot of unnecessary bounds checks

[TurkeyMan]

I'm finding a lot of my low-level perf issues are because DMD emits bounds checks everywhere, even where they're not needed, because error checking prior to the index has already caught the cases where the index is out of bounds.

Take this for instance:

immutable ubyte[8] tab = [0,1,2,3,4,5,6,7];

uint f = ...;
if (f >= 8)
  assert(false);
else
{
  // expect no bounds check...
  ubyte x = tab[f];
}

In that case, we are certain that f < 8, but DMD emits a bounds check:

00007FF6A08AB7CB  mov         r9d,8  
00007FF6A08AB7D1  cmp         r8,r9  
00007FF6A08AB7D4  jb          urt.si.unit.fun+187h (07FF6A08AB7E7h)  
00007FF6A08AB7D6  mov         edx,0A3h  
00007FF6A08AB7DB  lea         rcx,[__CB4DBA694D27B192B1C18F754978AF0C (07FF6A0BC0D30h)]  
00007FF6A08AB7E2  call        _d_arraybounds_indexp (07FF6A069286Fh)  
00007FF6A08AB7E7  ...

If I write:

ubyte x = tab[f & 7];

Then the bounds check disappears; so it seems that it is keeping track of f & 7 to determine a value range, but the if/assert immediately above didn't do it...?

There are a million cases like this; but this is just the one I have right in front of me.

[TurkeyMan]

I suggest just trawling some code and looking for array bounds checks; you'll find so many that are redundant because there was a condition immediately prior.

I find myself writing this a LOT: myArray.ptr[n]
...by dereferencing the pointer, it detaches the length and so elides the bounds check. The thing I've noticed is that I do that so often (more often then not) that I wonder why I even have bounds checking enabled!

Basically, my assessment over the last several months has been that in this current state, bounds checking is mostly useless, and I'm starting to think I should stop butchering my code with .ptr and just turn it off.

[jmdavis]

Honestly, if you care about performance this much, you should probably be using ldc or gdc and not dmd. It would be great if dmd could detect and eliminate redundant checks, but Walter is allergic to data flow analysis, so the frontend is unlikely to detect this sort of thing, and I have no clue how capable the dmd backend is at finding stuff like this (but however good it is or isn't, ldc is bound to do better unless separate compilation is making it so that it can't see the checks, though those particular hooks have been templated by now IIRC). Either way, in general, ldc and gdc are going to do a better job of optimizing code, since they have a lot more people working on them to make them produce optimized code. So, while I'm all for dmd doing a better job of it, normally, folks who really care about performance to that degree just don't use dmd outside of development (e.g. at Symmetry, we primarily use dmd during development so that we get faster compilation times, but ldc is used for production code).

As for D code in general, bounds checking is required for the code to actually be @safe, since without it, there's no guarantee that you're actually accessing data in the array (and if you're out-of-bounds, then that violates memory safety). Obviously, you can turn it off if you think that that's going to be best for what you're doing, but it's there because it's required for @safe, and people do screw up or forget their checks sometimes. So, for most folks, it's recommended that they keep the checks in, and if they have a particular piece of code which absolutely need to avoid the check, they can use ptr (though obviously if you feel the need to do that constantly, it does essentially make the bounds checking pointless for you). But as far as defaults go, the checks definitely need to be there.

So, I don't disagree with the idea behind the issue here. Ideally, dmd would do a better job of this (and with better data flow analysis, it may be the case that the frontend would be a good place to detect it given that it understands D in a way that the backends don't), but for the most part, the kind of folks who are concerned about performance to this degree don't use dmd in production.

[jmdavis]

I suggest just trawling some code and looking for array bounds checks; you'll find so many that are redundant because there was a condition immediately prior.

And to respond to this specifically, yes, bounds checking is supposed to be redundant in most cases, because it's an Error if it fails. You're supposed to only ever be using valid indices, and it's a bug in your program if you pass an invalid index. So, in a program without buggy indexing, unless the code is written in such a way that it knows that an index is in bounds without doing a check first, the bounds checking that the language does is going to be redundant (and arguably, even in that case, it's redundant; it's just harder to detect). However, without the checks that the language inserts, you risk memory-safety issues just like you do in C or C++, so the checks need to be there. And barring being optimized out by the compiler, you should expect a lot of redundant checks. It's a case of memory safety trumping performance.

But it's certainly true that if the compiler can detect that the check has already been done (or if it can detect that the check is unnecessary for other reasons), it would ideally remove the check that it automatically inserts with indexing or slicing, since if it knows that the check has been done, it knows that it's redundant and thus unnecessary to guarantee memory safety. So, improvements in this area would be welcome, but the language design here makes it so that you should expect that bounds checking in general is redundant and simply there to ensure memory safety when you do make mistakes. The more unnecessary checks that gets optimized out the better, but they're redundant by their very nature - at least so long as you write correct code.

[ibuclaw]

Honestly, if you care about performance this much, you should probably be using ldc or gdc and not dmd.

Agreed. No bounds checking seen here: https://compiler-explorer.com/z/ofjYYzEoc

[TurkeyMan]

DMD is a very productive compiler.
What I'm suggesting here is that some care be taken to improve the situation. I reckon an awful lot of spurious bounds checks are simple and similar in nature; there may be some low-hanging fruit.

Obviously DMD makes SOME effort here already or the case with tab[f & 7] which I showed above wouldn't work... so DMD does make some effort, and so it's not unreasonable to see it improve. @WalterBright?

[TurkeyMan]

@ibuclaw FYI, there's something odd about the GDC output there; see how it initialises the array with a series of load-immediates, and then puts assert test AFTER initialising the array... the array is unused by the assert branch, so I would expect optimisation to move the branch before the initialisation. LDC got it right; the assert branch is the very first instruction. I would expect the same from GDC...?

[ibuclaw]

@ibuclaw FYI, there's something odd about the GDC output there; see how it initialises the array with a series of load-immediates, and then puts assert test AFTER initialising the array... the array is unused by the assert branch, so I would expect optimisation to move the branch before the initialisation. LDC got it right; the assert branch is the very first instruction. I would expect the same from GDC...?

Not my problem. https://compiler-explorer.com/z/9T551xKs5

[TurkeyMan]

True, although I wonder if that difference where the GCC compiler does one 8-byte load, where GDC does 8 1-byte loads is though? Definitely better codegen to do one reg-sized load... I wonder why the difference :/

[ibuclaw]

True, although I wonder if that difference where the GCC compiler does one 8-byte load, where GDC does 8 1-byte loads is though? Definitely better codegen to do one reg-sized load... I wonder why the difference :/

Ah, you're assuming ldc -O and gdc -O are equivalent. You'll need higher optimisation level to see that load collapse.