News for hackers. Stuff that matters.
Re:Type-erased generic functions for C: A modest non-proposal by mseepgood on Thursday October 03, 2024 @06:22AM (#41729204)
> Looks very similar to Go generics, which also don't support monomorphization.

That's not true. Go's generics are monomorphized, when it makes sense (different shapes) and not monomorphized when it doesn't (same shapes). It's a hybrid approach to combine the best of both worlds: https://go.googlesource.com/proposal/+/refs/heads/master/des...

Re:Type-erased generic functions for C: A modest non-proposal by cherryteastain on Thursday October 03, 2024 @07:16AM (#41729511)
Go does monomorphization in a rather useless manner from a performance perspective because all pointers/interfaces are essentially the same "shape". Hence you still have no inlining and you do not avoid the virtual function when any interfaces are involved as detailed in https://planetscale.com/blog/generics-can-make-your-go-code-...

C++ fully monomorphizes class/function templates, and therefore incurs 0 overhead while unlocking a ton of inlining, unlike Go.

Re:Type-erased generic functions for C: A modest non-proposal by tialaramex on Thursday October 03, 2024 @08:31AM (#41730129)
Yup. The most classic example of this is that in both Rust and C++ we can provide a method on some type which takes a callable and instead of a single implementation which runs off a function pointer, the compiler will separately monomorphize individual uses with lambdas to emit the optimised machine code for the specific case you wrote often inline.

For example Rust's name.contains(|c| c == 'x' || (c >= '0' && c <= '9')) gets you code which just checks whether there are any ASCII digits or a lowercase latin x in name. If you don't have monomorphisation this ends up with a function call overhead for every single character in name because the "shape" of this callable is the same as that of every callable and a single implementation has to call here.

Is Go's choice a valid one? Yes. Is it somehow the "best of all worlds"? Not even close.

Re:Type-erased generic functions for C: A modest non-proposal by foldr on Thursday October 03, 2024 @12:19PM (#41732131)
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). 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

Re:Type-erased generic functions for C: A modest non-proposal by tialaramex on Thursday October 03, 2024 @12:48PM (#41732450)
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 ?

Re:Type-erased generic functions for C: A modest non-proposal by foldr on Thursday October 03, 2024 @01:21PM (#41732759)
I linked an example here in an edit to my original post: 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.

Re:Type-erased generic functions for C: A modest non-proposal by tialaramex on Thursday October 03, 2024 @01:50PM (#41733030)
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?
Re:Type-erased generic functions for C: A modest non-proposal by foldr on Thursday October 03, 2024 @01:53PM (#41733050)
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.
Re:Type-erased generic functions for C: A modest non-proposal by tialaramex on Thursday October 03, 2024 @06:21PM (#41735710)
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.

Re:Type-erased generic functions for C: A modest non-proposal by foldr on Thursday October 03, 2024 @07:01PM (#41735982)
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)

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/GoInlin...

Re:Type-erased generic functions for C: A modest non-proposal by neonsunset on Thursday October 03, 2024 @08:44AM (#41730243)
Yup, much like Rust and C# (with structs).
Re:Type-erased generic functions for C: A modest non-proposal by jchw on Thursday October 03, 2024 @09:24AM (#41730568)
Go developers didn't really want C++ templates. C++ templates are very powerful, but while they unlock a lot of runtime performance opportunities, they are also dog-slow for compilation.

What Go developers wanted was a solution to the problem of having to repeat things like simple algorithms (see e.g. slice tricks) once for each type they would ever need to operate on, and also a solution to the problem of confusing interfaces dancing around the lack of generics (see e.g. the standard sort package.) Go generics solve that and only that.

Every programming language has to choose how to balance and prioritize values when making design decisions. Go favors simplicity over expressiveness and also seems to prioritize keeping compile-time speeds fast over maximizing runtime performance, and their generics design is pretty consistent with that.

The Go generics design did not win over anyone who was already a Go hater because if you already didn't like Go it's probably safe to say that the things Go values most are not the things that you value most. Yes, everyone likes faster compile times, but many people would prefer faster runtime performance. Personally I think that it's worth balancing runtime performance with fast compile times, as I prefer to keep the edit-compile-test latency very low; that Go can compile and run thousands of practical tests in a couple seconds is pretty useful for me as a developer. But on the other hand, you may feel that it's silly to optimize for fast compile times as software will be ran many more times than it will be compiled, so it makes sense to pay more up front. I know some people will treat this like there's an objectively correct answer, even though it's pretty clear there is not. (Even calculating whether it makes sense to pay more up front is really, really hard. It is not guaranteed.)

So actually, I would like type erasure generics in C. I still write some C code here and there and I hate reaching into C++ just for templates. C is so nice for implementing basic data structures and yet so terrible for actually using them and just this tiny little improvement would make a massive, massive difference. Does it give you the sheer power that C++ templates give you? Well, no, but it's a huge quality of life improvement that meshes very well with the values that C already has, so while it won't win over people who don't like C, it will improve the life of people who already do, and I think that's a better way to evolve a language.

Re:Type-erased generic functions for C: A modest non-proposal by foldr on Thursday October 03, 2024 @12:16PM (#41732092)
You can use value types rather than pointers/interfaces if that's what you want.