20 ms·

How much does Rust's bounds checking cost?

• tragomaskhalos 4y ago
  I would expect an iterator into a slice to not incur any bounds checking, as the compiler can deduce the end pointer one time as start + size. So idiomatic looping should be maximally efficient you'd hope.
  • lmkg 4y ago
    The compiler shouldn't have to deduce anything, an Iterator shouldn't have a bounds check to begin with. It ought to be using unsafe operations under the hood, because it can guarantee they will only be called with valid arguments.
    • tylerhou 4y ago
      Safe iterators have to have bounds checks for dynamically sized arrays; otherwise, how you prevent iterators from walking past the end?
      • apendleton 4y ago
        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.
        • vore 4y ago
          I don't think that's always possible in practice: consider Vec<T>, whose size is only known at runtime. A Vec<T>'s iterator can only do runtime bounds checking to avoid walking past the end. That said, this is unavoidable in C/C++ too.
          • apendleton 4y ago
            I think we're suffering from some fuzziness about what bounds checks we're referring to. Even in your example, you only need to check the size of the Vec<T> when you instantiate the iterator, not each time the iterator accesses an element, because at the time the iterator over the Vec<T>'s contents is instantiated, the Vec<T>'s size is known, and it can't change over the life of the iterator (because mutation is disallowed when there's an outstanding borrow). With a regular for-loop: for i in 0..v.len() { println!("{:?}", v[i]); } you check the length at the top (the `v.len()`) and also for each `v[i]`. The first is unavoidable, but the second can be skipped when using an iterator instead, because it can be statically guaranteed that, even if you don't know at compile time what concretely the length is, whatever it ends up being, the index will never exceed it. Rust specifically differs from C++ in this respect, because nothing in that language prevents the underlying vector's length from changing while the iterator exists, so without per-access bounds checks it's still possible for an iterator to walk past the end.
            • tylerhou 4y ago
              When I read "iterator" I think of an object that points into the vector and can be advanced. For Rust's vector, that is std::slice::Iter (https://doc.rust-lang.org/std/slice/struct.Iter.html https://doc.rust-lang.org/std/slice/struct.Iter.html). When you advance an iterator, you must do a bounds check if the vector is dynamically sized; otherwise, you don't know when to stop. I.e., if I have let mut it = vec.iter(); println!(it.next()); println!(it.next()); println!(it.next()); This needs to do bounds checking on each call to next() to either return Some(a) or None (assuming the length of vec is unknown at compile time). (hhttps://doc.rust-lang.org/beta/src/core/slice/iter/macros.rs.html#133-152 https://doc.rust-lang.org/beta/src/core/slice/iter/macros.rs....) You are right that theoretically a range-based for loop that uses iterators does not need to do bounds checking because a compiler can infer the invariant that the iterator is always valid. In practice I don't know enough about LLVM or rustc to know whether this optimization is actually happening.
              • dwattttt 4y ago
                The Rust docs for the 'for' keyword do say for loops are implemented as sugar for iterator loops. https://doc.rust-lang.org/std/keyword.for.html https://doc.rust-lang.org/std/keyword.for.html Relevant part: > for-in-loops, or to be more precise, iterator loops, are a simple syntactic sugar over a common practice within Rust, which is to loop over anything that implements IntoIterator until the iterator returned by .into_iter() returns None (or the loop body uses break). (The other uses of the 'for' keyword it refers to are unrelated to loops)
    • meindnoch 4y ago
      Calling ‘next’ on an iterator involves a bounds check.
• bugfix-66 4y ago
  Similarly, you can turn off bounds-checking in Go like this: go build -gcflags=-B and see if it helps. Generally the assembly looks better, but it doesn't really run faster on a modern chip. Do your own test, and keep the results in mind next time somebody on Hacker News dismisses Go because of the "overwhelming cost of bounds checking".
  • masklinn 4y ago
    > next time somebody on Hacker News dismisses Go because of the "overwhelming cost of bounds checking". That’s certainly one criticism I don’t remember ever seeing.
    • viraptor 4y ago
      There's a few examples like this https://news.ycombinator.com/item?id=32256038 https://news.ycombinator.com/item?id=32256038 if you search comments for "go bounds checking"
  • pjmlp 4y ago
    It appears that the flag keeps being undocumented, though. https://pkg.go.dev/cmd/compile https://pkg.go.dev/cmd/compile
• rfoo 4y ago
  A consistent 5 ms difference in micro-benchmarks is definitely not "measurement noise". Noise averages out way before accumulating to 5ms. There must be a reason and it mostly likely relates to the change. So you can confidently say that removing bounds checking (at least with how you did it) is a regression. ... that being said, I'd argue that the most beneficial memory-safety feature of Rust is about temporal things (i.e. prevents UAF etc) instead of spatial ones.
  • spullara 4y ago
    A benchmarking harness without error bars?
  • whatshisface 4y ago
    Well, there is both random and systemic error in any experiment, and if 5ms is small relative to anything you'd expect (or there is some other reason to discount it) then it might be related to a problem in the benchmarking setup that's too small to be worth resolving. Any test is good to within some level of accuracy and they don't always average out to infinitely good if you rerun them enough times.
    • joosters 4y ago
      The 5ms isn't the key number. It's 5ms extra over a 28ms baseline, that's about 18% difference. If your noise threshold is 18%, then I think you have to accept that the benchmark probably isn't any good for this stated task.
      • viraptor 4y ago
        https://github.com/bheisler/criterion.rs https://github.com/bheisler/criterion.rs is good for tests like that. It will give you much more than a single number and handle things like outliers. This makes identifying noisy tests simpler.
        • glittershark 4y ago
• killingtime74 4y ago
  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.
  • masklinn 4y ago
    > It's like talking about how much faster a car would go if it didn't have to carry the extra weight of brakes. And there’s folks who do exactly that.
  • returningfory2 4y ago
    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 that performance is not really affected, then it makes a C-to-Rust migration argument more compelling.
    • ablob 4y ago
      Making the migration in order to find out if it was worth it appears to be quite an expensive test of an hypothesis.
      • emn13 4y ago
        What's the alternative, really?
  • pitaj 4y ago
    Sometimes the programmer can prove that bounds checks are unnecessary in a certain situation, but the compiler can't prove that itself, and the programmer can't communicate that proof to the compiler. Bounds checks can result in lost performance in some cases (very tight loops), so unsafe facilities exist as a workaround (like `get_unchecked`).
• pitaj 4y ago
  Very interesting. One thing that I'm curious about is adding the bounds-check assertion to `get_unchecked` and seeing if that has a significant effect.
  • masklinn 4y ago
    Happens from time to time, I’ve seen folks going around libraries looking for “perf unsafe” and benching if removing the unsafe actually lowered performances. One issue on that front is a question of reliability / consistency: on a small benchmark chances are the compiler will always trigger to its full potential because there’s relatively little code, codegen could be dodgier in a context where code is more complicated or larger. Then again the impact of the bounds check would also likely be lower on the non-trivial code (on the other hand there are also threshold effects, like branch predictor slots, icache sizes, …).
• gigatexal 4y ago
  TL;DR - in the test bounds checking vs no checks showed no noticeable difference. Very good article though. Worth reading.
  • carl_dr 4y ago
    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.
    • dale_glass 4y ago
      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 performance characteristics.
      • carl_dr 4y ago
        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 find out why, even if it did end up being measurement noise.
        • dahfizz 4y ago
          "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.
    • 4y ago
• jackmott42 4y ago
  Occasionally small changes like this will result in bigger than expected performance improvements. An example of this happened once with C#, when two very tiny changes, each of which were borderline measurable, combined they made a big difference. IIRC it was in the List.Add method, a very commonly used function in the C# core libs. First one programmer refactored it to very slightly reduce how many instructions were output when compiled. Then a second programmer working on the jit compiler optimizations which also affected this Add method making it a little smaller as well. Alone, each change was hard to even measure, but seemed like they should be a net win at least in theory. Combined, the two changes made the Add method small enough to be an in-lining candidate! Which meant in real programs sometimes very measurable performance improvements result. As others in this post have noted, a removed bounds check might also unblock vectorization optimizations in a few cases. One might be able to construct a test case where removing the check speeds thing up by a factor of 16!
• tayistay 4y ago
  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.
  • jackmott 4y ago
  • tylerhou 4y ago
    With bounds checking by default, even if a compiler can't statically prove that an index is in bounds, if the index in practice is always in bounds, the compiler inlines the check/branch into the calling function, and you're not starved of branch prediction resources, the check will be "free" because the branch will always be predicted as taken.
  • constantcrying 4y ago
    >What if a compiler were to only allow an array access when it can prove that it's in bounds? Even very good static analysis tools have a hard time doing this. In a language like C++ this would effectively mean that very few index operations can be done naively and compile times are significantly increased. Performance is likely reduced as well over the trivial alternative of using a safe array.
  • glittershark 4y ago
    there's a cheeky link to idris's vector type in the second paragraph: https://www.idris-lang.org/docs/idris2/current/base_docs/docs/Data.Vect.html https://www.idris-lang.org/docs/idris2/current/base_docs/doc... which accomplishes just that
  • est31 4y ago
    Rust has a tool for that, it's iterators. It is only limited however.
    • dathinab 4y ago
• lowbloodsugar 4y ago
  I am a Rust fan, but 10% degradation in performance (29ms to 33ms) is not "a pretty small change" nor "within noise threshold". If the accuracy of the tests are +/- 10% then that needs to be proven and then fixed. I didn't see any evidence in the article that there is, in fact, a 10% error, and it looks like there is a genuine 10% drop in performance.
  • glittershark 4y ago
    a 10% drop in performance with bounds checks removed, mind you - so if anything the bounds checks are improving performance.
    • pantalaimon 4y ago
      The more likely explanation is that the test is bunk. Or maybe the unsafe access acts like volatile in C and disables any optimization/reordering because the compiler thinks it’s accessing a register.
      • Jweb_Guru 4y ago
        Unsafe accesses do not act that way, they compile to exactly the same code as array accesses in C. The tests aren't bunk. There are a variety of reasons why the assertions generated by array index checks can be useful for LLVM, and there is also a fair amount of noise in any end to end test like this. The main point is that it clearly isn't a primary bottleneck (which should be pretty obvious in a test that takes 30 ms and performs under 2000 bounds checks).
  • hra5th 4y ago
    To be clear, removing the bounds checks led to the observed performance degradation. Your statement beginning with "I am a Rust fan, but..." suggests that you might have interpreted it as the other way around
    • lowbloodsugar 4y ago
• constantcrying 4y ago
  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 safe arrays aren't a unique rust feature. Even writing your own in C++ is not hard.
  • jackmott42 4y ago
    Yep, unless your code is wrong, the bounds check will always be predictable. Which makes it free in a sense. But sometimes it will block other optimizations, and it takes up space in the caches.
  • pantalaimon 4y ago
    That would be bad on Embedded where MCUs usually don’t do any branch prediction.
  • dathinab 4y ago
    > 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.
  • int_19h 4y ago
    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.
    • pjmlp 4y ago
      On VC++ it is quite easy to do so, https://learn.microsoft.com/en-us/cpp/standard-library/checked-iterators?view=msvc-170 https://learn.microsoft.com/en-us/cpp/standard-library/check... The hard part is changing the mentality from whoever sits at the keyboard.
• deleted 4y ago
  [deleted]
• moloch-hai 4y ago
  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 operations, but they know less about the happy path in libraries. This is a motivation for the "likely" annotations compilers support. The likely path can then be made the one where the branch is not taken. Code on the unhappy path can be stuck off in some other cache line, or even another MMU page, never fetched in normal operation. The cost seen here is likely from something else, though. Keeping array size in a register costs register pressure, or comparing to a stack word uses up cache bandwidth. Doing the comparison burns an ALU unit, and propagating the result to a branch instruction via the status register constrains instruction order. Even those might not be at fault, because they might not add any extra cycles. Modern processors spend most of their time waiting for words from memory: just a few cycles for L1 cache, many more for L2 or L3, an eternity for actual RAM. They can get a fair bit done when everything fits in registers and L1 cache, and loops fit in the micro-op cache. Blow any of those, and performance goes to hell. So depending how close your code is to such an edge, extra operations might have zero effect, or might tank you. Results of measurements don't generalize. Change something that looks like it ought to make no difference, and your performance goes up or down by 25%. In that sense, the 10% seen here is noise just because it is hard to know what might earn or cost you 10%.
  • dathinab 4y ago
    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.
• dathinab 4y ago
  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).
  • ridiculous_fish 4y ago
    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 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.
• api 4y ago
  It's a lot cheaper than having an RCE and being completely pwned.
• Jach 4y ago
  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 https://www.cs.fsu.edu/~engelen/courses/COP4610/hoare.pdf)
  • titzer 4y ago
    > 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 in 1980. So instead of paying 2% in bounds checks and getting a merge 980x faster, we get 2-3x more CVEs, costing the economy billions upon billions of dollars a year.
• bjourne 4y ago
  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 < arr_len(arr)) 2. get element from array index x 3. else 4. throw exception 5. do more stuff The compiler deduces that at line 5 0 <= x < arr_len(arr). From that it can deduce that abs(x) is a no op, that 2*x won't overflow (cause arrays can only have 2^32 elements), etc. Without bounds checking the compiler emits: 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 <= x < arr_len(arr) 2. get element from array index x 3. do more stuff
  • vore 4y ago
    I'm not sure I follow: where is abs(x)?
    • layer8 4y ago
      It’s an example of what could occur within “do more stuff”. The mentioned 2*x is another example.
  • est31 4y ago
    Interesting observation. So one should instead do the comparison with something like: 1. if (x >= 0) && (x < arr_len(arr)) 2. get element from array index x 3. else 4. core::hint::unreachable_unchecked 5. do more stuff Where unreachable_unchecked transmits precisely such information to the optimizer: https://doc.rust-lang.org/stable/std/hint/fn.unreachable_unchecked.html https://doc.rust-lang.org/stable/std/hint/fn.unreachable_unc...
  • CrendKing 4y ago
    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?
• deleted 4y ago
  [deleted]
• tester756 4y ago
  I've been shocked when I've heard C programmers being actually concerned about performance penalty of checks like, why bother? CPUs in next 2 years will win that performance anyway and your software will be safer
  • humanrebar 4y ago
    All of the CPUs? C runs a lot of places.
    • tester756 4y ago
      If you need perf, then consider better algorithms, better data structures, multi-threading, branchless programming (except safety), data-oriented design and then elimination of checks, not first.
      • deleted 4y ago
        [deleted]
  • Gigachad 4y ago
    Most online debates are filled with illogical opinions on theoretical issues. You get people on this site complaining that they have to spend money on a catalytic converter because it's not required for the car to run and only prevents other people from getting cancer.
  • flohofwoe 4y ago
    For proper bounds checking in C you first need to communicate the "bounds" to be "checked" to all the places where it matters, just a pointer isn't enough. Unfortunately many old-school C APIs (including the stdlib) often don't pass pointer-size pairs around, but just pointers (and IMHO the biggest problem in the C world is not so much the language, but outdated APIs like the C stdlib or POSIX which have mostly been designed in the K&R era and which basically "encourage" unsafe usage). Other then that, I doubt that any reasonably pragmatic and experienced C programmer will ever argue against runtime bounds checking from a performance point of view. Even in hot loops one can usually move the bounds checking to a place outside the loop.
• piwi 4y ago
  The article mentions measurement noise several times without addressing the uncertainty. It would help to add statistical tests, otherwise the spread could let us conclude the opposite of what is really happened, just because we are out of luck.
• deleted 4y ago
  [deleted]
• titzer 4y ago
  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.
  • dataangel 4y ago
    A 2% efficiency difference is tens if not hundreds of millions of dollars for Google, Meta, etc. Globally it’s enormous.
    • titzer 4y ago
      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?)
• mastax 4y ago
  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 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 {}.
  • est31 4y ago
    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).
    • mastax 4y ago
      I wonder if there could be a flag to tell the compiler that you don't care about getting the exact distinct panic message for each bounds check, please optimize it. I suppose the assert is a flag, in a way, but I mean something more global and automatic. Maybe the compiler could emit a single shared basic block per function that just says "out of bounds access in function foo". We've learned to accept that when you turn on optimizations, you lose some lines and variables from your debug info. This is a pretty similar trade-off.
      • Arnavion 4y ago
        You can use a custom `#[panic_handler]` item that ignores its `PanicInfo` arg and just aborts. The optimizer should notice that it doesn't need to bother with unique messages. However currently this requires either being a no_std program or compiling libstd without its handler, since otherwise its handler will conflict with yours. Although, if one is building their own libstd anyway, then I believe compiling with `--build-std-features panic_immediate_abort` should also have the same effect.
    • Someone 4y ago
      But Rust doesn’t have a spec (https://doc.rust-lang.org/reference/ 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 sometimes (it might not want to do it if the loop made changes that are visible from outside the loop, such as changing a volatile variable or doing I/O)
• brundolf 4y ago
  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)
  • tialaramex 4y ago
    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.
    • est31 4y ago
      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 < len in int i; for(i = 0; i < len; i++)). That's no different from a loop over a slice, both of which eliminate the bounds check in the body of the loop (the one in list[i]). Arrays 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.
      • nindalf 4y ago
        > 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.
        • ReactiveJelly 4y ago
          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];
• mjcohen 4y ago
  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 and kept array bounds checking on in all my code.
  • moloch-hai 4y ago
    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.
• dataangel 4y ago
  If you make no changes what is the difference across benchmark runs? I’m very skeptical.
• worewood 4y ago
  99. ..% of "real" applications are bottlenecked by I/O, be it disk or network or synchronization (as in, waiting for something else to happen) If you're not in a HPC or heavily resource constrained context you can safely ignore the performance implications of choosing whatever programming language you like.
  • azylman 4y ago
    This isn't really true, some languages handle I/O much better than other languages. We migrated a Python application to Go that was about as simple as you can get and mostly blocked by I/O (call DB, transform storage format to Thrift, respond to caller with Thrift) and saw SUBSTANTIAL improvements in performance. Approximately 40% improvement in p99 latency and, more notably, 15x improvement in throughput.
• dahfizz 4y ago
  This is a pretty unsatisfying benchmark. Can we pin the thread to a core and re-run a few times to de-noise? And how about using an actual CPU bound program? Even a significant speedup in the code will be lost in an application like this where you spend so much time in I/O.
• cyber_kinetist 4y ago
  This is one of the main reason you should use indices instead of pointers to store references to other objects (regardless of if you’re using Rust or C++): memory safety. Indices can be bound-checked, pointers can’t.
• Animats 4y ago
  "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.
  • moloch-hai 4y ago
    Each check burns a branch prediction slot, even if it always goes the same way. That may eject a branch predictor whose prediction matters.
    • imtringued 4y ago
      Then it sounds like our branch predictors are shit if they can't deal with simple things like this.
      • saagarjha 4y ago
        This is exactly what they are designed to do and they do their job well, but they can't do it for free.
        • KMag 4y ago
          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) have instructions that hint to the branch predictor, but I think they still end up influencing branch predictor state.
• sammy2255 4y ago
  “ I’d say that either it’s entirely explainable by measurement noise” How about you do something about that? Pin it to a single core? Run it a few thousand times?
• vlovich123 4y ago
  I had written a piece of code that was trying to process things at disk line speed and bounds checking was the first bottleneck I discovered in profiling. I think this is very dependent on the application. It’s unlikely to pop in many applications, but if you’re really trying to push the machine, it seems possible to be the first bottleneck.