How much does Rust's bounds checking cost? • Hacker News Board

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

#161

Post by tialaramex » Thu, Dec 01, 2022, 8:52 AM UTC

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…

Rust doesn't have "volatile variables" that's a weird C thing which then ends up in C++ and related languages because nobody wants to touch this mess.

The purpose of "volatile" is to mark MMIO so that the memory reads and writes don't get optimised out because they actually perform I/O. Everywhere you see volatile abused to do something else (yes including Unix signal handlers) that's because C has a hammer and so now everything looks like a nail to C programmers. In a few cases this abuse is guaranteed to work (and results in a lot of heavy lifting elsewhere to achieve that) in most cases it's just luck.

Rust has generic intrinsics which perform memory read/write that won't get optimised out, which is the actual thing C needed when volatile was invented.

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

#162

Post by pjmlp » Thu, Dec 01, 2022, 9:18 AM UTC

flohofwoe wrote: post #160

pjmlp wrote: post #155

Earlier quoted context omitted.

My experience in some gamedev and embedded development circles is that there are several that will religiously argue against it, without ever having run a profiler to validate their perception of the world.

FWIW, I'm also coming out of the game dev world, and we shipped all our games with (custom) asserts enabled (which includes bounds checking in containers). I did regular performance tests and the enabled asserts were never a big enough performance hit to justify removing them (around 1..3% across an entire frame), the ability to get 'clean' crash reports from out in the wild, triggered by asserts instead of random se…

That is what I have been doing since forever, in C and C++ land.

In C++, I kind of always strived to use the higher level abstractions, with support for bounds checking. First the compiler provided frameworks from pre-C++98, then configuring builds so that STL types also bounds check in release.

In C is harder, but a mix of asserts, using TU as if they were modules exposing ADTs (Modula-2/Pascal units style), can also be a way to help mitigate issues. Kudos to the Code Complete book for some of the ideas[0].

However, trying to sell this experience always feels like quixotic in those environments, so kudos for actually doing it.

[0] - "Code Complete. A Practical Handbook of Software Construction"

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

#163

Post by saagarjha » Thu, Dec 01, 2022, 9:20 AM UTC

imtringued wrote: post #158

moloch-hai wrote: post #127

Earlier quoted context omitted.

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

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.

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

#164

Post by camkego » Thu, Dec 01, 2022, 10:29 AM UTC

dahfizz wrote: post #103

dataangel wrote: post #78

Earlier quoted context omitted.

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.

> autovectorizing is broken by bounds checks This is the big one. You pay a 50% penalty for actual CPU bound, iteration heavy code with bounds checking enabled. https://github.com/matklad/bounds-check-cost

This should be the article.

Running this with 1.65 on an Intel 12400 gets a nearly 4x speedup when bounds checking is not needed. Just wow.

Bounds checking avoidance is important when it becomes a significant chunk of your hot-path.

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

#165

Post by grogers » Thu, Dec 01, 2022, 12:15 PM UTC

varajelle wrote: post #150

xyzzyz wrote: post #146

Earlier quoted context omitted.

Like what, for example? To the contrary, I think that, other than constness, C++ has rather few facilities to communicate semantic invariants to the compiler.

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.

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

#166

Post by moloch-hai » Thu, Dec 01, 2022, 1:31 PM UTC

titzer wrote: post #135

moloch-hai wrote: post #129

Earlier quoted context omitted.

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.

> would need to know that the loop range matches or subtends the array bound Some compilers have pretty sophisticated analyses aimed at just that: determining affine relations to statically bound indexed accesses. Failing that, some compilers will resort to loop versioning, generating two versions of the loop and then partitioning the iteration space into the definitely-in-bounds range from possibly-out-of-bounds ran…

Libraries can do this too, in many cases more reliably.

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

#167

Post by zozbot234 » Thu, Dec 01, 2022, 2:49 PM UTC

dahfizz wrote: post #103

dataangel wrote: post #78

Earlier quoted context omitted.

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.

> autovectorizing is broken by bounds checks This is the big one. You pay a 50% penalty for actual CPU bound, iteration heavy code with bounds checking enabled. https://github.com/matklad/bounds-check-cost

The proper way of addressing that is to manually hoist bound checks out of "hot" loops. Not just remove them altogether.

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

#168

Post by pjmlp » Thu, Dec 01, 2022, 3:14 PM UTC

int_19h wrote: post #105

constantcrying wrote: post #32

I imagine the reason bounds check are cheap is because of the branch predictor. If you always predict the in bounds path, the check is almost free. You also do not really care about flushing the pipe on an out of bounds index, since very likely normal operations can not go on and you move over to handling/reporting the error, which likely has no need for significant throughput. Also I would just like to note that saf…

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.

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

#169

Post by titzer » Thu, Dec 01, 2022, 3:24 PM UTC

moloch-hai wrote: post #166

titzer wrote: post #135

Earlier quoted context omitted.

> would need to know that the loop range matches or subtends the array bound Some compilers have pretty sophisticated analyses aimed at just that: determining affine relations to statically bound indexed accesses. Failing that, some compilers will resort to loop versioning, generating two versions of the loop and then partitioning the iteration space into the definitely-in-bounds range from possibly-out-of-bounds ran…

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.

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

#170

Post by est31 » Thu, Dec 01, 2022, 3:31 PM UTC

clarkmoody wrote: post #139

ReactiveJelly wrote: post #134

Earlier quoted context omitted.

I think they mean a one-off constant index should never check. let arr = [1, 2, 3, 4]; // Will not compile a bound check let x = arr [3]; let v = vec! [1, 2, 3, 4]; // Imagine other code separates these two lines // Might compile a bound check let x = v [3];

In this case, v is not declared mutable, so you could ignore. In fact, the compiler will probably end up assigning x = 4 at compile time.

A better comparison is:

    fn foo_arr(v: &[u8; 5]) -> u8 {
        v[2]
    }

    fn foo_vec(v: &Vec) -> u8 {
        v[2]
    }

In the foo_arr case, the index lookup can be optimized out. In the foo_vec case, it can't be, because theoretically you might pass something with only 2 elements or less to foo_vec, and access to the third element will fail.

Same goes for e.g. the slice::windows vs slice::array_windows functions. In windows, you get a slice in the closure, and while the size is guaranteed by the implementation, without there being inlining the optimizer doesn't know about this guarantee. With array_windows, this size guarantee is communicated.