Associated Types and Monomorphisation

[rogerkeays]

Is it correct to think of associated types as implicit generic types? i.e. are trait implementations monomorphised over associated types in the same way they are over generic types?

[paramagnetic]

I'm not sure I understand the question. Only functions (machine code) and types (memory layout) can be monomorphized. A given (concrete) impl can only have a single (concrete) associated type, so I don't think even talking about monomorphization makes sense. (If you have a GAT, then the only way it'll be used is it'll be instantiated as some concrete type anyway, so it again boils down to the monomorphization of functions that use it.)

Associated types are output types of a trait, they are determined by the impl, whereas generic parameters are inputs and are determined by whoever is concretizing a generic type, trait, or function. Thus, they serve different roles, and are not the same at all.

[jorendorff]

I think the answer is no.

Generic functions are monomorphized depending on their type parameters. When code is generated for a monomorphization, the compiler knows all those parameters, and so naturally it also knows the associated types, and the generated code is specialized accordingly.

You should think of the associated types as information the compiler knows when it goes to generate code, but there's a lot more in that category than just the type parameters, including the return types of the non-generic functions the code calls, even the bodies of those functions (for inlining), the values of consts it uses, and so on.

[rogerkeays]

For example, if I create an iterator from a Vec<String> and another from a Vec<i32>, will two versions of the Iterator::next() implementation be compiled, one for returning Strings and one for returning i32? I can't see how it could be any other way. It just seems like a lot of compiling, that's all.

[paramagnetic]

@rogerkeays

For example, if I create an iterator from a Vec<String> and another from a Vec<i32>

Those are not associated types, those are the type parameter of Vec.

[rogerkeays]

@jorendorff

You should think of the associated types as information the compiler knows when it goes to generate code,

This is what I meant by implicit generic types. Maybe a better metaphor would be just implicit types. I get the input/output types explanation, but was looking for something more ... cough generic.

[jorendorff]

@rogerkeays

It just seems like a lot of compiling, that's all.

Quote of the week.

You've understood correctly. It's a lot of compiling.

[rogerkeays]

@paramagnetic

@rogerkeays

For example, if I create an iterator from a Vec<String> and another from a Vec<i32>

Those are not associated types, those are the type parameter of Vec.

I was thinking more about the return type of Iterator::next():
fn next(&mut self) -> Option<Self::Item>

For a Vec<String> that should be String; for Vec<i32>, i32. So it's a generic function, and has to be monomorphised, right?

[kpreid]

@rogerkeays

I was thinking more about the return type of Iterator::next():
fn next(&mut self) -> Option<Self::Item>

For a Vec<String> that should be String; for Vec<i32>, i32. So it's a generic function, and has to be monomorphised, right?

<std::vec::IntoIter<T, A> as Iterator>::next() lives inside a generic implementation impl<T, A> Iterator for IntoIter<T, A>, so it has to be monomorphized for T and A.

But that is not true of all iterators. For excample, <std::env::Args as Iterator>::next() is not generic — it always returns Option<String>. So, <Args as Iterator>::Item is always String — and no monomorphization is needed.

[paramagnetic]

@rogerkeays

So it's a generic function

No, next() itself is not generic, it has no type parameters.

The monomorphization in the case of Vec happens because Vec is generic. But for a specific T, <Vec<T> as IntoIterator>::IntoIter = std::vec::IntoIter<T> is also a very specific type, with a specific item type (Item = T itself, of course). It has nothing to do with the associated type.

For example, Chars isn't generic, either (except for the lifetime, but that doesn't affect the Item associated type). Its item type is always char, and it's next() method always returns an Option<char>. There's nothing to monomorphize.

[SkiFire13]

@rogerkeays

For a Vec<String> that should be String; for Vec<i32>, i32. So it's a generic function, and has to be monomorphised, right?

If you start with different types (Vec<String> and Vec<i32>) you'll end up with different functions anyway. The associated type won't make a difference.

An associated type is unique for each combination of implemented trait and type. If you're in a situation where it is different then there's already some other generic type that has changed and will cause a different monomorphization. The associated type will never be the primary cause of that.

[quinedot]

@SkiFire13

An associated type is unique for each combination of implemented trait and type.

This is sometimes phrased as associated types^[1] being the outputs of implementations. (The trait, implementing type, and parameters of those, are the inputs.)

---

1. and other trait items such as methods ↩︎

[the8472]

@rogerkeays

It just seems like a lot of compiling, that's all.

Note that those are the language semantics. Optimizations such as lld's ICF, llvm's MergeFunctions and one day rust's polymorphization can claw back some of that cost for functions that are nominally different but end up being the same at the respective level of abstraction.