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

121–130 of 195 posts

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

#121

Post by moloch-hai »

mjcohen wrote: post #85

Back in the 80's, I was programming in Fortran on a VAX 780. I had converted a complex eigenvalue-eigenvector routine from Algol to Fortran, and, after verifying that it worked, decided to see how much bounds checking added to the runtime. I figured since so much array referencing was done that this would be a worst case scenario. In that particular situation, it added about 30%. I decided that this was well worth it…

That is pretty silly. Your eigen library had in it everything it needed to ensure its own safety, so anything more just added slowness.

A check performed in a library, or a condition ensured in a library, is wholly as good as the same work done in the compiler. Compilers are not magic, they are just programs.

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

#122

Post by TylerE »

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.

Yeah, I didn’t find it compelling either.

If your conclusion is “no signal, just noise” boost the input until the signal becomes apparent. If that means writing such a massive loop that the program takes an hour to run, fine.

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

#123

Post by [deleted] »

Someone wrote: post #99
est31 wrote: post #69

Earlier quoted context omitted.

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

But Rust doesn’t have a spec ( https://doc.rust-lang.org/reference/ gets closest, but explicitly states “Rust compilers, including rustc, will perform optimizations. The reference does not specify what optimizations are allowed or disallowed” and “this book is not normative” ), so it doesn’t promise what kind of error you’ll get or when. I would think a Rust compiler could hoist the check outside of the loop at least…

[deleted]

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

#124

Post by titzer »

dataangel wrote: post #90
titzer wrote: post #65

For Virgil, there is a switch to turn off bounds checking, for the only reason to measure their cost. (It's not expected that anyone ever do this for production code). Bounds checks do not appear to slow down any program that matters (TM) by more than 2%. That's partly because so many loops automatically have bounds checks removed by analysis. But still. It's negligible.

A 2% efficiency difference is tens if not hundreds of millions of dollars for Google, Meta, etc. Globally it’s enormous.

And yet globally both of these companies spend 20% of CPU cycles on TLB misses. Should we turn off virtual memory protections and go back to raw physical memory (or something?)

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

#125

Post by est31 »

kibwen wrote: post #114
est31 wrote: post #69

Earlier quoted context omitted.

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.

Actually that made me think... you might be right. I just saw this opinion in earlier threads and repeated it but upon second inspection I either remembered it wrongly, or it is a wrong theory.

I think the issue is more the side effects than the panic message. I have tried making a side effect free loop like for i in 0..44 { v[i]; } but it compiled down to a "if array length is larger than limit X, then call panic_bounds_check". On the other hand, if you replace the v[i] with soon-stable black_box(v[i]), you see that the loop remains. It doesn't know what black_box is doing so it has to run the code. The optimizer is in this case very happy if you have a check before the loop.

https://rust.godbolt.org/z/5x46edeTb

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

#126

Post by gigatexal »

carl_dr wrote: post #46
gigatexal wrote: post #15

TL;DR - in the test bounds checking vs no checks showed no noticeable difference. Very good article though. Worth reading.

Not too long, did read : The benchmark went from 28.5ms to 32.9ms. That as a percentage is 15% and is huge, it’s not noise. The test is flawed in some way, the article is disappointing in that the author didn’t investigate further.

Right but it went up when turning off bounds checking. Which is crazy no?

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

#127

Post by moloch-hai »

Animats wrote: post #120

"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. Tha…

Each check burns a branch prediction slot, even if it always goes the same way. That may eject a branch predictor whose prediction matters.

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

#128

Post by nindalf »

est31 wrote: post #95
tialaramex wrote: post #94

Earlier quoted context omitted.

Yes, for example the relatively modern (didn't exist two years ago) implementation of IntoIterator for arrays themselves, gives you an iterator which doesn't use bounds checks since it is going to give exactly each of the things in the array once and it knows exactly how many of them there are.

It will still implement that with a loop over the array where there is a (bounds) check for the integer when it's being incremented (the i do have an advantage however, compilers can see their size so if you have an array (or array reference) and index it with a constant, then that bounds check will be eliminated. Also, array references are cheaper than slices because slices always contain the length.

> Arrays do have an advantage however, compilers can see their size

Wouldn’t vectors have the same advantage in Rust? If we’re iterating over a vector, it’s proveable at compile time that the length is not being modified during the iteration.

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

#129

Post by moloch-hai »

femto wrote: post #113
nine_k wrote: post #77

Earlier quoted context omitted.

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

To omit the check, the compiler would need to know that the loop range matches or subtends the array bound. That is commonly easy for built-in arrays, uncommonly for user-defined types. Most types are user-defined.

We trust the library author to get it right, despite (in Rust) wrapping accesses in "unsafe" or (in C++) not. Compilers are not particularly better at everything than library authors.

Post reply on HN