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

41–50 of 195 posts

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

#41

Post by dathinab »

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 optimized for that kind of checks at they appear in a lot of languages (e.g. Java).

Then in many cases the compiler can eliminate the checks partially.

For example any many kinds of for-each element iterations the compiler can infer that the result of the conditionally loop continuation check implies the bounds check. Combine that with loop unrolling which can reduce the number of continuation checks and you might end up with even less.

Also bounds checks tend to be an emergency guard, so you tend to sometimes do checks yourself before indexing and the compiler can often use that to eliminate the bounds check.

And even if you ignore all optimizations it's (assuming in bounds) "just" at most one int/pointer cmp (cheap) followed by a conditional branch which doesn't branch (cheap).

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

#43

Post by dathinab »

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…

> If you always predict the in bounds path, the check is almost free.

Note that you often only branch in the "bad" case, which means even on systems without branch prediction it tends to be not very expensive, and compilers can also eliminate a lot of bounds checks.

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

#44

Post by vore »

apendleton wrote: post #31
tylerhou wrote: post #25

Earlier quoted context omitted.

Safe iterators have to have bounds checks for dynamically sized arrays; otherwise, how you prevent iterators from walking past the end?

In Rust at least, once you instantiate the iterator, the array it's iterating over can't be mutated until the iterator is dropped, and that can be statically guaranteed at compile time. So you don't need to bounds-check at every access; you can decide at the outset how many iterations there are going to be, and doing that number of iterations will be known not to walk past the end.

I don't think that's always possible in practice: consider Vec, whose size is only known at runtime. A Vec's iterator can only do runtime bounds checking to avoid walking past the end.

That said, this is unavoidable in C/C++ too.

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

#45

Post by Jach »

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 designing a new language, why don't we just implement ALGOL60?" We all instantly agreed--in retrospect, a very lucky decision for me. But we knew we did not have the skill or experience at that time to implement the whole language, so I was commissioned to design a modest subset. In that design I adopted certain basic principles which I believe to be as valid today as they were then.

"(1) The first principle was security: The principle that every syntactically incorrect program should be rejected by the compiler and that every syntactically correct program should give a result or an error message that was predictable and comprehensible in terms of the source language program itself. Thus no core dumps should ever be necessary. It was logically impossible for any source language program to cause the computer to run wild, either at compile time or at run time. A consequence of this principle is that every occurrence of every subscript of every subscripted variable was on every occasion checked at run time against both the upper and the lower declared bounds of the array. Many years later we asked our customers whether they wished us to provide an option to switch off these checks in the interests of efficiency on production runs. Unanimously, they urged us not to -- they already knew how frequently subscript errors occur on production runs where failure to detect them could be disastrous. 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."

-Tony Hoare, 1980 Turing Award Lecture (https://www.cs.fsu.edu/~engelen/courses/COP4610/hoare.pdf)

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

#46

Post by carl_dr »

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.

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

#47

Post by dathinab »

moloch-hai wrote: post #40

The instructions generated make a big difference. Modern processor specifications commonly quote how many instructions of a type can be "retired" in a cycle. They can retire lots of conditional branches at once, or branches and other ops, when the branches are not taken . So it matters whether the code generator produces dead branches that can be retired cheaply. Probably, optimizers take this into account for built-…

In rust there is `#[cold]` for functions as well as (nightly only) `likely(cond)`/`unlikely(cond)` and some tricks you can have something similar in stable rust.

Also branch paths which lead guaranteed to an panic tend to be treated as "unlikely" but not sure how far this is guaranteed.

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

#48

Post by est31 »

tayistay wrote: post #21

What if a compiler were to only allow an array access when it can prove that it's in bounds? Wherever it can't you'd have to wrap the array access in an if, or otherwise refactor your code to help the compiler. Then you'd have no panicking at least and more predictable performance.

Rust has a tool for that, it's iterators. It is only limited however.

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

#49

Post by bjourne »

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 emit code like the following:

    1. assert that 0
Post reply on HN