171–180 of 195 posts
Similarly, you can turn off bounds-checking in Go like this: go build -gcflags=-B and see if it helps. Generally the assembly looks better, but it doesn't really run faster on a modern chip. Do your own test, and keep the results in mind next time somebody on Hacker News dismisses Go because of the "overwhelming cost of bounds checking".
Earlier quoted context omitted.
Libraries can do this too, in many cases more reliably.
Unless libraries are receiving a copy of the meta representation of the program and running integer equality relations over the dataflow chains, then no, not really.
The library author has certain knowledge of what the library is meant to achieve, where the compiler is obliged to guess according to whatever tea leaves it can find to descry.
In particular, the library author knows that the container won't be changing size over the duration of the loop, something the compiler would have difficulty proving.
Earlier quoted context omitted.
Then it sounds like our branch predictors are shit if they can't deal with simple things like this.
This is exactly what they are designed to do and they do their job well, but they can't do it for free.
Yes, some architectures (including x86) have instructions that hint to the branch predictor, but I think they still end up influencing branch predictor state.
Earlier quoted context omitted.
It's not hard, but when the idiomatically used containers aren't bounds-checked, most code out in the wild won't be, either. Worse yet if you are writing a library and have to interop with other code which will also use those idiomatic types. These days, C++ really should be compiled with bounds-checked indexing and iterators by default. Unfortunately, this is still not a scenario that is well-supported by tooling.
On VC++ it is quite easy to do so, https://learn.microsoft.com/en-us/cpp/standard-library/check... The hard part is changing the mentality from whoever sits at the keyboard.
In my experience with them, the performance hit is far more substantial that a few percent, except in situations where the compiler can elide the checks altogether. For example, simply iterating over std::vector with _ITERATOR_DEBUG_LEVEL=1 is twice as slow if you work with iterators explicitly instead of writing it as a range-for.
And I'm not sure if it can be substantially better, given that C++ as designed simply needs to do more checks to ensure validity - to catch cases like comparing iterators belonging to different containers, or iterators getting invalidated when containers get resized or when the corresponding element is deleted outright. This all can't be done with simple ranges or slices, which is why VC checked iterators maintain a reference to the parent container.
Earlier quoted context omitted.
On VC++ it is quite easy to do so, https://learn.microsoft.com/en-us/cpp/standard-library/check... The hard part is changing the mentality from whoever sits at the keyboard.
FWIW it looks like they're planning to kill it off for release builds: https://github.com/microsoft/STL/issues/277 In my experience with them, the performance hit is far more substantial that a few percent, except in situations where the compiler can elide the checks altogether. For example, simply iterating over std::vector with _ITERATOR_DEBUG_LEVEL=1 is twice as slow if you work with iterators explicitly instead o…
The performance hit from bounds checking was never an issue for most applications I have done in C++.
Why C++? WinDev likes it a lot, alongside COM, and not everything is exposed to .NET.
Earlier quoted context omitted.
And event const can't in general be used for optimizations (because there can be another reference to the same location, or one can just const_cast)
If the thread you are on doesn't modify the variable (e.g. by const_cast), and that variable isn't atomic or volatile, the compiler should be allowed to treat it as invariant. Whether it does in practice probably depends on a lot of things though.
Earlier quoted context omitted.
Unless libraries are receiving a copy of the meta representation of the program and running integer equality relations over the dataflow chains, then no, not really.
Yet, really. The library author has certain knowledge of what the library is meant to achieve, where the compiler is obliged to guess according to whatever tea leaves it can find to descry. In particular, the library author knows that the container won't be changing size over the duration of the loop, something the compiler would have difficulty proving.
What's special about libraries? Every programmer has such knowledge, and every programmer writes buggy code.
Earlier quoted context omitted.
> I note with fear and horror that even in 1980, language designers and users have not learned this lesson. In any respectable branch of engineering, failure to observe such elementary precautions would have long been against the law. Here we are, 42 years later, and bounds checks are still not the default in some languages. Because performance, or something. And our computers are literally 1000x as fast as they were…
Removing bounds checks is a stark example of a premature optimization. You can remove bounds checks when you can prove that the index won't ever get out of bounds; this is possible in many cases, such as iteration with known bounds.
The norms there, from what I gather, are that you compile with runtime checks enabled unless you've used the SPARK prover tools to verify the absence of runtime errors, in which case you can safely disable runtime checks in your builds.
[0] https://docs.adacore.com/spark2014-docs/html/ug/en/usage_sce...
Earlier quoted context omitted.
Yet, really. The library author has certain knowledge of what the library is meant to achieve, where the compiler is obliged to guess according to whatever tea leaves it can find to descry. In particular, the library author knows that the container won't be changing size over the duration of the loop, something the compiler would have difficulty proving.
> The library author has certain knowledge of what the library is meant to achieve What's special about libraries? Every programmer has such knowledge, and every programmer writes buggy code.
Library authors know things about what their code is meant to be doing that compilers cannot deduce, so cannot act on. But the library author can. A library, according to how heavily it is used, benefits from more thorough testing than generic application code gets.
Earlier quoted context omitted.
This is exactly what they are designed to do and they do their job well, but they can't do it for free.
If even our performance-critical code moves to languages that always bounds-check, perhaps that will put pressure on ISA designers to add instructions for never-taken branches that just don't participate in any of the branch prediction logic. You'll always get a mispredict on failed bounds checks or final loop condition checks, but you'll avoid causing mispredictions elsewhere. Yes, some architectures (including x86)…
There are four versions of a conditional branch: to be predicted, almost always taken, almost never taken, and too random to waste a predictor on. Compilers nowadays have "likely" and "unlikely" intrinsics, but offer, yet, none for the last. I think x86 now ignores its "likelihood" branch prefix because back when introduced it was too often wrong; and now compilers don't emit it because it they know it is ignored.
The "too random to predict" would be good for sorting, where it could provide a 2x speedup. To get the effect today you need to use conditional-move instructions, which have become unfashionable. Getting your compiler to emit a cmov is tricky.
Intel added a special instruction (maybe in skylake?) to use for spinning on an atomic flag update, that just halts until the cache line being watched gets clobbered by a message from some other cache. Compilers don't emit it, unfortunately, even when spinning on what they know is an atomic flag.
There are zillions of such instructions that were good ideas but were never taken up by programmers who they were meant for.