Hacker News Reader

Comment by cherryteastain | Hacker News Reader

Looks very similar to Go generics, which also don't support monomorphization. Sadly, Go's generics are a bit of a basket case in terms of usefulness since they don't support compile time duck typing like C++ generics, but I imagine it won't be a problem for C since it does not have methods etc like Go. That said, I personally feel like that's precisely why I feel like this proposal adds little value compared to macros, since runtime dispatch is bad for performance (very important for most uses of C) and the convenience added is small because C only supports a few primitive types plus POD structs without embedding/inheritance.

View on HN

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

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.

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.

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

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 ?

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.

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?

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.

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.

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

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.

You can use value types rather than pointers/interfaces if that's what you want.

Yup, much like Rust and C# (with structs).

> Sadly, Go's generics are a bit of a basket case in terms of usefulness since they don't support compile time duck typing like C++ generics,

What are you referring to here? Code like

    func PrintAnything[T Stringer](item T) {
     fmt.Println(item.String())
    }

looks like type-safe duck typing to me.

The example you gave is the most trivial one possible. There is 0 reason to write that code over PrintAnything(item Stringer). Go doesn't even let you do the following:

  auto foo(auto& x) { return x.y; }

The equivalent Go code would be

  package main

  import "fmt"

  func foo[T any, V any](x T) V {
     return x.y
  }

  type X struct {
       y int
   }

  func main() {
       xx := X{3}
       fmt.Println(foo[*X, int](&xx))
   }

which does not compile because T (i.e. any) does not contain a field called y. That is not duck typing, the Go compiler does not substitute T with *X in foo's definition like a C++ compiler would.

Not to mention Go's generics utterly lack metaprogramming too. I understand that's almost like a design decision, but regardless it's a big part of why people use templates in C++.

Interesting, thank you for the example. I'm mostly used to how Rust handles this, and in its approach individual items such as functions need to be "standalone sane".

    func foo[T any, V any](x T) V {
        return x.y
    }

would also not fly there, because T and V are not usefully constrained to anything. Go is the same then. I prefer that model, as it makes local reasoning that much more robust. The C++ approach is surprising to me, never would have thought that's possible. It seems very magic.

Lots of C++ is driven by textual substitution, the same mess which drives C macros. So, not magic, but the resulting compiler diagnostics are famously terrible since a compiler has no idea why the substitution didn't work unless the person writing the failed substitution put a lot of work in to help a compiler understand where the problem is.

No, the equivalent go code would be

  package main

  import "fmt"

  type Yer[T any] interface {
      Y() T
  }

  func foo[V any, X Yer[V]](x X) V {
     return x.Y()
  }

  type X struct {
       y int
  }

  func (x X) Y() int { return x.y }

  func main() {
       xx := X{3}
       fmt.Println(foo(&xx))
  }

It is not equivalent because, per the monomorphization discussion above, putting an interface in there means that you incur the cost of a virtual function call. The C++ code will compile down to simply accessing a struct member once inlined while the Go code you wrote will emit a ton more instructions due to the interface overhead.

Depending on which implementation you use, the following may produce the same instructions as the example above. Go on, try it!

     package main

     import "fmt"

     func foo(x *X) int {
          return x.y
     }

     type X struct {
          y int
     }

     func main() {
          xx := X{3}
          fmt.Println(foo(&xx))
     }

Now, gc will give you two different sets of instructions from these two different programs. I expect that is what you are really trying and failing to say, but that is not something about Go. Go allows devirualizing and monomorphizing of the former program just fine. An implementation may choose not to, but the same can be said for C++. Correct me if I'm wrong, but from what I recall devirtualization/monomorphization is not a requirement of C++ any more than it is of Go. It is left to the discretion of the implementer.

Tried it out in godbolt, yes you are right that with the above example gc is able to realize that

  func foo[V any, X Yer[V]](x X) V

can be called with only one type (X) and therefore manages to emit the same code in main_main_pc0. It all falls apart when you add a second struct which satisfies Yer [1], which leads the compiler to emit a virtual function table instead. You can see it in the following instructions in the code with a second implementation for Yer added:

  LEAQ    main..dict.foo[int,*main.X](SB), DX
  LEAQ    main.(*X).Y(SB), CX
  CALL    CX

[1] https://godbolt.org/z/zTco4ardx

Was it really necessary to try in gc...? We already talked about how it produces different instructions for the different programs. Nice of you to validate what I already said, I suppose, but this doesn't tell any of us anything we didn't already know.

The intent was for you to try it in other implementations to see how they optimize the code.

> compile time duck typing

The term you are looking for is structural typing.

It isn't though. C++ templates are duck-typed. Structural typing is two structs with the same structure are the same type. Duck typing is when you check if it has a quack field.

For a template like this:

    template<typename T> T max(T &a, T &b) { return a > b ? a : b; }

Structure is entirely irrelevant. All that matters is that T have `>` or the spaceship defined for it.

C++ templates get incredibly complex, but at no point is the type system structural. You can add a series of checks which amount to structural typing but that isn't the same thing at all.

By common definition, structural typing and duck typing end up being the exact same thing, apart from where they are evaluated. With duck typing obviously being evaluated dynamically, and structural typing being evaluated statically. Therefore, "compile time duck typing" is more commonly known as structural typing.

Consider the following in a hypothetical language that bears a striking similarity to Typescript. I will leave you to decide if that was on purpose or if it is merely coincidental.

    interface Comparable { isGreaterThan(other: Comparable): boolean }
    function max(a: Comparable, b: Comparable) { return a.isGreaterThan(b) ? a : b }

As usually defined, if this language accepts any type with an isGreaterThan method as a Comparable, it would be considered an example of structural typing. Types are evaluated based on their shape, not their name. This is the canonical example of structural typing! Ignore the type definitions and you get the canonical example of duck typing!!

Now, what if we rewrite that as this?

    interface Comparable { >(other: Comparable): boolean }
    function max(a: Comparable, b: Comparable) { return a > b ? a : b; }

Staring to look familiar? But let's go further. What if the interface could be automatically inferred by the type checker?

    function max<interface Comparable>(a: Comparable, b: Comparable) { return a > b ? a : b; }

That is looking an awful lot like:

    template<typename T> T max(T &a, T &b) { return a > b ? a : b; }

Of course, there is a problem here. Under use, the following will fail in the C++ version, even though both inputs "quack like a duck". The same code, any syntax differences aside, will work in our hypothetical language with structural typing.

    int x = 1;
    float y = 1.0;
    max(x, y);

So, yes, you're quite right that your example is not a display of structural typing. But it is also not a display of duck typing (of some compile time variety or otherwise) either. Here, "quacking" is not enough to satisfy the constraints. In order to satisfy the constraints the types need to have the same name, which violates the entire idea behind duck typing.

Which is all to say: Your confusion stems from starting with a false premise.

The rhetorical slight of hand you're engaging in here is simple: you're starting with a language in which 1 and 1.0 quack, and then swapping in a language in which 1 and 1.0 do not quack, and hoping, perhaps, that I won't notice?

Anyway, your confusion may be easily resolved by perusing the following link.

https://en.wikipedia.org/wiki/Duck_typing#Templates_or_gener...

> and then swapping in a language in which 1 and 1.0 do not quack

Except, no. This compiles and evaluates just fine in C++. Both quack the same quack.

    int x = 1;
    float y = 1;
    x > y;

The previously provided code fails because of the use of typename, which explicitly calls for the compiler to evaluate the type based on name. That is literally the documented purpose of the keyword. And which is exactly what duck typing is not. Duck typing doesn't need a duck to actually be a duck. If a goose walks and quacks like a duck... Close enough — it is a duck!

> Anyway, your confusion may be easily resolved by perusing the following link.

Imagine having such little understanding of what you are talking about that you can't do it and have to defer to the work of others. Why even bother participating in a discussion if you can't speak to it yourself? It is especially humorous when that work of someone else doesn't even state what it is purported to.

Reply on news.ycombinator.com