6 ms·

In addition, the Rust compiler can also remove the built-in indexing checks if it can prove the code is safe. So, say, iterator loops over an array won't have a

In addition, the Rust compiler can also remove the built-in indexing checks if it can prove the code is safe. So, say, iterator loops over an array won't have any index checking.

ori_b 10y ago
So can the C compiler. The optimization is called 'value range propagation'.
dbaupp 10y ago
As others have said, this is a fairly standard optimisation: compilers (Rust, C, C++, Java, PHP, whatever) will remove branches if they can see that it can never be taken. Iterators are slightly different in that they don't have any indexing checks at all: an array iterator yields a plain reference, and these are always dereferenced like plain pointers.
staticassertion 10y ago
C/ C++ compilers are also capable of doing this, though rust's iterator syntax tends to make it a pretty natural optimization.
- Animats 10y ago
  Neither C nor C++ knows, at the language level, the size of an array, unless that size is fixed. The subscript checking variants of C and C++ have to use "fat pointers" which carry along size information. The overhead for this is large and nobody uses that. Fat pointers used to be a feature you could turn on in gcc, but it's somewhat abandoned now.
  - sirclueless 10y ago
    > Neither C nor C++ knows, at the language level, the size of an array, unless that size is fixed. Neither does Rust. > The subscript checking variants of C and C++ have to use "fat pointers" which carry along size information. So do Rust's Slices. > The overhead for this is large and nobody uses that. People use std::vector all the time for this purpose in C++. It has about the performance you'd expect, with very little overhead except where you want it in bounds-checking. I don't think there's actually a performance difference here. Rust's default is safer because it requires dropping to unsafe code to do something dangerous, but the same optimizations are available in both.
    - steveklabnik 10y ago
      One thing that I've heard might be a difference, but haven't confirmed yet: Rust's lack of move constructors. So you have a vector, it's full, you push one more. It has to reallocate. How do you copy all of the elements over to the new allocation? In Rust, it's a straight memcpy of T * n bytes. But due to move constructors in C++, IIRC they must be moved one at a time. Again, I haven't actually dug into this; maybe someone more knowledgeable about this can point me in the right direction here?
      - sirclueless 10y ago
        Well, for trivially copyable types[1] the reallocation can be a straight memcpy. For the rest, I don't know that having or not having a move constructor is the important distinction; it will be preferred over the copy constructor if it is declared as not throwing exceptions, but either way some constructor of the object must be called if it exists (though it might be inlined and optimized away). I imagine Rust does something similar, copying bytes if the underlying type has the `Copy` trait and calling some actual code if not, but I'm not familiar with the details. [1]: http://en.cppreference.com/w/cpp/concept/TriviallyCopyable http://en.cppreference.com/w/cpp/concept/TriviallyCopyable
        steveklabnik 10y ago
        Thanks for elaborating on this! > copying bytes if the underlying type has the `Copy` trait and calling some actual code if not, It does not. Moves and copies are both "memcopy these bytes", the only difference is if you can use the previous copy or not. (This is also, of course, subject to the optimizer, which may elide the copy.) > either way some constructor of the object must be called if it exists (though it might be inlined and optimized away). Yeah, this is what I was getting at; this has to happen in C++, but not in Rust. You are right to point out that this only matters for things that aren't trivially copyable.
        sirclueless 10y ago
        Interesting. How does Rust handle types that want to do interesting things when copied, like bookkeeping or updating internal pointers? Maybe you just can't, which would preclude some kinds of intrusive data structures, or owning non-copyable mutexes for example. Does `drop()` get called on objects that have been copied from?
jdcarter 10y ago
Go also does this as of version 1.7: http://www.tapirgames.com/blog/golang-1.7-bce http://www.tapirgames.com/blog/golang-1.7-bce
pjmlp 10y ago
Compilers for Pascal dialects, Ada and Modula-2 were already doing that in the early 90's.
Veedrac 10y ago
Iterator loops are different. They don't elide bounds checks automatically, like frequently claimed. Instead they merge it with the loop branch, so there's no redundant checking.

In addition, the Rust compiler can also remove the built-in indexing checks if it can prove the code is safe. So, say, iterator loops over an array won't have any index checking.

ori_b 10y ago

So can the C compiler. The optimization is called 'value range propagation'.

dbaupp 10y ago

As others have said, this is a fairly standard optimisation: compilers (Rust, C, C++, Java, PHP, whatever) will remove branches if they can see that it can never be taken. Iterators are slightly different in that they don't have any indexing checks at all: an array iterator yields a plain reference, and these are always dereferenced like plain pointers.

staticassertion 10y ago

C/ C++ compilers are also capable of doing this, though rust's iterator syntax tends to make it a pretty natural optimization.

Animats 10y ago
Neither C nor C++ knows, at the language level, the size of an array, unless that size is fixed. The subscript checking variants of C and C++ have to use "fat pointers" which carry along size information. The overhead for this is large and nobody uses that. Fat pointers used to be a feature you could turn on in gcc, but it's somewhat abandoned now.
- sirclueless 10y ago
  > Neither C nor C++ knows, at the language level, the size of an array, unless that size is fixed. Neither does Rust. > The subscript checking variants of C and C++ have to use "fat pointers" which carry along size information. So do Rust's Slices. > The overhead for this is large and nobody uses that. People use std::vector all the time for this purpose in C++. It has about the performance you'd expect, with very little overhead except where you want it in bounds-checking. I don't think there's actually a performance difference here. Rust's default is safer because it requires dropping to unsafe code to do something dangerous, but the same optimizations are available in both.
  - steveklabnik 10y ago
    One thing that I've heard might be a difference, but haven't confirmed yet: Rust's lack of move constructors. So you have a vector, it's full, you push one more. It has to reallocate. How do you copy all of the elements over to the new allocation? In Rust, it's a straight memcpy of T * n bytes. But due to move constructors in C++, IIRC they must be moved one at a time. Again, I haven't actually dug into this; maybe someone more knowledgeable about this can point me in the right direction here?
    - sirclueless 10y ago
      Well, for trivially copyable types[1] the reallocation can be a straight memcpy. For the rest, I don't know that having or not having a move constructor is the important distinction; it will be preferred over the copy constructor if it is declared as not throwing exceptions, but either way some constructor of the object must be called if it exists (though it might be inlined and optimized away). I imagine Rust does something similar, copying bytes if the underlying type has the `Copy` trait and calling some actual code if not, but I'm not familiar with the details. [1]: http://en.cppreference.com/w/cpp/concept/TriviallyCopyable http://en.cppreference.com/w/cpp/concept/TriviallyCopyable
      - steveklabnik 10y ago
        Thanks for elaborating on this! > copying bytes if the underlying type has the `Copy` trait and calling some actual code if not, It does not. Moves and copies are both "memcopy these bytes", the only difference is if you can use the previous copy or not. (This is also, of course, subject to the optimizer, which may elide the copy.) > either way some constructor of the object must be called if it exists (though it might be inlined and optimized away). Yeah, this is what I was getting at; this has to happen in C++, but not in Rust. You are right to point out that this only matters for things that aren't trivially copyable.
        sirclueless 10y ago
        Interesting. How does Rust handle types that want to do interesting things when copied, like bookkeeping or updating internal pointers? Maybe you just can't, which would preclude some kinds of intrusive data structures, or owning non-copyable mutexes for example. Does `drop()` get called on objects that have been copied from?

jdcarter 10y ago

Go also does this as of version 1.7: http://www.tapirgames.com/blog/golang-1.7-bce http://www.tapirgames.com/blog/golang-1.7-bce

pjmlp 10y ago

Compilers for Pascal dialects, Ada and Modula-2 were already doing that in the early 90's.

Veedrac 10y ago

Iterator loops are different. They don't elide bounds checks automatically, like frequently claimed. Instead they merge it with the loop branch, so there's no redundant checking.