11 ms·

Rust Performance Pitfalls

424 points by blacksmythe 9y ago

Analemma_ 9y ago
I'm not a compiler expert, but it seems like some of these should be unnecessary, especially with Rust's strong knowledge of types and ownership lifespans. Like this example from the article: let nopes : Vec<_> = bleeps.iter().map(boop).collect(); let frungies : Vec<_> = nopes.iter().filter(|x| x > MIN_THRESHOLD).collect(); where he recommends avoiding the first collect(). Can't the optimizer do that for you if you don't do anything else with nopes?
- pornel 9y ago
  On a high level it seems like it could, but collect() performs heap allocation (and size checks and reallocations for unknown-length iterators), and that's probably too big side effect for LLVM to ignore.
  - radarsat1 9y ago
    Does current Rust contain a way to mark functions as Pure?
    - kibwen 9y ago
      Not in the referentially-transparent sense. Most Rust functions meet almost all of the practical criteria for for purity (i.e. does not mutate global state (or otherwise any state that was not explicitly passed in to the function), does not do I/O), but that's only a comfort for the programmer's ability to reason about the code; this weakened notion of purity-by-default isn't enough to allow the typical optimizations via purity (e.g. memoization).
      - stcredzero 9y ago
        but that's only a comfort for the programmer's ability to reason about the code A way to mark functions as pure for this purpose would be great! Especially if it's not as fraught as const in C++.
        steveklabnik 9y ago
        We actually did have this once, but it wasn't really worth it, so it was removed. https://news.ycombinator.com/item?id=6940624 https://news.ycombinator.com/item?id=6940624 is the HN discussion, but it looks like the link might now be wrong? It was also a very, very long time ago, and so today's Rust might be different enough that those reasons don't apply any more.
        tormeh 9y ago
        The reason at that point vis that there weren't any practical benefits and that it was preferable to wait for a more general mechanism. The first claim is dubious, but I can empathize with second, as long as it doesn't become tacked on. Haskell can do cool optimizations that make it feel like magic sometimes.
        steveklabnik 9y ago
        In some ways, const fn reminds me of this.
        Gankro 9y ago
        Note that a lot of these optimizations aren't necessary in Rust -- e.g. list fusion is only valuable in Haskell because mapping over lists is exposed as a one-shot operation that produces a new list. So `map map map list` is conceptually building 2 whole lists of temporaries you don't care about (and you often don't actually care about the last one either, in cases where you just iterate over it and discard it). Meanwhile mapping in Rust generally takes an iterator and produces another iterator that will apply the given closure to the current element as it's yielded. So the naive codegen for iter().map().map().map().collect() is exactly what list fusion is trying to produce -- no temporary lists. TL;DR: making "map" having the monadic `T[U] -> T[V]` signature is really expensive. ¯\_(ツ)_/¯
        radarsat1 9y ago
        > We actually did have this once, but it wasn't really worth it, so it was removed. Ah, yeah I had a vague memory that that was the case, which is why I asked.. I seem to recall it being removed, but I only follow Rust news, don't use it, so I wasn't sure of the reasons or implications.
  - pcwalton 9y ago
    LLVM will remove heap allocations if they're unused. Optimizing the heap isn't something that LLVM refuses to do as a matter of principle.
- flavio81 9y ago
  Good question. That would mean chaining two statements together so "nopes" is not allocated as a symbol. But, with "let", the user is explicitly instructing the compiler to allocate a reference for "nopes", so i don't think the compiler would chain the statements. Unless it takes the task to checking that "nopes" is not used elsewhere. <Disclaimer: I don't implement compilers so, i can be totally wrong>
  - kibwen 9y ago
    Compiler backends don't particularly care about the user-defined variables in the source, since a typical compilation step is to convert to SSA form ( https://en.wikipedia.org/wiki/Static_single_assignment_form https://en.wikipedia.org/wiki/Static_single_assignment_form ). And it's relatively easy for a backend to remove allocations (or e.g. ignore the act of taking a reference) for variables that never get used. As long as the semantics are preserved, it's all good. The problem in this case is that removing implicitly that first call to collect might change the semantics of the program.
  - jcranmer 9y ago
    The code is problematic, but not because of the let. Optimizations work basically on the as-if principle: they're free to execute code any way they like, but the results must be as if they followed your explicit instructions. Compilers need not, and usually do not, preserve references just because you gave them a name--if you've ever run gdb on optimized code, you'll note how many variables become "<optimized out>" (although that's often a lie for other reasons). The real problem is that you're shoving the variable into a Vec<>, which means that you are doing heap allocation. This means that optimizing it out requires matching the heap allocation to the free, noting that the side effects of these two function calls are only about allocation. There's also issues with respect to inlining, dead-code elimination, and then doing data dependence analysis to prove that the two loops can be fused.
    - deleted 9y ago
      [deleted]
- kibwen 9y ago
  There might be side effects from the first call to `collect`, so the compiler can't get rid of it without potentially changing the semantics of the program.
  - yazaddaruvala 9y ago
    Best example of this (at least in Java): List<CompletableFuture> futures = requestList.map(Client::makeRemoteCall).collect(toList); List<Response> responses = futures.map(CompletableFuture::get).collect(toList); Basically, we need to start all of the futures, then wait for all the futures. Eliminating the first call to `.collect` would force these remote calls to happen one at a time.
    - Analemma_ 9y ago
      This is the kind of example I was hoping for, and I understand a little better now where collect() can have semantically-visible side effects. It seems like it should be possible to have a smarter type system that can tell the difference between futures where collect() can be optimized out and ones where they can't though.
      - Tyr42 9y ago
        Something something Applicative vs Monadic code mumble handwave. Actually that's part of why ApplicativeDo was created: https://research.fb.com/publications/desugaring-haskells-do-notation-into-applicative-operations/ https://research.fb.com/publications/desugaring-haskells-do-... It's pretty cool.
      - kibwen 9y ago
        > It seems like it should be possible to have a smarter type system that can tell the difference between futures While that Java code is neat, you don't need to get anywhere near concurrency to exhibit problems with side effects. Here's a program with two iterator chains and two calls to collect: let foo = [1, 2, 3]; let bar: Vec<_> = foo.iter() .map(|x| { print!("{} ", x); x + 10 }) .collect(); let qux: Vec<_> = bar.iter() .map(|x| { print!("{} ", x); x * 10 }) .collect(); This program prints "1 2 3 11 12 13 ". Here's that same program, but with the first collect removed and the iterator chains collapsed into one: let foo = [1, 2, 3]; let bar: Vec<_> = foo.iter() .map(|x| { print!("{} ", x); x + 10 }) .map(|x| { print!("{} ", x); x * 10 }) .collect(); This program prints "1 11 2 12 3 13 ". When you have two iterator chains with two calls to collect, everything in the first iterator runs to completion, then the second iterator chain runs. When you collapse those two chains into one, you change the order in which things happen. It's still true that a smarter type system would be able to track side effects, but like all effects systems, these things are viral, and it's not immediately clear whether the annotation burden makes up for itself in optimization potential.
agwa 9y ago
> To get rid of the checks, we can either use bytes directly (usually via Vec<u8> / &[u8]) or, if we are absolutely sure the input will be valid UTF-8, use str::from_utf8_unchecked(_) (note that this will require unsafe and break your code in surprising ways should the input not be valid UTF-8). I believe this needs a stronger warning. Functions that operate on strings are allowed to assume that their input is valid UTF-8 and may perform out-of-bounds memory accesses if the input is not valid UTF-8. Therefore, creating a string containing invalid UTF-8 can lead to a memory safety vulnerability. The suggestion to use this function seems out-of-place in this article, which otherwise avoids suggesting unsafe code (e.g. indexing arrays without bounds checking).
- kibwen 9y ago
  What sort of language beyond "absolutely sure", "require unsafe", and "break your code in surprising ways" would you recommend to make this warning stronger?
  - Anderkent 9y ago
    'break your code in surprising ways' is super vague. Saying 'may cause out of bounds memory access/writes should the input not be valid UTF-8' explicitly is probably more scary.
    - steveklabnik 9y ago
      The nature of undefined behavior is in fact super vague; it's not actually possible to say what will happen.
      - infogulch 9y ago
        While technically true, a specific example helps the reader conceptualize what level of danger that means, when they don't already have a concrete understanding like you do. Recall that the breadth of experience for rust's userbase is much larger than e.g. C.
blinkingled 9y ago
> for i in 0..(xs.len()) { let x = xs[i]; // do something with x } > should really be this: > for x in &xs { // do something with x } I am curious why the compiler can't rewrite the former to the latter?
- tatterdemalion 9y ago
  A Sufficiently Smart Compiler would be able to. The second just increments a pointer which starts at the first elem of the array; the first increments a counter and then uses it as an offset into the array, which is bounds checked (the second never generates bounds checks). Proving that that counter never exceeds the end of the array, so the bounds check can be dropped, is not trivial.
- pcwalton 9y ago
  Because in the former case, the optimizer has to prove that the length of the array cannot change during the body of the loop, while in the latter case, that's guaranteed by the language semantics.
  - masklinn 9y ago
    Also because the iterator could do something completely different from an iteration by sequential index no?
  - mindleyhilner 9y ago
    Doesn't `let x = xs[i]` immutably borrow from xs? So for the duration of x's lifetime (which is the entire for-body block), xs cannot be changed and therefore its length must remain the same. Though this might be information that rustc knows about but not LLVM.
    - pcwalton 9y ago
      In the case of "let x = &xs[i]" it would immutably borrow. But we'd need more MIR optimizations to make use of that fact.
- 9y ago
smitherfield 9y ago
>Sometimes, when changing an enum, we want to keep parts of the old value. Use mem::replace to avoid needless clones. use std::mem; enum MyEnum { A { name: String, x: u8 }, B { name: String } } fn a_to_b(e: &mut MyEnum) { // we mutably borrow `e` here. This precludes us from changing it directly // as in `*e = ...`, because the borrow checker won't allow it. Therefore // the assignment to `e` must be outside the `if let` clause. *e = if let MyEnum::A { ref mut name, x: 0 } = *e { // this takes out our `name` and put in an empty String instead // (note that empty strings don't allocate). // Then, construct the new enum variant (which will // be assigned to `*e`, because it is the result of the `if let` expression). MyEnum::B { name: mem::replace(name, String::new()) } // In all other cases, we return immediately, thus skipping the assignment } else { return } } Don't get me wrong, I think Rust is an incredibly impressive language, but this is nuts. For the first time ever, I had a moment of appreciation for the "simple clarity" of C++11 move constructors. If it weren't for the comments and the documentation[1] I wouldn't have had the slightest clue what this code is doing (a hack to fool the borrow checker while allowing for Sufficiently Smart Compilation to a no-op[2] ... I think). This is a good example of the main conceptual aspect of Rust where I feel it could use improvement.[3] A lot of its features marry very high-level concepts (like algebraic data types) to exposed, low-level implementations (like tagged unions). Now, there's nothing wrong with the obvious choice to implement ADTs as tagged unions, but the nature of Rust as a language that exposes low-level control over allocation and addressing, in combination with the strictures of the borrow checker, means enums and other high-level features live in a sort of uncanny valley, falling short of either the high-level expressiveness of ADTs or the low-level flexibility of tagged unions (without expert-level knowledge or using `unsafe`). Similarly, the functional abstractions almost feel like a step backwards from the venerable C++ <algorithm>, abstraction and composition-wise. Very nitty-gritty, low-level implementation details leak out like a sieve — you can't have your maps or folds without a generous sprinking of `as_slice()`, `unwrap()`, `iter()` / `iter_mut()` / `into_iter()` and `collect()` everywhere, although at least for this case you would be able to figure out the idioms by reading the official docs. But nevertheless it seems like reasonable defaults could be inferred from context (with the possible exception of `collect()` since it allocates), while still allowing explicitness as an option when you want low-level control over the code the compiler generates. In this case, enums are a language-level construct, not a library, so the borrow-checker really shouldn't be rejecting reasonable patterns. It (legal to alias between the structural and nominal common subsequence of several members of an enum) should be the default behavior and not require an nonobvious, unreadable hack such as the above. At the very least that behavior (invaluable for many low-level tasks) should be easy to opt in to with e.g. an attribute.[4] [1] https://doc.rust-lang.org/std/mem/fn.replace.html https://doc.rust-lang.org/std/mem/fn.replace.html [2] Or rather since it is a tagged union, in MASMish pseudocode something like jnz x_nonzero mov MyEnum.B, e.tag x_nonzero: ret Although it could still be a no-op depending on what else Sufficiently Smart Compiler/LLVM inlines. [3] And I'm not saying I have the solution or even that all-around-better solutions exist. [4] Something like #![safe_alias_common_subsequence(structural)] #![safe_alias_common_subsequence(nominal_and_structural)]
Lerc 9y ago
I have been doing some exploration of how well Rust optimizes Iterators and have been quite impressed. Writing a iterator to provide the individual bits supplied by an iterator of bytes means you can count them with fn count_bits<I : Iterator<Item=bool>>(it : I) -> i32{ let mut a=0; for i in it { if i {a+=1}; } return a; } Counting bits in an array of bytes would need something like this let p:[u8;6] = [1,2,54,2,3,6]; let result = count_bits(bits(p.iter().cloned())); Checking what that generates in asm https://godbolt.org/g/iTyfap https://godbolt.org/g/iTyfap The core of the code is .LBB0_4: mov esi, edx ;edx has the current mask of the bit we are looking at and esi, ecx ;ecx is the byte we are examining cmp esi, 1 ;check the bit to see if it is set (note using carry not zero flag) sbb eax, -1 ;fun way to conditionally add 1 .LBB0_1: shr edx ;shift mask to the next bit jne .LBB0_4 ;if mask still has a bit in it, go do the next bit otherwise continue to get the next byte cmp rbx, r12 ;r12 has the memory location of where we should stop. Are we there yet? je .LBB0_5 ; if we are there, jump out. we're all done movzx ecx, byte ptr [rbx] ;get the next byte inc rbx ; advance the pointer mov edx, 128 ; set a new mask starting at the top bit jmp .LBB0_4 ; go get the next bit .LBB0_5: Apart from magical bit counting instructions this is close to what I would have written in asm mysef. That really impressed me. I'm still a little wary of hitting a performance cliff. I worry that I can easily add something that will mean the optimiser bails on the whole chain, but so far I'm trusting Rust more than I have trusted any other Optimiser. If this produces simiarly nice code (I haven't checked yet) I'll be very happy for (dest,source) in self.buffer.iter_mut().zip(data) { *dest=source }
- gamegoblin 9y ago
  How much of this is the Rust compiler and how much is generic LLVM optimization passes?
  - pcwalton 9y ago
    It's the combination of LLVM, the Rust compiler providing enough information to LLVM, and very optimized library code. As well as plenty of testing to make sure this kind of stuff doesn't regress :)
jancsika 9y ago
> With some investment into optimizations, matching or exceeding C’s speed should be possible in most cases. What class of algorithms is faster in Rust than it is in C?
- pornel 9y ago
  I don't think it can be generalized like that. Theoretically, Rust's memory ownership/aliasing rules are stricter and more granular than C's restrict, so some pointer-heavy code could optimize better. Rust is very good at inlining by default. Rust makes it easy to use stack-allocated structures. But C can do the same, it's just a matter of effort. Both languages are low level enough that you can use them as a portable assembly and endlessly tweak them to one-up the other. If some C code doesn't optimize well you can write a more contorted code that will.
  - Gankro 9y ago
    Yeah the only thing that Rust might have over C, in terms of really optimized implementations, is low-level idioms that C declares to be UB, but Rust declares to be defined (generally to be what x64 hardware does). Maybe something that leverages signed overflow, overlong shifts, or type punning. But if you have enough control over your codebase to mandate the compiler/flags its built with, then you can generally tell the major C compilers to act like Rust in these cases. That said, the expected win for Rust over C(++) in practice is that you can be more "reckless", because you have a stronger type system protecting you from messing things up. A production-quality C(++) codebase might rightly do more copies, use more reference counting, and use less concurrency just because the risk of doing otherwise isn't worth the potential performance wins. Organizations have limited resources to commit to optimizing/verifying code. Rust is intended to get you more bang for your buck.
    - duneroadrunner 9y ago
      > That said, the expected win for Rust over C(++) in practice is that you can be more "reckless", ... I'm glad to see somebody articulate this observation. SaferCPlusPlus[1] is meant to, in part, bring this benefit to existing C++ code bases. The question is, would a borrow checker for C++ make sense? [1] shameless plug: https://github.com/duneroadrunner/SaferCPlusPlus https://github.com/duneroadrunner/SaferCPlusPlus
mcguire 9y ago
"Similarly, the Read::lines() iterator is very easy to use, but it has one downside: It allocates a String for each line. Manually allocating and reusing a String will reduce memory churn and may gain you a bit of performance." Back when Rust used "internal" iterators, this could be the default. Now, you can encapsulate it by passing a function to handle each line.

424 points by blacksmythe 9y ago

I'm not a compiler expert, but it seems like some of these should be unnecessary, especially with Rust's strong knowledge of types and ownership lifespans. Like this example from the article: let nopes : Vec<_> = bleeps.iter().map(boop).collect(); let frungies : Vec<_> = nopes.iter().filter(|x| x > MIN_THRESHOLD).collect(); where he recommends avoiding the first collect(). Can't the optimizer do that for you if you don't do anything else with nopes?

pornel 9y ago
On a high level it seems like it could, but collect() performs heap allocation (and size checks and reallocations for unknown-length iterators), and that's probably too big side effect for LLVM to ignore.
- radarsat1 9y ago
  Does current Rust contain a way to mark functions as Pure?
  - kibwen 9y ago
    Not in the referentially-transparent sense. Most Rust functions meet almost all of the practical criteria for for purity (i.e. does not mutate global state (or otherwise any state that was not explicitly passed in to the function), does not do I/O), but that's only a comfort for the programmer's ability to reason about the code; this weakened notion of purity-by-default isn't enough to allow the typical optimizations via purity (e.g. memoization).
    - stcredzero 9y ago
      but that's only a comfort for the programmer's ability to reason about the code A way to mark functions as pure for this purpose would be great! Especially if it's not as fraught as const in C++.
      - steveklabnik 9y ago
        We actually did have this once, but it wasn't really worth it, so it was removed. https://news.ycombinator.com/item?id=6940624 https://news.ycombinator.com/item?id=6940624 is the HN discussion, but it looks like the link might now be wrong? It was also a very, very long time ago, and so today's Rust might be different enough that those reasons don't apply any more.
        tormeh 9y ago
        The reason at that point vis that there weren't any practical benefits and that it was preferable to wait for a more general mechanism. The first claim is dubious, but I can empathize with second, as long as it doesn't become tacked on. Haskell can do cool optimizations that make it feel like magic sometimes.
        steveklabnik 9y ago
        In some ways, const fn reminds me of this.
        Gankro 9y ago
        Note that a lot of these optimizations aren't necessary in Rust -- e.g. list fusion is only valuable in Haskell because mapping over lists is exposed as a one-shot operation that produces a new list. So `map map map list` is conceptually building 2 whole lists of temporaries you don't care about (and you often don't actually care about the last one either, in cases where you just iterate over it and discard it). Meanwhile mapping in Rust generally takes an iterator and produces another iterator that will apply the given closure to the current element as it's yielded. So the naive codegen for iter().map().map().map().collect() is exactly what list fusion is trying to produce -- no temporary lists. TL;DR: making "map" having the monadic `T[U] -> T[V]` signature is really expensive. ¯\_(ツ)_/¯
        radarsat1 9y ago
        > We actually did have this once, but it wasn't really worth it, so it was removed. Ah, yeah I had a vague memory that that was the case, which is why I asked.. I seem to recall it being removed, but I only follow Rust news, don't use it, so I wasn't sure of the reasons or implications.
- pcwalton 9y ago
  LLVM will remove heap allocations if they're unused. Optimizing the heap isn't something that LLVM refuses to do as a matter of principle.
flavio81 9y ago
Good question. That would mean chaining two statements together so "nopes" is not allocated as a symbol. But, with "let", the user is explicitly instructing the compiler to allocate a reference for "nopes", so i don't think the compiler would chain the statements. Unless it takes the task to checking that "nopes" is not used elsewhere. <Disclaimer: I don't implement compilers so, i can be totally wrong>
- kibwen 9y ago
  Compiler backends don't particularly care about the user-defined variables in the source, since a typical compilation step is to convert to SSA form ( https://en.wikipedia.org/wiki/Static_single_assignment_form https://en.wikipedia.org/wiki/Static_single_assignment_form ). And it's relatively easy for a backend to remove allocations (or e.g. ignore the act of taking a reference) for variables that never get used. As long as the semantics are preserved, it's all good. The problem in this case is that removing implicitly that first call to collect might change the semantics of the program.
- jcranmer 9y ago
  The code is problematic, but not because of the let. Optimizations work basically on the as-if principle: they're free to execute code any way they like, but the results must be as if they followed your explicit instructions. Compilers need not, and usually do not, preserve references just because you gave them a name--if you've ever run gdb on optimized code, you'll note how many variables become "<optimized out>" (although that's often a lie for other reasons). The real problem is that you're shoving the variable into a Vec<>, which means that you are doing heap allocation. This means that optimizing it out requires matching the heap allocation to the free, noting that the side effects of these two function calls are only about allocation. There's also issues with respect to inlining, dead-code elimination, and then doing data dependence analysis to prove that the two loops can be fused.
  - deleted 9y ago
    [deleted]
kibwen 9y ago
There might be side effects from the first call to `collect`, so the compiler can't get rid of it without potentially changing the semantics of the program.
- yazaddaruvala 9y ago
  Best example of this (at least in Java): List<CompletableFuture> futures = requestList.map(Client::makeRemoteCall).collect(toList); List<Response> responses = futures.map(CompletableFuture::get).collect(toList); Basically, we need to start all of the futures, then wait for all the futures. Eliminating the first call to `.collect` would force these remote calls to happen one at a time.
  - Analemma_ 9y ago
    This is the kind of example I was hoping for, and I understand a little better now where collect() can have semantically-visible side effects. It seems like it should be possible to have a smarter type system that can tell the difference between futures where collect() can be optimized out and ones where they can't though.
    - Tyr42 9y ago
      Something something Applicative vs Monadic code mumble handwave. Actually that's part of why ApplicativeDo was created: https://research.fb.com/publications/desugaring-haskells-do-notation-into-applicative-operations/ https://research.fb.com/publications/desugaring-haskells-do-... It's pretty cool.
    - kibwen 9y ago
      > It seems like it should be possible to have a smarter type system that can tell the difference between futures While that Java code is neat, you don't need to get anywhere near concurrency to exhibit problems with side effects. Here's a program with two iterator chains and two calls to collect: let foo = [1, 2, 3]; let bar: Vec<_> = foo.iter() .map(|x| { print!("{} ", x); x + 10 }) .collect(); let qux: Vec<_> = bar.iter() .map(|x| { print!("{} ", x); x * 10 }) .collect(); This program prints "1 2 3 11 12 13 ". Here's that same program, but with the first collect removed and the iterator chains collapsed into one: let foo = [1, 2, 3]; let bar: Vec<_> = foo.iter() .map(|x| { print!("{} ", x); x + 10 }) .map(|x| { print!("{} ", x); x * 10 }) .collect(); This program prints "1 11 2 12 3 13 ". When you have two iterator chains with two calls to collect, everything in the first iterator runs to completion, then the second iterator chain runs. When you collapse those two chains into one, you change the order in which things happen. It's still true that a smarter type system would be able to track side effects, but like all effects systems, these things are viral, and it's not immediately clear whether the annotation burden makes up for itself in optimization potential.

agwa 9y ago

> To get rid of the checks, we can either use bytes directly (usually via Vec<u8> / &[u8]) or, if we are absolutely sure the input will be valid UTF-8, use str::from_utf8_unchecked(_) (note that this will require unsafe and break your code in surprising ways should the input not be valid UTF-8). I believe this needs a stronger warning. Functions that operate on strings are allowed to assume that their input is valid UTF-8 and may perform out-of-bounds memory accesses if the input is not valid UTF-8. Therefore, creating a string containing invalid UTF-8 can lead to a memory safety vulnerability. The suggestion to use this function seems out-of-place in this article, which otherwise avoids suggesting unsafe code (e.g. indexing arrays without bounds checking).

kibwen 9y ago
What sort of language beyond "absolutely sure", "require unsafe", and "break your code in surprising ways" would you recommend to make this warning stronger?
- Anderkent 9y ago
  'break your code in surprising ways' is super vague. Saying 'may cause out of bounds memory access/writes should the input not be valid UTF-8' explicitly is probably more scary.
  - steveklabnik 9y ago
    The nature of undefined behavior is in fact super vague; it's not actually possible to say what will happen.
    - infogulch 9y ago
      While technically true, a specific example helps the reader conceptualize what level of danger that means, when they don't already have a concrete understanding like you do. Recall that the breadth of experience for rust's userbase is much larger than e.g. C.

blinkingled 9y ago

> for i in 0..(xs.len()) { let x = xs[i]; // do something with x } > should really be this: > for x in &xs { // do something with x } I am curious why the compiler can't rewrite the former to the latter?

tatterdemalion 9y ago
A Sufficiently Smart Compiler would be able to. The second just increments a pointer which starts at the first elem of the array; the first increments a counter and then uses it as an offset into the array, which is bounds checked (the second never generates bounds checks). Proving that that counter never exceeds the end of the array, so the bounds check can be dropped, is not trivial.
pcwalton 9y ago
Because in the former case, the optimizer has to prove that the length of the array cannot change during the body of the loop, while in the latter case, that's guaranteed by the language semantics.
- masklinn 9y ago
  Also because the iterator could do something completely different from an iteration by sequential index no?
- mindleyhilner 9y ago
  Doesn't `let x = xs[i]` immutably borrow from xs? So for the duration of x's lifetime (which is the entire for-body block), xs cannot be changed and therefore its length must remain the same. Though this might be information that rustc knows about but not LLVM.
  - pcwalton 9y ago
    In the case of "let x = &xs[i]" it would immutably borrow. But we'd need more MIR optimizations to make use of that fact.
9y ago

smitherfield 9y ago

>Sometimes, when changing an enum, we want to keep parts of the old value. Use mem::replace to avoid needless clones. use std::mem; enum MyEnum { A { name: String, x: u8 }, B { name: String } } fn a_to_b(e: &mut MyEnum) { // we mutably borrow `e` here. This precludes us from changing it directly // as in `*e = ...`, because the borrow checker won't allow it. Therefore // the assignment to `e` must be outside the `if let` clause. *e = if let MyEnum::A { ref mut name, x: 0 } = *e { // this takes out our `name` and put in an empty String instead // (note that empty strings don't allocate). // Then, construct the new enum variant (which will // be assigned to `*e`, because it is the result of the `if let` expression). MyEnum::B { name: mem::replace(name, String::new()) } // In all other cases, we return immediately, thus skipping the assignment } else { return } } Don't get me wrong, I think Rust is an incredibly impressive language, but this is nuts. For the first time ever, I had a moment of appreciation for the "simple clarity" of C++11 move constructors. If it weren't for the comments and the documentation[1] I wouldn't have had the slightest clue what this code is doing (a hack to fool the borrow checker while allowing for Sufficiently Smart Compilation to a no-op[2] ... I think). This is a good example of the main conceptual aspect of Rust where I feel it could use improvement.[3] A lot of its features marry very high-level concepts (like algebraic data types) to exposed, low-level implementations (like tagged unions). Now, there's nothing wrong with the obvious choice to implement ADTs as tagged unions, but the nature of Rust as a language that exposes low-level control over allocation and addressing, in combination with the strictures of the borrow checker, means enums and other high-level features live in a sort of uncanny valley, falling short of either the high-level expressiveness of ADTs or the low-level flexibility of tagged unions (without expert-level knowledge or using `unsafe`). Similarly, the functional abstractions almost feel like a step backwards from the venerable C++ <algorithm>, abstraction and composition-wise. Very nitty-gritty, low-level implementation details leak out like a sieve — you can't have your maps or folds without a generous sprinking of `as_slice()`, `unwrap()`, `iter()` / `iter_mut()` / `into_iter()` and `collect()` everywhere, although at least for this case you would be able to figure out the idioms by reading the official docs. But nevertheless it seems like reasonable defaults could be inferred from context (with the possible exception of `collect()` since it allocates), while still allowing explicitness as an option when you want low-level control over the code the compiler generates. In this case, enums are a language-level construct, not a library, so the borrow-checker really shouldn't be rejecting reasonable patterns. It (legal to alias between the structural and nominal common subsequence of several members of an enum) should be the default behavior and not require an nonobvious, unreadable hack such as the above. At the very least that behavior (invaluable for many low-level tasks) should be easy to opt in to with e.g. an attribute.[4] [1] https://doc.rust-lang.org/std/mem/fn.replace.html https://doc.rust-lang.org/std/mem/fn.replace.html [2] Or rather since it is a tagged union, in MASMish pseudocode something like jnz x_nonzero mov MyEnum.B, e.tag x_nonzero: ret Although it could still be a no-op depending on what else Sufficiently Smart Compiler/LLVM inlines. [3] And I'm not saying I have the solution or even that all-around-better solutions exist. [4] Something like #![safe_alias_common_subsequence(structural)] #![safe_alias_common_subsequence(nominal_and_structural)]

Lerc 9y ago

I have been doing some exploration of how well Rust optimizes Iterators and have been quite impressed. Writing a iterator to provide the individual bits supplied by an iterator of bytes means you can count them with fn count_bits<I : Iterator<Item=bool>>(it : I) -> i32{ let mut a=0; for i in it { if i {a+=1}; } return a; } Counting bits in an array of bytes would need something like this let p:[u8;6] = [1,2,54,2,3,6]; let result = count_bits(bits(p.iter().cloned())); Checking what that generates in asm https://godbolt.org/g/iTyfap https://godbolt.org/g/iTyfap The core of the code is .LBB0_4: mov esi, edx ;edx has the current mask of the bit we are looking at and esi, ecx ;ecx is the byte we are examining cmp esi, 1 ;check the bit to see if it is set (note using carry not zero flag) sbb eax, -1 ;fun way to conditionally add 1 .LBB0_1: shr edx ;shift mask to the next bit jne .LBB0_4 ;if mask still has a bit in it, go do the next bit otherwise continue to get the next byte cmp rbx, r12 ;r12 has the memory location of where we should stop. Are we there yet? je .LBB0_5 ; if we are there, jump out. we're all done movzx ecx, byte ptr [rbx] ;get the next byte inc rbx ; advance the pointer mov edx, 128 ; set a new mask starting at the top bit jmp .LBB0_4 ; go get the next bit .LBB0_5: Apart from magical bit counting instructions this is close to what I would have written in asm mysef. That really impressed me. I'm still a little wary of hitting a performance cliff. I worry that I can easily add something that will mean the optimiser bails on the whole chain, but so far I'm trusting Rust more than I have trusted any other Optimiser. If this produces simiarly nice code (I haven't checked yet) I'll be very happy for (dest,source) in self.buffer.iter_mut().zip(data) { *dest=source }

gamegoblin 9y ago
How much of this is the Rust compiler and how much is generic LLVM optimization passes?
- pcwalton 9y ago
  It's the combination of LLVM, the Rust compiler providing enough information to LLVM, and very optimized library code. As well as plenty of testing to make sure this kind of stuff doesn't regress :)

jancsika 9y ago

> With some investment into optimizations, matching or exceeding C’s speed should be possible in most cases. What class of algorithms is faster in Rust than it is in C?

pornel 9y ago
I don't think it can be generalized like that. Theoretically, Rust's memory ownership/aliasing rules are stricter and more granular than C's restrict, so some pointer-heavy code could optimize better. Rust is very good at inlining by default. Rust makes it easy to use stack-allocated structures. But C can do the same, it's just a matter of effort. Both languages are low level enough that you can use them as a portable assembly and endlessly tweak them to one-up the other. If some C code doesn't optimize well you can write a more contorted code that will.
- Gankro 9y ago
  Yeah the only thing that Rust might have over C, in terms of really optimized implementations, is low-level idioms that C declares to be UB, but Rust declares to be defined (generally to be what x64 hardware does). Maybe something that leverages signed overflow, overlong shifts, or type punning. But if you have enough control over your codebase to mandate the compiler/flags its built with, then you can generally tell the major C compilers to act like Rust in these cases. That said, the expected win for Rust over C(++) in practice is that you can be more "reckless", because you have a stronger type system protecting you from messing things up. A production-quality C(++) codebase might rightly do more copies, use more reference counting, and use less concurrency just because the risk of doing otherwise isn't worth the potential performance wins. Organizations have limited resources to commit to optimizing/verifying code. Rust is intended to get you more bang for your buck.
  - duneroadrunner 9y ago
    > That said, the expected win for Rust over C(++) in practice is that you can be more "reckless", ... I'm glad to see somebody articulate this observation. SaferCPlusPlus[1] is meant to, in part, bring this benefit to existing C++ code bases. The question is, would a borrow checker for C++ make sense? [1] shameless plug: https://github.com/duneroadrunner/SaferCPlusPlus https://github.com/duneroadrunner/SaferCPlusPlus

mcguire 9y ago

"Similarly, the Read::lines() iterator is very easy to use, but it has one downside: It allocates a String for each line. Manually allocating and reusing a String will reduce memory churn and may gain you a bit of performance." Back when Rust used "internal" iterators, this could be the default. Now, you can encapsulate it by passing a function to handle each line.