4 ms·

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

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.

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.