3 ms·

The bounds checks in Rust are implicit (i.e. part of the std implementation), and get removed by the compiler if they're unnecessary. I think that's a pretty gr

by tinco 3y ago

The bounds checks in Rust are implicit (i.e. part of the std implementation), and get removed by the compiler if they're unnecessary. I think that's a pretty great improvement over the state of things in C. And if you are convinced you don't need a bounds check and the compiler does not remove it you can explicitly remove the bounds check, provided you mark the access as unsafe. So Rust is a strict improvement over C in this regard.

faitswulff 3y ago
shnatsel wrote a post on bounds checking performance implications in Rust. Money quote: > The real-world performance impact of bounds checks is surprisingly low. > The greatest impact I’ve ever seen on real-world code from removing bounds checks alone was *15%,* but the typical gains are in *1% to 3% range,* and even that only happens in code that does a lot of number crunching. > You can occasionally see greater impact (as we’ll see soon!) if removing bounds checks allows the compiler to perform other optimizations. > Still, performance of code that’s not doing large amounts of number crunching will probably [not be impacted by bounds checks](https://blog.readyset.io/bounds-checks/ https://blog.readyset.io/bounds-checks/) at all. It is, of course, not universally applicable, so read the post for full details: https://shnatsel.medium.com/how-to-avoid-bounds-checks-in-rust-without-unsafe-f65e618b4c1e https://shnatsel.medium.com/how-to-avoid-bounds-checks-in-ru...
bayindirh 3y ago
Asking because of interest: How compiler decides that it needs BC or not?
- tinco 3y ago
  Through value tracking. It's actually LLVM that does this, GCC probably does it as well, so in theory explicit bounds checks in regular C code would also be removed by the compiler. How it works exactly I don't know, and apparently it's so complex that it requires over 9000 lines of C++ to express: https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/ValueTracking.cpp https://github.com/llvm/llvm-project/blob/main/llvm/lib/Anal...
  - jcranmer 3y ago
    > How it works exactly I don't know The idea is pretty simple. You can build a list of known facts based on control flow, explicit __builtin_assumes, and undefined behavior relations. For example, if you've got this code: if (x < N) { // In this block, we know that x < N } else { // ... and in this block we know that x >= N! } And on top of that, we can do some basic algebra. If we know that x < N and N < 5, then we can infer that x < 5. So if we see a comparison x < 5, we can then rewrite that to true. > and apparently it's so complex that it requires over 9000 lines of C++ to express The two main reasons for that is that a) there is a lot of rules covering cases like "we know the result of count_leading_zeroes can be no more than the number of bits in an integer" and so forth, and b) this is doing a lot more logic than just tracking integer comparisons: there's tracking known-bits of integers, maximum possible value, floating-point comparisons, pointer object references.
    - jakubadamw 3y ago
      > And on top of that, we can do some basic algebra. If we know that x < N and N < 5, then we can infer that x < 5. So if we see a comparison x < 5, we can then rewrite that to true. Even better: if `x` and `N` are integers, then we can infer that `x` < 4. :)
      - KMag 3y ago
        I think you mean x <= 4, right?
        karamanolev 3y ago
        No, x < 4, within integers. If N < 5, then N <= 4. If x < N, then x < 4.
- deleted 3y ago
  [deleted]
- orlp 3y ago
  An example of when it's not necessary: for i in 0..v.len() { v[i] += 1; } Because the compiler can prove that i < v.len() due to the loop condition, the bounds check gets eliminated.
  - bayindirh 3y ago
    Thanks! My case is a bit outside that, so I don't think the compiler can deduce that. I have a file format which tells me the expected number of fields about a category, and I throw an error & abort if the number is not exactly that. Also, these data structure fields are always sent in as const variables, so they are never modified (making them "sealed" in a sense), hence I don't need to bounds check on arrays and vectors storing them.
    - deleted 3y ago
      [deleted]
    - ihattendorf 3y ago
      That sounds trivial enough that the compiler would remove the bounds checks, assuming I'm understanding correctly that you have a condition that validates the number of fields at some point before an invalid access would occur. But if it's possible for someone to muck with the file contents and lie about the number of fields which would cause a bounds error, that's exactly what bounds checking is supposed to avoid. So either bounds checks will be removed, or they're necessary.
      - bayindirh 3y ago
        I think it won't be able to because the creation of these data structures and consuming them is 3 files apart. > But if it's possible for someone to muck with the file contents and lie about the number of fields. You can't. You can say you'll have 7, but provide 8. But as soon as I encounter the 8th one during parsing, everything aborts. Same for saying 7 and providing 6. If the file ends after parsing 6th one, I say there's an error in your file and abort. Everything has to checkout and have to be sane to be able to start. Otherwise you'll get file format errors all day. The rest of the pipeline is unattended completely. It's bona fide number crunching (material simulation to be exact), so speed is of the essence. Talking about >1.5 million iterations per second per core.

by tinco 3y ago

faitswulff 3y ago

shnatsel wrote a post on bounds checking performance implications in Rust. Money quote: > The real-world performance impact of bounds checks is surprisingly low. > The greatest impact I’ve ever seen on real-world code from removing bounds checks alone was *15%,* but the typical gains are in *1% to 3% range,* and even that only happens in code that does a lot of number crunching. > You can occasionally see greater impact (as we’ll see soon!) if removing bounds checks allows the compiler to perform other optimizations. > Still, performance of code that’s not doing large amounts of number crunching will probably [not be impacted by bounds checks](https://blog.readyset.io/bounds-checks/ https://blog.readyset.io/bounds-checks/) at all. It is, of course, not universally applicable, so read the post for full details: https://shnatsel.medium.com/how-to-avoid-bounds-checks-in-rust-without-unsafe-f65e618b4c1e https://shnatsel.medium.com/how-to-avoid-bounds-checks-in-ru...

bayindirh 3y ago

Asking because of interest: How compiler decides that it needs BC or not?

tinco 3y ago
Through value tracking. It's actually LLVM that does this, GCC probably does it as well, so in theory explicit bounds checks in regular C code would also be removed by the compiler. How it works exactly I don't know, and apparently it's so complex that it requires over 9000 lines of C++ to express: https://github.com/llvm/llvm-project/blob/main/llvm/lib/Analysis/ValueTracking.cpp https://github.com/llvm/llvm-project/blob/main/llvm/lib/Anal...
- jcranmer 3y ago
  > How it works exactly I don't know The idea is pretty simple. You can build a list of known facts based on control flow, explicit __builtin_assumes, and undefined behavior relations. For example, if you've got this code: if (x < N) { // In this block, we know that x < N } else { // ... and in this block we know that x >= N! } And on top of that, we can do some basic algebra. If we know that x < N and N < 5, then we can infer that x < 5. So if we see a comparison x < 5, we can then rewrite that to true. > and apparently it's so complex that it requires over 9000 lines of C++ to express The two main reasons for that is that a) there is a lot of rules covering cases like "we know the result of count_leading_zeroes can be no more than the number of bits in an integer" and so forth, and b) this is doing a lot more logic than just tracking integer comparisons: there's tracking known-bits of integers, maximum possible value, floating-point comparisons, pointer object references.
  - jakubadamw 3y ago
    > And on top of that, we can do some basic algebra. If we know that x < N and N < 5, then we can infer that x < 5. So if we see a comparison x < 5, we can then rewrite that to true. Even better: if `x` and `N` are integers, then we can infer that `x` < 4. :)
    - KMag 3y ago
      I think you mean x <= 4, right?
      - karamanolev 3y ago
        No, x < 4, within integers. If N < 5, then N <= 4. If x < N, then x < 4.
deleted 3y ago
[deleted]
orlp 3y ago
An example of when it's not necessary: for i in 0..v.len() { v[i] += 1; } Because the compiler can prove that i < v.len() due to the loop condition, the bounds check gets eliminated.
- bayindirh 3y ago
  Thanks! My case is a bit outside that, so I don't think the compiler can deduce that. I have a file format which tells me the expected number of fields about a category, and I throw an error & abort if the number is not exactly that. Also, these data structure fields are always sent in as const variables, so they are never modified (making them "sealed" in a sense), hence I don't need to bounds check on arrays and vectors storing them.
  - deleted 3y ago
    [deleted]
  - ihattendorf 3y ago
    That sounds trivial enough that the compiler would remove the bounds checks, assuming I'm understanding correctly that you have a condition that validates the number of fields at some point before an invalid access would occur. But if it's possible for someone to muck with the file contents and lie about the number of fields which would cause a bounds error, that's exactly what bounds checking is supposed to avoid. So either bounds checks will be removed, or they're necessary.
    - bayindirh 3y ago
      I think it won't be able to because the creation of these data structures and consuming them is 3 files apart. > But if it's possible for someone to muck with the file contents and lie about the number of fields. You can't. You can say you'll have 7, but provide 8. But as soon as I encounter the 8th one during parsing, everything aborts. Same for saying 7 and providing 6. If the file ends after parsing 6th one, I say there's an error in your file and abort. Everything has to checkout and have to be sane to be able to start. Otherwise you'll get file format errors all day. The rest of the pipeline is unattended completely. It's bona fide number crunching (material simulation to be exact), so speed is of the essence. Talking about >1.5 million iterations per second per core.