4 ms·

Is there a well defined class of code, whose expression in Rust, will perform better than what would be emitted by a sufficiently advanced optimizing compiler (

Is there a well defined class of code, whose expression in Rust, will perform better than what would be emitted by a sufficiently advanced optimizing compiler (say SBCL) ?

skavi 4y ago
Not exactly a class, but there are runtimes of concrete programs written in SBCL and C++ here: https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/sbcl-gpp.html https://benchmarksgame-team.pages.debian.net/benchmarksgame/... No direct Rust SBCL comparisons, but generally Rust and C++ perform similarly. There's some discussion on the limitations of SBCL's GC in this thread: https://old.reddit.com/r/Common_Lisp/comments/j8z1j7/how_does_the_gc_in_sbcl_impact_fps/ https://old.reddit.com/r/Common_Lisp/comments/j8z1j7/how_doe...
- jjtheblunt 4y ago
  thank you!
- dgb23 4y ago
  It’s interesting to see that a fully dynamic, GC language manages to stay within 1x, 5x, 10x range of C++ in these tests. I haven’t looked at the tests themselves so I can’t speak to their application. But the range of performance for dynamic languages seems to be enormous. Much bigger than the one of static languages.
  - tmtvl 4y ago
    > fully dynamic Well, no, it's SBCL. Common Lisp has support for types, but most compilers only use them for optimization, SBCL goes one step further and emits warnings when you mismatch types. And looking at the code, I can see lots of type declarations. It's also interesting to note that the code does not seem to be using SBCL's new SIMD library*, so it could be sped up even more. * <https://github.com/marcoheisig/sb-simd https://github.com/marcoheisig/sb-simd>, see the texinfo file for documentation.
saurik 4y ago
I mean... if the compiler isn't smart enough to see what you were trying to do and generate some ridiculously fast implementation, is it truly worthy of being called "sufficiently advanced"? ;P You just know someone is going to try to add in an LLM-based (note the lack of a V there) compiler pass that says "give me a faster algorithm that does the same thing as this function" (and then all hell will break loose when it starts injecting random bullshit into the function it sort of grokked, or decides your code is for some evil ad company and deletes it on purpose... oh, wait: maybe this is a great idea).
TheDong 4y ago
The most common example is aliasing. Since the rust type system promises that you won't have two mutable aliases to the same data, even data coming from an unknown caller, the compiler can in theory make optimizations that aren't possible in other languages that permit multiple mutable aliases. Especially for values that cross the boundaries of compilation units, the compiler in another language cannot possible have enough information to know if aliasing could occur.
- howinteresting 4y ago
  I think we haven't even come close to harnessing the full benefits of (1) mutable references can't be aliased, and (2) referential transparency: data behind an immutable pointer never changing no matter how many aliases to it there are. (The exception being UnsafeCell, of course, which can easily be detected.) Exciting times ahead for Rust performance!
- jjtheblunt 4y ago
  alias analysis in Rust is great, but friends worked on it in optimizing compilers in Urbana-Champaign in the early 1990s, so it's possible Rust is its most widespread rollout.
  - jamincan 4y ago
    It's possible to specify no alias in C with the `restrict` keyword, but it isn't a widely used feature. With Rust, a whole bunch of bugs related to it were found and fixed in LLVM, so I think you're correct that it is the most widespread rollout.
nequo 4y ago
Maybe CPU bound code where either your data fits on the stack or you can avoid a lot of copying chunks of the heap by expressing your algorithm in terms of in-place mutation? That is where garbage collected languages seem to be incurring penalties. Not sure what SBCL does specifically. There was this talk last October about efforts at Jane Street to make explicit stack allocations possible in OCaml: https://www.youtube.com/watch?v=yGRn5ZIbEW8 https://www.youtube.com/watch?v=yGRn5ZIbEW8
ww520 4y ago
Not sure how C++ compiler or SBCL compiler utilizes auto-vectorization. The Rust compiler is able to auto-vectorize tight loops to use SIMD without much prompting. E.g. the following uses SIMD automatically. byte_array1.iter().position(|&x| x == digit)
- dgb23 4y ago
  I was shocked when I first heard about SIMD in a online lecture. Not by what it does. But by the fact that apparently every operation uses it, but most just throw away the result.

Is there a well defined class of code, whose expression in Rust, will perform better than what would be emitted by a sufficiently advanced optimizing compiler (say SBCL) ?

skavi 4y ago

Not exactly a class, but there are runtimes of concrete programs written in SBCL and C++ here: https://benchmarksgame-team.pages.debian.net/benchmarksgame/fastest/sbcl-gpp.html https://benchmarksgame-team.pages.debian.net/benchmarksgame/... No direct Rust SBCL comparisons, but generally Rust and C++ perform similarly. There's some discussion on the limitations of SBCL's GC in this thread: https://old.reddit.com/r/Common_Lisp/comments/j8z1j7/how_does_the_gc_in_sbcl_impact_fps/ https://old.reddit.com/r/Common_Lisp/comments/j8z1j7/how_doe...

jjtheblunt 4y ago
thank you!
dgb23 4y ago
It’s interesting to see that a fully dynamic, GC language manages to stay within 1x, 5x, 10x range of C++ in these tests. I haven’t looked at the tests themselves so I can’t speak to their application. But the range of performance for dynamic languages seems to be enormous. Much bigger than the one of static languages.
- tmtvl 4y ago
  > fully dynamic Well, no, it's SBCL. Common Lisp has support for types, but most compilers only use them for optimization, SBCL goes one step further and emits warnings when you mismatch types. And looking at the code, I can see lots of type declarations. It's also interesting to note that the code does not seem to be using SBCL's new SIMD library*, so it could be sped up even more. * <https://github.com/marcoheisig/sb-simd https://github.com/marcoheisig/sb-simd>, see the texinfo file for documentation.

saurik 4y ago

I mean... if the compiler isn't smart enough to see what you were trying to do and generate some ridiculously fast implementation, is it truly worthy of being called "sufficiently advanced"? ;P You just know someone is going to try to add in an LLM-based (note the lack of a V there) compiler pass that says "give me a faster algorithm that does the same thing as this function" (and then all hell will break loose when it starts injecting random bullshit into the function it sort of grokked, or decides your code is for some evil ad company and deletes it on purpose... oh, wait: maybe this is a great idea).

TheDong 4y ago

The most common example is aliasing. Since the rust type system promises that you won't have two mutable aliases to the same data, even data coming from an unknown caller, the compiler can in theory make optimizations that aren't possible in other languages that permit multiple mutable aliases. Especially for values that cross the boundaries of compilation units, the compiler in another language cannot possible have enough information to know if aliasing could occur.

howinteresting 4y ago
I think we haven't even come close to harnessing the full benefits of (1) mutable references can't be aliased, and (2) referential transparency: data behind an immutable pointer never changing no matter how many aliases to it there are. (The exception being UnsafeCell, of course, which can easily be detected.) Exciting times ahead for Rust performance!
jjtheblunt 4y ago
alias analysis in Rust is great, but friends worked on it in optimizing compilers in Urbana-Champaign in the early 1990s, so it's possible Rust is its most widespread rollout.
- jamincan 4y ago
  It's possible to specify no alias in C with the `restrict` keyword, but it isn't a widely used feature. With Rust, a whole bunch of bugs related to it were found and fixed in LLVM, so I think you're correct that it is the most widespread rollout.

nequo 4y ago

Maybe CPU bound code where either your data fits on the stack or you can avoid a lot of copying chunks of the heap by expressing your algorithm in terms of in-place mutation? That is where garbage collected languages seem to be incurring penalties. Not sure what SBCL does specifically. There was this talk last October about efforts at Jane Street to make explicit stack allocations possible in OCaml: https://www.youtube.com/watch?v=yGRn5ZIbEW8 https://www.youtube.com/watch?v=yGRn5ZIbEW8

ww520 4y ago

Not sure how C++ compiler or SBCL compiler utilizes auto-vectorization. The Rust compiler is able to auto-vectorize tight loops to use SIMD without much prompting. E.g. the following uses SIMD automatically. byte_array1.iter().position(|&x| x == digit)

dgb23 4y ago
I was shocked when I first heard about SIMD in a online lecture. Not by what it does. But by the fact that apparently every operation uses it, but most just throw away the result.