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

111–120 of 195 posts

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

#111

Post by CrendKing »

bjourne wrote: post #49

The reason performance decreased when he removed bounds checking is because asserting bounds is very useful to a compiler. Essentially, the compiler emits code like this: 1. if (x >= 0) && (x The compiler deduces that at line 5 0 1. get element from array index x 2. do more stuff So the compiler doesn't know anything about x, which is bad. The solution which apparently is not implemented in Rust (or LLVM, idk) is to…

If what you said is true, then this is not Rust specific, and we should observe performance improvement in all languages, should they introduce bounds-checking during code emission. Is there compiler flag that we can turn on bounds-checking in GCC for C++ programs? Is there research to compare performance before and after that flag?

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

#112

Post by ridiculous_fish »

oconnor663 wrote: post #97
brundolf wrote: post #84

One thing that I assume reduces this problem even further is the prevalent use of iterators in Rust. I almost never index an array or vector directly, which means it's impossible for me to use an out of bounds index, and I'd be really surprised if rustc and/or LLVM don't somehow take advantage of that fact (maybe just through unchecked indexing in the standard library's iterator functions)

I think LLVM is smart enough to optimize regular `for i in 0..stuff.len()` loops into the same assembly as `for i in &stuff` loops in almost all cases. I imagine this sort of "we can tell that i is always less than len" optimization is a big contributor to the low cost of bounds checks. In some large portion of cases where they're not needed, the optimizer can already see that.

IME loops with induction variables (integer indexes) often produces better codegen than with iterators. Compare the these two Rust functions for inverting bits: https://rust.godbolt.org/z/cE4vPdbdY

This got improved in Rust 1.65 just this month, but the point stands.

edit: ARM64 compilation is even sillier. https://rust.godbolt.org/z/PEsbeGxWP

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

#113

Post by femto »

nine_k wrote: post #77
titzer wrote: post #62

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.

Isn't this a job for the compiler? The default would be to have boundary checking, but if the compiler can prove that the index is always in range it can drop the boundary check. From the user's perspective, the boundary check is always there. Most vector operations would have provable boundaries.

Edit:

Based on the benchmark code linked to in dahfizz 's comment, it seems that Rust does the above for vectors, but there are situations where the bounds can't be proved, so boundary checking can't be removed. How common is this case in practice?

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

#114

Post by kibwen »

est31 wrote: post #69
mastax wrote: post #66

One technique is to add asserts before a block of code to hoist the checks out. The compiler is usually smart enough to know which conditions have already been checked. Here's a simple example: https://rust.godbolt.org/z/GPMcYd371 This can make a big difference if you can hoist bounds checks out of an inner loop. You get the performance without adding any unsafe {}.

Yeah this is because the error message printed contains the location of the error as well as the attempted index. Thus, there are differences between the bounds failures and the optimizer can't hoist the check out (plus probably some concerns due to side effects of opaque functions).

Hm? The existence of panic messages doesn't preclude the optimizer from hoisting a bounds check out of the loop.

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

#115

Post by dahfizz »

carl_dr wrote: post #61
dale_glass wrote: post #51

Earlier quoted context omitted.

MySQL is a huge amount of code doing a variety of things in each query -- networking, parsing, IO, locking, etc. Each of those can easily have significant and hard to predict latencies. Benchmarking that needs special care, and planning for whatever it is you want to measure. A million trivial queries and a dozen very heavy queries are going to do significantly different things, and have different tradeoffs and perfo…

The benchmark was specifically testing the hot path of a cached query in their MySQL caching proxy. MySQL wasn’t involved at all. I agree completely that benchmarks need care, hence my point that the article is disappointing. The author missed the chance to investigate why removing bounds checks seemed to regress performance by 15%, and instead wrote it off as “close enough.” It would have been really interesting to…

"just a cached query" isn't like it's just a hash lookup. You're still doing IO, network protocol decoding, multithreaded synchronization, etc etc. It's certainly not a CPU bound program.

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

#116

Post by kibwen »

bjourne wrote: post #49

The reason performance decreased when he removed bounds checking is because asserting bounds is very useful to a compiler. Essentially, the compiler emits code like this: 1. if (x >= 0) && (x The compiler deduces that at line 5 0 1. get element from array index x 2. do more stuff So the compiler doesn't know anything about x, which is bad. The solution which apparently is not implemented in Rust (or LLVM, idk) is to…

> The solution which apparently is not implemented in Rust (or LLVM, idk) is to emit code like the following:

The solution to what? You appear to be suggesting that compilers should insert bounds checks even when the programmer doesn't ask for them, which, sure, I'm down for that, but the whole point of this discussion is that the bounds checking that currently gets done has a negligible cost in practice.

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

#117

Post by ridiculous_fish »

dathinab wrote: post #41

Anything between nothing and one most likely correct branch predicted to _not_ jump "branch iff int/pointer > int/pointer". This kind of bounds check are normally not ever violated (in well formed code) so branch prediction predicts them correctly nearly always. It also is (normally) just jumping in the bad case, which means with a correct branch predictions thy can be really cheap. And then cpu "magic" tends to be o…

Branches add control flow which can inhibit other optimizations, such as vectorization. Compare the codegen of these two functions to double the first 64 elements in a u8 slice: https://rust.godbolt.org/z/hccWGv889

The unchecked version is fully unrolled and vectorized using multiple registers. The checked version must use a loop.

Part of what's going on here is that panics are "recoverable." If the out-of-bounds write occurs at index 61, this will panic, but the writes to lower indexes must have gone through. This means the panic cannot be hoisted out of the loop.

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

#118

Post by ablob »

returningfory2 wrote: post #11
killingtime74 wrote: post #5

Can someone smarter than me enlighten me when you would consider disabling bounds checking for performance? In ways the compiler is not already doing so? The article starts with a bug that would have been prevented by bounds checking. It's like talking about how much faster a car would go if it didn't have to carry the extra weight of brakes.

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.

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

#119

Post by moloch-hai »

dataangel wrote: post #78
Jach wrote: post #45

Always amuses me that it's current year and people think about turning off checks, even when they're pretty much free in modern* (since 1993 Pentium, which got like 80% accuracy with its primitive branch prediction?) CPUs... "Around Easter 1961, a course on ALGOL 60 was offered … After the ALGOL course in Brighton, Roger Cook was driving me and my colleagues back to London when he suddenly asked, "Instead of designin…

They’re nowhere near free. Branch prediction table has finite entries, instruction cache has finite size, autovectorizing is broken by bounds checks, inlining (the most important optimization) doesn’t trigger if functions are too big because of the added bounds checking code, etc. This is just not great benchmarking — no effort to control for noise.

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 library. Rust still has a long way to go to catch up with C++ on this axis, and C++ is not waiting around.

Rust claims responsibility for enforcing safety in the compiler, with libraries using "unsafe" to delegate some of that to themselves. Users then trust the compiler and libraries to get it right. In C++, the compiler provides base semantics while libraries take up the whole responsibility for safety. Users can trust libraries similarly as in Rust, to similar effect.

Modern C++ code typically does no visible operations with pointers at all, and most often does not index directly in arrays, preferring range notation, as in Rust, achieving correctness by construction. A correct program is implicitly a safe program.

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

#120

Post by Animats »

"It seems like at least for this kind of large-scale, complex application, the cost of pervasive runtime bounds checking is negligible."

Right. The myth that bounds checking is expensive may have come from some terrible compilers in the early days. Berkeley Pascal was a notable example. Each bounds check was a subroutine call.

The common cases for bounds checks are:

- It's in an inner loop iterating over arrays. That's the case where the highest percentage of the time goes into the bounds check. It's also the case likely to be optimized out. This is the case people worry about.

- It's in code that doesn't do a lot of subscript operations. So it doesn't matter.

- It's in non-optimizable code that does a lot of subscript operations. That's unusual, but it does come up. An modern case might be Unreal Engine's Nanite meshes, which have lots of small offsets within the data stream. On the other hand, if you don't check that stuff, it's a great attack vector.

Post reply on HN