Rust Functions Are Weird (But Be Glad)
ฝัง
- เผยแพร่เมื่อ 16 พ.ค. 2024
- Rust takes a unique approach to function types, for both closures and fn items. In this video we'll talk about a way to fit these strange function types into your existing understanding of what types are. Then we'll look at how another language (okay, it's C++) does function types in a way that causes poor codegen in generic higher-order functions if you aren't careful--and how/why Rust avoids this problem.
Compiler Explorer - godbolt.org/
Godbolt code samples from the video:
C++ - godbolt.org/z/xo83Ecfqb
Rust - rust.godbolt.org/z/E5fvaxWPM
Rust Stuff
fn pointers vs. fn items - doc.rust-lang.org/std/primiti...
Fn (the trait) - doc.rust-lang.org/std/ops/tra...
C++ Stuff
Decay - en.cppreference.com/w/cpp/typ...
Boost.TypeIndex - www.boost.org/doc/libs/1_82_0...
std::reduce - en.cppreference.com/w/cpp/alg...
Ranges - en.cppreference.com/w/cpp/ranges
static - en.cppreference.com/w/cpp/lan...
I use the amazing Manim library for animating these videos, and I edit them with Blender and Audacity.
www.manim.community/
www.blender.org/
www.audacityteam.org/
The noinline thing in the C++ code* has caused some confusion, so let me clarify: I used noinline to simulate an example of a higher order function that is not inlined, to show how function pointer types hurt codegen (and lambdas help it) in template instantiations that aren't fully inlined. Template != "definitely inlined"; not being inlined is common for e.g. recursive higher order functions, or doozies like std::sort. While answering comments about this I came up with a clearer example, that doesn't use noinline, where in a reasonable implementation of a commonplace algorithm (in-order binary tree traversal), using a function by name generates worse code than using a lambda:
godbolt.org/z/eqz8EbWM6
The lambda line generates zero code whatsoever (since due to the lambda type it instantiates walk() in a way that is statically known to dispatch to f(), which does nothing, so the whole thing optimizes away), whereas the function pointer line generates an out-of-line instantiation of walk() containing indirect calls.
Here's the Rust version, on the other hand: rust.godbolt.org/z/8xf87G5WT It's a bummer the compiler isn't able to optimize out the control flow completely (note GCC has the same issue with the C++ version), but the important thing is that _inside_ the monomorphizations of calculate, there are no indirect calls to the passed-in function, since its type statically resolves to code that does nothing, for both the named function and closure case. The two monomorphizations produce the same code and then they get deduplicated in the final output as I showed at the end of the video.
I think this example is pretty compelling and if I could replace the one I used in the video with this instead, I definitely might. Even though Rust's codegen isn't a dramatic "home run" over C++'s since rustc doesn't optimize out the pointless recursion, it still supports my argument that Rust's type system lends itself to good codegen in non-inlined higher order functions, whereas C++'s type system works against it.
*I also disabled inlining of calculate() in the Rust code, for the record.
hey, this sounds stupid, but did you delete my reply?
Definitely not--I didn't even see one come through. Apparently TH-cam automatically/inexplicably deletes replies sometimes on a whim: www.reddit.com/r/youtube/comments/11wgrlc/youtube_keeps_deleting_my_comments_for_no_reason/
Sorry about that. Maybe try leaving it as a top-level comment?
Oh... did it have a godbolt link in it? Reading some more, I guess TH-cam might be prone to auto-delete comments with external links (my comments with links seem to all work but I haven't seen anyone else post a comment with links, and another person saying their comment got deleted was supposed to be posting me a link). If you post it again (and really sorry for the hassle and trouble) maybe we can try the thing where you post the link so it doesn't look like a link (i.e. 'godbolt dot org slash 12345').
Can you produce a Rust version of the example you came up with?
I don't think it's fair to disable the C++ channel of communicating caller context and then state that the Rust way of doing it is better because you did that.
Also video corrections are usually pinned. I think this comment is important to understand the video. I got this comment on the second page.
@@_noisecode hi, yes exactly - it had a godbolt link. I'll retry later and thanks for checking :)
Another great video, thank you Logan!
Hi Tris
@@CielMC 😁
hey there! love your vids man, especially the HAM radio one.. getting my license soon :)
@@astroorbis You're too kind! The Rust community are so friendly, I wouldn't have got going without them! ❤
@@NoBoilerplate Rustaceans rise up! For some reason, Obsidian and Rust feel very close although they don't have any actual relation.. might just be your videos :shrug:
Rust: same function copy pasted? Different type.
Javascript: null is an object? Sure.
Null is not an object. The typeof thingy is a bug ^^
@SuperQuwertz It's not a bug, it works exacty as intended. "typeof" is meant to always classify things as part of a data type, always returns something. So if null is not an object, then what it is? Because it certainly is not "undefined". The only remaining type left for it is "object".
No, just null@@Leonhart_93
regarding rustc merging functions: function merging is done by LLVM and clang can do it for C++ too, it's just off by default. you can manually turn it on with `-Xclang -fmerge-functions`
Also if you write:
pub fn f_u32(num: u32) -> u32 { num + num }
pub fn f_i32(num: i32) -> i32 { num + num }
they will also be optimized to be the same function, because of the clever design of two's compliment
Super cool! I hadn't tried this myself. Of course [for completeness] this relies not only on the functions boiling down to the same machine instructions, but also `i32` and `u32` having the same ABI. Putting them in a struct you can end up with different functions with identical machine code, since the functions have different ABIs. rust.godbolt.org/z/Mxnvs5qae
But in debug mode, won't it panic when overflow?
@@Originalimoc In debug mode, two functions will never be optimized into one. In debug mode there are pretty much no codegen optimizations at all, the compiler just generates whatever and gives it to you.
But in release mode, if you use num.checked_add(num), then yes, this optimization indeed won't be possible because checking for overflow is different for signed and unsigned integers.
EDIT: you also can use `-C overflow-checks=yes` to check for integer overflow even in release mode.
I think it because these two functions generate the totally same assembly code, and the types are erased on runtime so Rust doesn't care about which one can fit the type
"Clever design"? You mean the "elegant mathematics of modular arithmetic"?
0xFFFF_FFFF + 1 = 0, therefore 0 - 1 = 0xFFFF_FFFF = -1. (Why people don't make the next step to 0xAAAA_AAAB * 3 = 1, therefore 1 / 3 = 0xAAAA_AAAB = ⅓, even though it's backed by the exact same mathematics, is beyond me.) Also, 0x8000_0000 + 0x8000_0000 = 0, therefore 0x8000_0000 = 0 - 0x8000_0000 = -0x8000_0000. It's just like 0 in that it's its own negative! In fact, it's the _antipode_ of 0 on the number wheel.
In C++ you can pass functions as template parameters using template and then the compiler can optimize it properly. You can think of this as passing the function by value, just as a template parameter instead of a function parameter.
A few people have said this, to which my reply has been that you could, but then you're swimming upstream from convention. Idiomatic higher-order functions in C++ (e.g. the whole STL algorithms library) are written to take functions as regular parameters, not NTTPs. So this isn't really a generalizable piece of advice for how to avoid this pitfall; it only works if the function you are calling has this interface, which the vast majority (in my experience) do not.
Besides... I have to say that "just write your higher order functions using NTTPs to get codegen" _kind of_ just supports my argument that in C++ you often have to do the non-obvious thing in order to get good codegen. It's the same as saying "wrap everything in lambdas"; it's something extra you have to do to get the compiler to generate the code you want, since the default behavior for passing named functions by value is to give you indirect calls. In the video I never said you _couldn't_ get the good codegen, in fact I literally demonstrated that you can with lambdas, I just argued that you have to jump through hoops to get it. This feels _exactly_ like jumping through a hoop to get it.
Also, if you pass the function as a function pointer in Rust (not a generic implementing an Fn trait), you get the same dynamic call as in C++. That's also a case where the easier solution (no generics) is less performant.
@@_noisecode It's easy to make a template class with a call operator that calls a template parameter though, and the syntax would be less of a chore than a lambda
@@Max-ui5gc I'm comparing/contrasting how the type systems have different consequences for generic instantiations in the two languages. Of course if you explicitly say you want indirect calls by taking a function pointer parameter, you will get them.
Great description. Thank you for taking the effort to produce such a quality material!
how u have such deep understanding of such topics is just amazing, hope one would also able to get simple topics to such great depths
have you tried his C++ Godbolt but with a different compiler? Try it with clang.
I'm not sure if this is within the scope of this channel, but making a video on the difference between hardware threads and software threads and how rust affects and is affected by that difference would be really interesting!
I would also like to see this
Brilliant explanation. Thanks for sharing!
gotta say: I love your content. Please keep it up!
Amazing video, great work! I’m sharing this with all my co-workers.
great video, makes me super excited for whatever you have planned for Fn, FnMut and FnOnce!
This guy has very quickly become the subscription that I am most looking forward to his next video
same here
Fascinating, I love learning stuff like this, keep it up!
Good stuff, please keep making these.
This is dope. Totally awesome. Please keep on making these. So fundamental. :)
I already knew Rust's particular "weird" function type approach-but I only already knew it because of those excellent, educational error messages! I'm sharing this with all my Rust students, because it explains it all much better than I have been.
Thank you for the great explanation, particularly with the comparison between passing a function and a lambda to calculate in C++, I found this really helpful.
You are an excellent teacher of programming concepts. The style of your teaching in this video worked very well for me personally. Very high quality content - keep it up. And thank you!!!
ooooh. wow. I would have never thought of that. in other words: rust's functions allow for static dispatch. this enables the compiler to do much smarter optimizations since it knows exactly what function is being passed as an argument. brilliant!
Your last two videos were so good I was eyebrow-raising when I saw a new notification from your channel. Please keep up this great work 👍🏻
Great video!! Knowing about it's pretty cool to see this kind of in-depth content about how types work, and thanks for the compiler explorer tip!!
These rust videos are wonderful. I've barely written any c++ code at all, but it's wonderful to look at how these immensely different approaches to similar-ish languages pan out at compile time.
This is an awesome video! Loved learning more about rust's language design.
I still think higher kinded types would be useful in rust if it could still be performant and safe. Having types based on types signatures. There is a world where having the same signature being the same "type" is very useful. Like defining a functor, monad etc... I know rust is moving towards Generic Associated Types, that helps solve some of these issue's. But, in my mind this function type you are mentioning is just a function ptr more or less. Still an interesting video, thanks!
Yea rust will always be a low level non expressive systems language unless they add HKT and ideally dependent types too.atm it's just better C which isn't much of an accomplishment
Great video! In this little series you started recently, you talk about things that I already (mostly) know. However you show implications much deeper that I would initially find out myself, which makes me rethink about those subjects in a different setting. For example, in the case of your previous video, I knew that returning &Option is a bad idea and more idiomatic way would be to return Option instead. But I did not know all of the reasons *why* that is the case. That is all to say that I love your videos and hope to learn much more from you. Cheers!
amazing, looking forward to the next one
Amazing description, keep it up!
Great video! Thanks for explaining this amazing topic! Only think that I would like to say is that it would have better if you'd have cleared up the whole inlining thing from the comments int the video itself. Keep going with great content!
6:05 I think the best way to think about closures are as tuples, or perhaps tuple + fn-pointer. With the tuple being your captured variables. When getting annoying problems with the borrow-checker, etc. it helps me understand to think of closures as tuples instead.
A closure like `|x: i32| x + y` would be the tuple (i32,) since it captures `y` which is an i32. A closure which captures nothing is the empty tuple () which is zero sized, just like a normal function, so it can be coerced to one. Any other tuple is non-zero sized so needs additional stack space in addition to any potential function pointer making them incompatible.
I think this is a great mental model for closures. Similar to mine but not identical; in my mental model (strongly influenced by my mental model of C++ lambdas), closures are a struct containing each capture (if any), and that struct has a single method that contains the code inside the closure. That method is what's invoked by the call operator.
Note for the record that in terms of layout, the representation of closures in memory is completely unspecified by Rust.
Excelent video. Amazing explanation.
You can get 2 lines of assembly, with moving 20 to eax in C++ with normal function if both funcitons (f and tempalte) are defined as constexpr.
I would love an episode about Result types. I know there's a lot of cool stuff you can do with the ? operator and good functions for operating on them. I just struggle with all of the extra overhead of creating my own error types to return, combining different error types, and so on. Nine times out of ten I end up just reaching for Option because it mostly does what I want, even though I know it's not the right tool for the job.
Using the anyhow crate simplifies this a lot, removing the need for specifying specific Error types
I feel like you could probably get away with `impl std::error::Error` or `Box` as the error type most of the time.
@rsnively take a look at the error-stack crate. error-stack adds a few things that remove boilerplate and make errors nice to look at but what I like about it is that it actually forces you to learn Result the hard way. Using anyhow and similar crates is really nice but you can get away without ever actually understanding the result type. When I was learning I read everything I could find and watched every video but I was still confused. I would think I understood it but then I would have a problem that made me understand that I fundamentally misunderstood. If this guy made a video it would probably be good enough but until he does learning Result the hard way is probably your best option (no pun intended)
Anyhow is a great crate for applications but for libraries I would recommend thiserror since it makes it easy to create actually different errors for the outside, not just return a single error type like you would if you used anyhow
And now, you got your wish. An episode about Result types was released about a day ago. Possibly due to your comment.
Great video man, glad this showed up in my recommended feed even though I really don't need to learn rust since I've been using it in production for like 6 years now.
I had to learn this the hard way when I first learned rust. I come from a functional programming background and when I started writing rust I wrote it like a functional language. I'm sure you can figure out some of the horrible side effects that came with me writing rust that way. I remember being extremely baffled by the fact that we had three different function types via the trait system and then becoming even more baffled when I realized that we actually had infinite function types since every function is its own type. Now of course having used it for 6 years now, I will say that it is a really cool system in practice. I do still have my gripes with the trait system, for example the fact that generics are effectively just trait arguments is still a bit annoying. As somebody with a category theory and lambda calculus background, it's a bit counterintuitive to have generics that don't really work like true generics and functions that don't really work like functions but this really only matters for maybe 1% of use cases in my experience.
Anyhow, keep up the good work mate.
" I do still have my gripes with the trait system, for example the fact that generics are effectively just trait arguments is still a bit annoying. As somebody with a category theory and lambda calculus background, it's a bit counterintuitive to have generics that don't really work like true generics and functions that don't really work like functions but this really only matters for maybe 1% of use cases in my experience. "
Could you clarify, out of curiosity? How does Haskell get generics right and Rust gets them wrong by making them just trait arguments? How does it abide more to Category Theory than Rust? Thank you.
Dude your visual representation of how everything works is fucking amazing. Keep up the great work!
Thank you for the hint. Now that you mentioned it, function item types are like unit structs that implement the Fn traits. That's how it's zero size.
Really enjoying these deep dives into topics I would otherwise not think twice about!
Loved it 👍
Excellent video man. Thank you.
awesome explanation .Thanks a lot
So one can regard functions are basically just unit structs (hence they all have their own unique type), which implement Fn* traits based on their signature. This makes it easier to understand closures as structs whose fields are their capture variables.
It's worth noting that if you want function pointer behavior instead in Rust, you can just specify the argument as a function pointer and not as implementing a trait. Better yet, the compiler is still smart enough to see through it at compile time when it can, even if the generated assembly makes indirect calls.
I.e., your exact example with calculate's signature replaced with fn calculate(bar: fn(i32) -> i32) -> i32 still has main just return 20, but the code generated seems to be literally identical to the C++ example's code. This is probably usually a bad thing though. Still interesting to think about the trade off with function pointer types vs function trait types. I would probably just shorthand the signature you had as fn calculate(bar: impl Fn(i32) -> i32) -> i32 most of the time so it's shorter to write.
Totally agree about doing `impl Fn` for calculate() in real code--I wrote it "longhand" with the `where` clause (and the C++ version with the `requires` clause) for the video so you can visually match up the different key elements of the two versions better (and so the animation between the two looks cooler ;) ).
And yep, if you intentionally opt in to the indirection (by concretely taking a function pointer type as a parameter) you get identical codegen to the "bad" C++ version. I prefer this story over C++'s... you get the nice clean optimized version unless you specifically say you want the indirect version (which you might, for e.g. reducing monomorphizations if a very large number of them is causing problems).
It is nice to watch a Rust video from someone that knows C++ and does good comparisons, instead of a JavaScript developer that misspeaks every time they talk about C or C++. It seems like everyone on the internet comes from front end web development.
Great video! Thanks! ❤
Dude! Beautiful video! 🎉
So THAT's why lambdas can only be assigned to auto-typed variables. The reference is so jargon-heavy, I just couldn't figure out what a "unique unnamed non-union non-aggregate non-structural class type" even is.
This was awesome!
Your videos are incredible
Logan narrates and explains the functionality so well.
6:25 This might be nitpicky, since y is immutable but local captures a reference to y, not a value, unless you use "move". This isn't crucial since it's likely to be inlined anyway but something to keep in mind.
Fair nitpick! You are correct.
Another banger
I still don't get why it is necessary for functions, but not for e.g. integers. Wouldn't it be so great and efficient if the numeral "2" had the type 2? And there was a trait i32 that 2 would implement and then every computation on literals would be done using the type system? And arguments from the outer world would be "dyn i32"?
I feel just like this using the functions in Rust. I think I get that the advantages of using functions like that is far greater than the advantage of using "i32 as trait" approach, and this is the main argument for it. But it makes the whole thing unnatural for me, I would prefer consistency in the type system, the optimizations could be done behind the scenes, not at the expense of design.
Thanks for this comment, I think this is a super interesting point. I honestly think there's a decent argument to be made that the literal "2" should indeed be of type `2`, and only coerced into i32 when it's "type erased" in some way. Some type systems in some languages do exactly that (TypeScript for example). In that mental model, `2` is to `i32` as `{f}` is to `fn(_) -> _`.
From what I can tell, the main downside of extending this to all Rust literals is just the absurd amount of generic monomorphizations that would result. It would mean the compiler would need to statically stamp out a completely different implementation of something like `foo(_: impl std::i32)` for each of `foo(0)`, `foo(1)`, `foo(2)`, etc. Seems sorta like that's simply a bridge too far, although I don't hate the purity, consistency, and elegance of the idea.
@@_noisecode Rust doesn't have type coersion in itself, the traits only have it right? In Typescript, every type is like a set (of objects of this type) so it makes sense, and sets can be made subsets of each other, but in Rust every object is of exactly one type, making the whole thing asymmetrical...
Sure, that's a fair distinction to draw between TypeScript and Rust's type systems. For the Rust case, I was thinking that a type like `2` would be a ZST that uniquely identifies the value of 2 irrespective of type, but it coerces into a concrete integer type when you nudge it.
let x: i32 = 2; // the value of type 2 is coerced/erased to i32
let x: u8 = 2; // coerced/erased to u8
This would be analogous to how fn item names are coerced to fn pointer types if you give them a little nudge, as I show in the video:
let x: fn(_) -> _ = f; // the value of type {f} is coerced to fn pointer
@@_noisecode The illogical conclusion to this line of reasoning is to give every value its own type, and anything that used to be a non-zero-sized type is now a trait. This has the slight issue that typechecking would be undecidable!
amazing video!!
Amazing videos man.. just discovered rust and your channel, loving it. Which tool are you using to build your videos? Super smooth and enjoyable.
Thank you so much! I use the Manim library for the animations, check the description for more info.
Oh, man. Your vidos are so good. How about series dedicated to all Rust's features unshugaring. Moving, borrowing, smart pointers, etc. Performance implications using those and how compiler optimize those.
Your last point is very dubious (to not say misinformed). C++ does function merging (or "identical COMDAT folding") but it does so at link time, not compile time.
The reason is that with Rust, when you compile your file, it's considered a complete crate (AFAICT), while C++ consider is just an object file and doesn't do any things that could break the public ABI (since it can't know how the code will be used, unlike the linker).
that's really interesting!
though the "functional programmer" in me absolutely hates it :D
the compiler could technically do that in the background, without exposing it in the type system - simply by monomorphizing based on the identity of the function arguments to the call. (this wouldn't work for functions assigned to locals, but some rather simple analysis during type inference could identify those cases, where the variable can only refer to exactly one function.)
i was also quite surprised by how monomorphizations are supposedly skipped, if the functions are identical modulo optimization. this would inherently sequentialize code generation and optimization (to some degree). the observed effect, that `f` and `f_prime` used the same machine code could also be explained by function deduplication done by llvm.
however this would be after monomorphization and would therefore not reduce compile times. you could perhaps test this by generating a huge number of functions and making calls to a generic function for each of those functions, then compare the compile times for identical/different functions.
That's an interesting idea! I wonder indeed how plausible it would be for the compiler to do this monomorphization trick behind the scenes while telling the white lie that all functions do have the same type. Good food for thought!
On the other hand, then we're back in "functions are callable because they just... are" territory. A point I make in the video is (paraphrased) that calling a function is an _operation_ you perform on a function value, so the correct abstraction for it is a trait, just like any other operation you do to a generic value (e.g. std::ops::Add). I also like that the type system protects you from unnecessary dynamism; you only get a function pointer if you opt in to one (although to be fair, it is easy to accidentally opt into one, since fn items coerce to fn pointers so easily).
And you're right, I glossed over the point that the function deduplication stuff doesn't help with the compile time issue, just the final binary size. It does indeed have interesting consequences re: sequentializing codegen. Thanks for the comment. :)
@@_noisecode >telling the white lie that all functions do have the same type
I think, such thing contradicts the idea of Rust being explicit and low-level.
Great video!
Thank you. Your analysis is very clear and useful.
Do you know how haskell typeclasses work? I'd be very interested if you did a comparison of those to Rust traits, in terms of how dynamic dispatch and monomorphisation work. Obviously Haskell doesn't tend to give guarantees about the binary representation of things in the same way as rust and C++.
Interesting video, but I'd have appreciated it if you'd linked to your code so that we could see it on godbolt without having to retype it ourselves. I wasn't able to replicate your C++ results with my initial example and having to retype what you wrote exactly and then carefully look at what settings you were using in order to make sure that I was right about why we got different results was tedious.
This is a compiler problem, not a language one. gcc does the correct optimization once you give the compiler permission to do full monomophization by making both `f` and `calculate` be `constexpr`. Output is the same as the rust code, even on lower optimization levels. Works across multiple architectures too.
I'm not sure why clang specifically has trouble with this code and can only optimize the lambda version. But this is a compiler issue and not a language one. (It could also be user error. I'm not that familiar with the details of clang code gen.)
I'm also not sure why making `f` have static storage class would be expected to do anything here (and it doesn't change the generated code). I'm not even sure that your explanation of `static` is even correct in this context and it sounds like you mean to be talking about `constexpr`. (Though maybe in editing for brevity, some nuance involving `static` got lost?)
Very valid feedback! I'll put some links to the godbolt examples in the description.
Even considering your points, I do still argue this is a language problem. Not all code can be constexpr, and besides, constexpr is a language construct, not a compiler switch; my point stands that it's a language problem that the 'default' semantics don't let the compiler optimize your code completely (unlike the default semantics in Rust) and you have to manually opt in to semantics that do (like constexpr or lambdas).
My point about f being static was that, normally, you expect a tiny static function to probably be able to disappear/be optimized out completely (note that the out-of-line definition of f DOES get optimized out completely when we wrap it in a lambda). But due to needing its address when it's used as a function pointer, it can't be optimized out in that version of the code. I just rewatched that section and I don't *believe* I misspoke in any way about the semantics of `static` functions.
Thanks for watching and for the discussion. :)
Godbolt links in description! Thanks again for asking, should've put them there in the first place.
@@_noisecode Thanks for updating it so quickly!
FWIW, I played with this some more and it seems like clang and gcc treat "noinline" differently. Clang takes you quite literally and just refuses to do the optimization since it has the effect of inlining it and then eliminating the function as dead code. (What clang does is probably the thing that people generally intend when they use that attribute in real code.)
If you get rid of that attribute, the optimization works as it should even with minimal optimizations enabled. Both clang and gcc will be able to treat the functions as constexpr without having to force it by declaring it specifically.
So, it's not so much opt-in as opt-back-in (after opting-out). There are probably cases where constexpr is actually needed to trigger the optimization, but since clang and rust will use the same llvm analysis for that, I don't think you'll actually see a difference in practice.
If you could construct one, I'd be interested in seeing it, but so far, I haven't managed it. I suspect that Rust would benefit if the compiler needed to do an alias analysis on the arguments of a higher order function that took multiple functions as arguments. But haven't been able to construct a working example.
And since I can't actually think of a distinguishing case, I'm not confident that I can say that rust being nominally opt-out is "better" than c++ being nominally opt-in. That would depend on what opting out with the rust code looked like and how often you ended up with build time problems or other issues with degenerate monomorphization compared to the times where the annotation or code change in C++ was complex or non-obvious. We are already dealing with a corner case of a corner case at this point. So it's hard to say.
As for `static`, what you said is correct. Putting it on that function tells the compiler that it won't be referenced from any other file. This shouldn't impact the optimizations being done, only whether the compiler *also* emits the code for the function itself or if it has permission to eliminate it as dead code if it is inlined everywhere in the current file. And this is what actually happens on both gcc and clang. Using `static` there isn't something you'd normally see in the wild, so it stood out as odd. But having rewatched, I don't think there's an error in what you said.
This example optimizes down to nothing if you take away noinline, yeah, which is of course why I added it: I was trying to simulate a case where you have a higher order function that doesn't get inlined. One such function that's extremely common is std::sort (which typically doesn't get inlined). You don't have to manually opt out like I did to find common real world examples of compilers choosing not to inline function template instantiations, where then the types they are instantiated with matter for your codegen. (An out-of-line std::sort instantiated with a custom predicate that's a lambda will have that lambda inlined into its definition, whereas an out-of-line std::sort instantiated with a function pointer will have to make an indirect call for every element comparison).
(Huge amount of codegen here but you can see the two instantiations of __introsort [line 56 and then 1437] are quite different--the function pointer one has lots of `call`s that the lambda one does not: godbolt.org/z/1Er3nf6bT Code for `greater` is also generated even though it's marked static since its address is needed by the function pointer instantiation.)
I think constexpr is sort of unrelated to the matter at hand by the way. It may affect codegen in the way you're seeing because constexpr implies `inline`, but aside from that, a function being marked constexpr shouldn't affect how it's optimized when it's not being used as a constant expression (thus making its constant evaluation optional), except compilers _may_(?) be slightly more inclined to constant evaluate it (which isn't really an optimization and more of a language semantic thing that happens in the compiler frontend before anything gets to e.g. LLVM).
`static` is very common on functions in .cpp files--so I'm not sure what you mean that it's not something you'd see in the wild. Often in C++ they're put in anonymous namespaces instead, but `static` is another very typical way to do it, and some coding guidelines (e.g. LLVM's in fact) actually require `static` instead of anonymous namespaces for internal helper functions. You're right that `static` won't affect how the function is inlined etc., just whether its definition gets eliminated as dead code. Apologies if I suggested otherwise.
Here's a simpler and more compelling example:
godbolt.org/z/7rd79T1oT
Node::walk() traverses a binary tree, visiting each node with a predicate. There are no `noinline` attributes in sight. The call using the lambda (so the one where walk() is instantiated with a predicate that can be resolved statically based on type information) is optimized out completely and is nowhere in the generated code. The call using the function's name directly generates a bunch of code featuring indirect calls.
a video on iter trait and rayon crate would be cool
A high-quality channel with only 6.33k subs?
nice
What a great video!
Something I did not know that I wanted to know.
Thank you!
Very interesting.
6:20 well, it could support currying. When passing y to that clojure it could wrap inside a function and compose it with the clojure. Or something on these lines
Excellent piece of work! The premise is posited; the observations are presented; experiments are made; the conclusions are drawn! I am not really a beginner with Rust, but this video has been a real addition to my knowledge of Rust compiler works! Thank you, @Logan.
14:20 C++ compilers actually do just that. Same with C++20 coroutines despite being even more complicated and indirect.
If you really need to generate the function per object and not per type, just ask it to the compiler:
```cpp
#include
#include
#include
template
[[gnu::noinline]]
int calc()
requires std::invocable
{
auto r = std::views::iota(0, 5)
| std::views::transform(f)
| std::views::common;
return std::reduce(r.begin(), r.end());
}
static int f(int x) { return x + x; }
int main() { return calc(); }
```
Still an interesting design choice en rust's end tho, but the example is just not great imo.
You could change calculate's API so you have to pass the function pointer as a NTTP in this case yeah, but I don't see this is as a generalizable solution at all. For example, none of the STL algorithms are designed to work this way. Idiomatic higher order functions in C++ accept their functions as values, which is the pattern that has the shortcomings I showed. There are ways to get the good codegen, yes--NTTPs are one, lambdas are another as I showed--but resorting to NTTPs is actually just support for my argument that in C++ you have to do the less-obvious thing to get the good codegen, because the defaults are working against you.
It's fair to critique this example though; check out the pinned comment for a better one.
Google algorithm brought me here and...
Immediately 'liked' and 'subscribed'
Thanks for the content, my friend.
So, in rust function type is some mix of Id-location of a function, while in cpp it is just a signature? That’s some clever stuff going on there
I love these videos so much, I'm a huge geek for programming language design, and Rust is just a so beautifully constructed language.
I know I'm just adding more complexity to the matter, but my first approach would have been to write the C++ version as taking a function, not a typename, since this is what you want:
template int calculate() { return F(1) + F(2); }
Very good explanations of practical implications in this video, just as it was for "&Option vs Option" one. No other youtuber gets even close in that regard :) Keep it up!
great video, thank you ♥
Hey I was just wondering - Why is f_prime type different than f type in the beginning, even if they are both the same code, and the compiler optimizes these calls?
it uses the type of f_prime to refer to the code of f, but you wouldn't want the assert to change its result just because of an implementation detail of the compiler happening to reduce your function to another
Yep--in terms of the language's semantics, it's canon that they are different types, even if they happen to collapse down to the same thing after optimization. Sorta same way u32 and i32 are different types at the language level, even though after compilation they are indistinguishable (more or less).
making these types similar to gensyms probably is the same reason scheme macros are also hygienic (namespace splatting) -- but instead for typing functions and making sure you don't lead to weird behaviour as a result of them being 1st class values
This was very interesting, but I ended up watching it backwards. First i jumped to the practical application, then I went back to warch the rest. Seeing the ugly "wrap it in lambda" idiom made the rest make sense. Thank you for the table of contents!
Nice explanation. However in real code you almost always want to use function composition because you have different combinations of functions at runtime. Thus I strongly suspect it's not actually that common (in either C++ or Rust) to be passing functions in this static fashion, except maybe for generating constants. It would have been nice to see what Rust did in the dynamic case.
I often use `x.map(T::from)`. In fact, there is a clippy lint for that called `redundant_closure`.
Exactly. In Rust I try to used named functions like T::from wherever I can, because it's more elegant (it's kind of 'point-free style'). In C++ this could be detrimental to codegen, whereas in Rust it's not.
@@user-nw8pp1cy8q That's a good point about map(). Applying a function over a collection is a case where you'll combine named functions explicitly. Maybe it's not as unlikely as I thought.
In real Rust you can write things like launch::()
MyApp implements a trait that launch knows about, which probably has multiple trait methods. Imagine it's a GUI framework and MyApp has several methods to handle initialization, repaint, input events, etc.
An OO framework would probably express this interaction with an abstract class, but Rust doesn't have inheritance.
When I want to pass a callable thing that can be called in multiple ways I implement a trait. Same basic thing as passing a closure, there's just more of it.
In a traditional OO approach I would probably need to create an instance of MyApp and then maybe I call .run(). But in Rust the library can take responsibility for creating (and owning) the instance - which can be very useful. launch only needs to be told the type.
In turn, simple imperative C (no C++) inlines the function pointer, lol.
It just becomes something like:
mov eax, 20
ret
I didn't try with C++ but i believe the results would be the same if we use more imperative programming in C++. I think the problem here is that C++ is trying to be what it cannot be. C++ is an (apparently) evolution of C, and C is imperative, so is C++. The whole thing with C++ with RAII and other things it feels like Bjarne Stroustrup tried to make things feel more like stack allocated memory, as you do not need to handle (much) the destruction of the memory, but it became distracted with functional programming and it became what it is now. As such, Go is a better "evolution of C" than C++, although i don't like GC.
actually c++ with the lambda only got optimized, because f got inlined into the lambda, for more complex functions, c++ might not optimize it fully. However the dynamic dispatch could be optimized away, since the lambda knows which function its calling and the lambda itself can still be inlined.
Feels like something LLVM IR compiler can be improved on C++ side.
7:54 I think I have a better way to explain the zero-size types of functions.
Types tell the compiler exactly how to implement operations. rustc knows many different ways to translate `+` - the machine language instructions for adding u16 are different from adding u32. Or the operator could be overloaded.
The function-call operation is overloaded too. Calling f and calling g are different instances of the "call something" operation. This is especially true if the compiler chooses to inline the call.
(But I assume you're about to talk about static dispatch and inlining, so I'll watch the rest.)
Great video, I learned a few things
Forgive me, I'm from C++, but what about things like dependency injection, where it's desirable to have indirect calling? Is there solution there still to use function pointers?
If you do want indirect calls, it's idiomatic in Rust to use something like `dyn Fn(i32) -> i32`, which is essentially a type-erased dealio that calls the function through a vptr. Basically it's just a more generalized function pointer that can also call closures with state. If you want to own the callable, a la std::function in C++, you typically use `Box i32>`. If you just need to call it but not own it (a la something like llvm::function_ref in C++) then you use it by reference, e.g. `&dyn Fn(i32) -> i32`.
It's amazing that in 2023, you still have to pass itrable objects as two arguments (.begin() and .end) in C++.
For many algorithms, you don't: en.cppreference.com/w/cpp/algorithm/ranges
The algorithms like std::reduce didn't get Ranges versions in C++20, so I had to use .begin() and .end() for the std::reduce call. But C++23 is evidently getting Range-ified reduction algorithms that will make this code prettier: en.cppreference.com/w/cpp/algorithm/ranges/fold_left
great video
14:28 Hmm... I thought that CPU do have indirect branching prediction and that GCC do have -findirect-inlining which should work for templates and code within same module.
-findirect-inlining is an optimization that tries to _fix_ the issue I present in the video: C++'s type system causing indirect calls in higher order functions when you use a plain function name. Needing to turn on a special optimizer switch is kind of the same as needing to wrap the function in a lambda; it's an extra step you need to take to get good codegen because C++'s language semantics give you indirect calls in HOF by default, whereas Rust's give you static dispatch by default and you opt in to dynamism, rather than having to opt in to good codegen like in C++.
Funny to see this weird moments with c and c++ background
I'd like to see the same experiment but with the STL's function class because it is considered bad practice to deal with raw pointers in c++ in general, not just with the function pointers.
Feel free and try it out, there are godbolt links to the experiments in the description! I expect the codegen using std::function to be pretty similar to the function pointer version or slightly worse. std::function involves type erasure so it probably has to do a virtual call or some other form of an added indirection.
FWIW, function pointers in C++ aren't nearly as dangerous as raw pointers to object, since there's not really the same puzzle of ownership--functions (usually) exist for the life of the program so you don't have to worry about stuff like double deletion and you can be pretty sure they won't dangle unless you're doing some very advanced stuff. You do have to worry about null checks, but the same is true for std::function.
std::function is generally worse compared to lambdas or manual callable structs (with overriden operator()) because they are opaque.
std::function is powerful but that power comes at a price.
Creating a std::function from a lambda will give you a single indirection on the calls and additionally will give you indirect calls to a "manager" function whenever the std::function is copied or destroyed.
Creating a std::function from a function pointer will give you a double indirection!
Top !🎉
So every function is a singleton. Design patterns are back, baby!
so, if i understood this correctly, if you want to avoid the monomorphizations in rust, you can explicitly cast your function to an fn pointer and so avoid the code duplication in the compiled binary at the cost of getting an indirect call?
Yep! Although in my experimentation, even if you do this rustc will still sorta sidestep you sometimes and generate a fully monomorphized function even when you handwrote the indirection. I haven’t looked into why and it could be just because somehow it was smarter than whatever my experiment code was, and in “real” code it would keep the indirection in there.
So.... it turns down to inlining and optimizing your code again? Well, what if you have a library and the function call (that is an upper function that calls a passed function) and you do NOT want to optimize and inline so when the new version of the function is out, you don't have to recompile all the programs that use it?
Another way to fix this problem is to have 2 different function pointer types. The regular function pointers and another one that when used, it will signify that the function may or may not be inlined (but the choice is to the caller). After that, the caller may choose to pass a function as any of the 2 types and the compiler will do its job! Anonymous functions (lambdas) can also be choose which of the types they want to be.
I'm planning to implement this syntax for my programming language. I'll never understand why these new languages make things so complex and complicated when they could had created a simpler design...
Before I'm out, I will type the quote of the greatest programmer to have ever lived, Terry Davis! Rest in peace legend!
"An idiot admires complexity, a genius admires simplicity!"
It would be highly interesting how purely functional languages implement this...
From a mathematical viewpoint there is no difference between types and signatures, at least in most lambda calculi i have worked with...
Every Thing is a function and its type is its signature...
The original lambda calculus may be a bit more janky than that, since the untyped lambda expression are so polymorphic that their signatures arent even decidable sometimes.
Do you use Manim for visualization?
Yep! I always give credit in the description. :)
@@_noisecode amazing)
4:26 The first line saying "different fn items have unique types" is saying exactly what you want to add to the message.
Subscribed.
Another absolutely great video!!! I loved to see the C++ quirks and exactly these (endured them for too long) let you admire Rust so much more!
Btw I would looove to see an education video about rebarrowing etc, its a topic which lurks in the dark.. 😂
Keep in mind that the codegen would have been identical in his example if he used a lambda, or a constexpr that has been assigned a lambda, which would be the true equivalent of the rust code
@@ludoviclagouardette7020 Actually no, not necessarily. Lambdas decay into function pointers, which are just pointers. You CAN do this in a strongly typed and efficient way using c++20 concepts, and then you get the "performance" you need.
what happens with dyn Fn? do those get optimized or no