Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How much does Rust's bounds checking cost?

blog.readyset.io

Post reply on HN
Print view View original

181–190 of 195 posts

Re: How much does Rust's bounds checking cost?

#181

Post by moloch-hai »

nextaccountic wrote: post #148
moloch-hai wrote: post #119

Earlier quoted context omitted.

For real programs, you should demand that the compiler hoist such checks out of the loop, which may then be vectorized the usual way. If the compiler can't do that by itself, a library should do it. The real issue is whether the information about the true size of the memory region involved is available at the point where it is needed. This may come down to how good the language is at capturing desired semantics in a…

> For real programs, you should demand that the compiler hoist such checks out of the loop, which may then be vectorized the usual way. LLVM sometimes does this, but when it doesn't, you may insert asserts to guide the optimizer, as explained here https://news.ycombinator.com/item?id=33808853 I think this technique works in C and C++ too (if you use clang or gcc)

Sometimes a __builtin_assert(c) may help (which is not the same as the normal assertion, which won't). Other times, you need to make a private copy of a value that the compiler could not otherwise assume will not be clobbered.

Re: How much does Rust's bounds checking cost?

#182

Post by saagarjha »

KMag wrote: post #173
saagarjha wrote: post #163

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)…

How would this work? The branch isn’t “never” taken, it gets triggered when the bounds check fails. So someone needs to keep track of it…

Re: How much does Rust's bounds checking cost?

#183

Post by dllthomas »

saagarjha wrote: post #182
KMag wrote: post #173

Earlier quoted context omitted.

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)…

How would this work? The branch isn’t “never” taken, it gets triggered when the bounds check fails. So someone needs to keep track of it…

"Don't keep track of this branch for prediction stuff, instead always behave as if that prediction stuff says it won't be taken."

Re: How much does Rust's bounds checking cost?

#184

Post by emn13 »

ablob wrote: post #118
returningfory2 wrote: post #11

Earlier quoted context omitted.

I think the point of the article is the other way around: when starting from a language like C that doesn't have bound checking, moving to Rust will involve adding bounds checks and then an argument will be made that this will regress performance. So to test that hypothesis you start with the safe Rust code, and then remove the bounds check to emulate what the C code might be like. If, as in the article, you find tha…

Making the migration in order to find out if it was worth it appears to be quite an expensive test of an hypothesis.

What's the alternative, really?

Re: How much does Rust's bounds checking cost?

#185

Post by moloch-hai »

pjmlp wrote: post #151
moloch-hai wrote: post #119

Earlier quoted context omitted.

For real programs, you should demand that the compiler hoist such checks out of the loop, which may then be vectorized the usual way. If the compiler can't do that by itself, a library should do it. The real issue is whether the information about the true size of the memory region involved is available at the point where it is needed. This may come down to how good the language is at capturing desired semantics in a…

Unfortunely I only see Modern C++ on C++ conference talks and on my hobby projects. Most of the stuff I see at work, is quite far from this ideal reality, starting with Android's codebase, or the various ways C++ gets used in Microsoft frameworks.

There are choices for places to work. Maybe try another one?

Re: How much does Rust's bounds checking cost?

#186

Post by moloch-hai »

saagarjha wrote: post #182
KMag wrote: post #173

Earlier quoted context omitted.

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)…

How would this work? The branch isn’t “never” taken, it gets triggered when the bounds check fails. So someone needs to keep track of it…

If the instruction is tagged to keep it from claiming a branch prediction slot, it does not thereby evict some other branch from its prediction slot.

A prediction slot is where statistics on past behavior of a branch at a particular address accumulate. If no past behavior is needed to predict whether the branch will be taken, the predictor needs no statistics to decide, and statistics on some other branch instruction may accumulate in that slot instead.

Re: How much does Rust's bounds checking cost?

#187

Post by MaxBarraclough »

moloch-hai wrote: post #179
MaxBarraclough wrote: post #177

Earlier quoted context omitted.

> 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.

What's special about compilers, then? Compilers are code, and therefore, as you say, buggy. 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.

You're right that compilers tend to have bugs, but in practice, compiler bugs are rarely the cause of software issues. The same cannot be said of libraries. Major SSL/TLS libraries for instance tend to be written in C, and all of them have had memory-safety bugs.

> 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.

I don't see your point here.

> A library, according to how heavily it is used, benefits from more thorough testing than generic application code gets

This doesn't generalise. There's plenty of very widely used application-specific code, and there's plenty of little used library code. Also, widespread use does not imply a high level of scrutiny, even if we're talking only about Free and Open Source software.

Anyway, that's all a sidetrack. The benefits of memory-safe languages aren't up for debate, even for well-scrutinised codebases. We continue to suffer a stream of serious security vulnerabilities arising from memory-safety issues in code written in unsafe languages. The go-to example is Chromium, where 70% of serious security issues are due to memory safety. [0]

[0] https://www.chromium.org/Home/chromium-security/memory-safet...

Re: How much does Rust's bounds checking cost?

#188

Post by int_19h »

pjmlp wrote: post #175
int_19h wrote: post #174

Earlier quoted context omitted.

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…

Oh, so much for VC++ folks being security conscious. 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.

Array bounds checking is plenty fast, it's the iterators specifically that are the problem. Unless your code is heavy on those, you wouldn't notice.

(OTOH for cases where you would notice, given the perf penalty, you might as well just write it in C# then.)

Re: How much does Rust's bounds checking cost?

#189

Post by KMag »

moloch-hai wrote: post #186
saagarjha wrote: post #182

Earlier quoted context omitted.

How would this work? The branch isn’t “never” taken, it gets triggered when the bounds check fails. So someone needs to keep track of it…

If the instruction is tagged to keep it from claiming a branch prediction slot, it does not thereby evict some other branch from its prediction slot. A prediction slot is where statistics on past behavior of a branch at a particular address accumulate. If no past behavior is needed to predict whether the branch will be taken, the predictor needs no statistics to decide, and statistics on some other branch instruction…

I'm far from an expert here, but don't most modern branch predictors actually keep a shift register of the last few conditional branches, hash that branch history with the instruction's address, and use that as the index into the predictor's state table, and assume hash collisions won't happen? (Hash collisions only have a material impact if two conditional branches in the same hot code path collide, which is much more rare than general hash collisions.)

If my understanding is correct, slots aren't really "taken up", but rather avoiding the branch predictor reduces the probability of hash collisions for other branches.

I also have a question for the crowd: for indirect branch target prediction, are the BTB slots actually tagged with the address? If you have BTB miss, do you pre-emptively stall the pipeline? It's more power-efficient to do so, but maybe it's better to avoid tags and tag-checking and spend that transistor budget on more BTB slots, and just go ahead and mispredict if you get a collision on BTB slots.

Re: How much does Rust's bounds checking cost?

#190

Post by moloch-hai »

KMag wrote: post #189
moloch-hai wrote: post #186

Earlier quoted context omitted.

If the instruction is tagged to keep it from claiming a branch prediction slot, it does not thereby evict some other branch from its prediction slot. A prediction slot is where statistics on past behavior of a branch at a particular address accumulate. If no past behavior is needed to predict whether the branch will be taken, the predictor needs no statistics to decide, and statistics on some other branch instruction…

I'm far from an expert here, but don't most modern branch predictors actually keep a shift register of the last few conditional branches, hash that branch history with the instruction's address, and use that as the index into the predictor's state table, and assume hash collisions won't happen? (Hash collisions only have a material impact if two conditional branches in the same hot code path collide, which is much mo…

Details of actual branch predictors are proprietary, so we must speculate.

You don't stall on branches you have no history of, but apply heuristics that don't depend on history. E.g., backward branches are usually taken, forward branches less so. I think newer chips can try both alternatives, to some degree, although this cannot be carried far as it blows up exponentially.

Post reply on HN