4 ms·

This is just inlining of a function/method parameter. It only has anything at all to do with monomorphization in Rust because lambdas have their own special unw

by foldr 2y ago

This is just inlining of a function/method parameter. It only has anything at all to do with monomorphization in Rust because lambdas have their own special unwritable types. A good modern C compiler will be able to inline calls to function pointer arguments without doing monomorphization (example here: https://news.ycombinator.com/item?id=31496445 https://news.ycombinator.com/item?id=31496445). I doubt the Go compiler does such aggressive optimization, but there is nothing to stop it in principle. Edit: I think the Go compiler might actually be smart enough to inline in this kind of case. See line 113 of the assembly listing here: https://godbolt.org/z/8qGdzeKcG https://godbolt.org/z/8qGdzeKcG

tialaramex 2y ago
In C++ the lambda function also has an unnameable type, indeed unlike Rust that's a unique property, all of Rust's functions have such types whereas in C++ the named functions have a type based on their signature. Do you have an example of a "good modern C compiler" which inlines the function? Presumably this is a magic special case for say, qsort ?
- foldr 2y ago
  I linked an example here in an edit to my original post: https://news.ycombinator.com/item?id=31496445 https://news.ycombinator.com/item?id=31496445 The broader point is that compilers (including the Go compiler, it seems) can and do make this kind of optimization via inlining, and that this doesn't have much to do with any particular approach to generics.
  - tialaramex 2y ago
    The example seems to just be a boring case where the compiler can compute the answer for your entire program, which isn't interesting at all. Maybe you linked the wrong example?
    - foldr 2y ago
      It can compute the answer because it’s able to inline the function call made via the function pointer argument to 'find'. But if you don’t like that example for some reason, look at the Go example I linked above.
      - tialaramex 2y ago
        The Go example seems like we're giving the game away much the same as the C. Sure enough if I factor out the predicate, the compiler just... doesn't inline it any more. "Hopefully the optimiser will spot what I meant and optimise it". OK. We got into this with the claim (never substantiated) that this works for the C library function qsort, which is notable because it does indeed work for the C++ and Rust standard library sorts which are done the way I described.
        foldr 2y ago
        Monomorphization does not guarantee inlining of lambdas. You can perfectly well output a monomorphized version of the 'contains' method specialized to the type of a particular lambda argument and then call this lambda on each loop iteration in the generated code. (Rust's assembly output is pretty impenetrable compared to Go's, but I believe this is exactly what happens if you compile something like this without optimizations: https://godbolt.org/z/qaYbGMMzM https://godbolt.org/z/qaYbGMMzM) It does not surprise me that Rust inlines more aggressively than Go, but that doesn't have anything much to do with differences between Rust and Go generics or type systems. Adopting the type-level fiction that every lambda has a unique type does not fundamentally make inlining any easier for the compiler. It may well be that in Rust the monomorphization triggered by this feature of the type system leads to more inlining than would otherwise happen. But that is just an idiosyncrasy of Rust. Compilers can do whatever kind of inlining they like regardless of whether or not they think that every anonymous function has its own unique type. Edit: One further thing that's worth noting here is that the Go compiler does do cross-module inlining. So (unlike in the case of a typical C compiler) it is not the case that the kind of inlining we've been talking about here can only occur if the function and the lambda exist in the same module or source file. https://utcc.utoronto.ca/~cks/space/blog/programming/GoInlinesAcrossPackages https://utcc.utoronto.ca/~cks/space/blog/programming/GoInlin...

by foldr 2y ago

tialaramex 2y ago

In C++ the lambda function also has an unnameable type, indeed unlike Rust that's a unique property, all of Rust's functions have such types whereas in C++ the named functions have a type based on their signature. Do you have an example of a "good modern C compiler" which inlines the function? Presumably this is a magic special case for say, qsort ?

foldr 2y ago
I linked an example here in an edit to my original post: https://news.ycombinator.com/item?id=31496445 https://news.ycombinator.com/item?id=31496445 The broader point is that compilers (including the Go compiler, it seems) can and do make this kind of optimization via inlining, and that this doesn't have much to do with any particular approach to generics.
- tialaramex 2y ago
  The example seems to just be a boring case where the compiler can compute the answer for your entire program, which isn't interesting at all. Maybe you linked the wrong example?
  - foldr 2y ago
    It can compute the answer because it’s able to inline the function call made via the function pointer argument to 'find'. But if you don’t like that example for some reason, look at the Go example I linked above.
    - tialaramex 2y ago
      The Go example seems like we're giving the game away much the same as the C. Sure enough if I factor out the predicate, the compiler just... doesn't inline it any more. "Hopefully the optimiser will spot what I meant and optimise it". OK. We got into this with the claim (never substantiated) that this works for the C library function qsort, which is notable because it does indeed work for the C++ and Rust standard library sorts which are done the way I described.
      - foldr 2y ago
        Monomorphization does not guarantee inlining of lambdas. You can perfectly well output a monomorphized version of the 'contains' method specialized to the type of a particular lambda argument and then call this lambda on each loop iteration in the generated code. (Rust's assembly output is pretty impenetrable compared to Go's, but I believe this is exactly what happens if you compile something like this without optimizations: https://godbolt.org/z/qaYbGMMzM https://godbolt.org/z/qaYbGMMzM) It does not surprise me that Rust inlines more aggressively than Go, but that doesn't have anything much to do with differences between Rust and Go generics or type systems. Adopting the type-level fiction that every lambda has a unique type does not fundamentally make inlining any easier for the compiler. It may well be that in Rust the monomorphization triggered by this feature of the type system leads to more inlining than would otherwise happen. But that is just an idiosyncrasy of Rust. Compilers can do whatever kind of inlining they like regardless of whether or not they think that every anonymous function has its own unique type. Edit: One further thing that's worth noting here is that the Go compiler does do cross-module inlining. So (unlike in the case of a typical C compiler) it is not the case that the kind of inlining we've been talking about here can only occur if the function and the lambda exist in the same module or source file. https://utcc.utoronto.ca/~cks/space/blog/programming/GoInlinesAcrossPackages https://utcc.utoronto.ca/~cks/space/blog/programming/GoInlin...