<p>Generic functions in compiled languages can be implemented in (at least) two different ways:</p>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Monomorphization" rel="noreferrer">Monomorphisation</a> ─ separate versions of the function are compiled for each different assignment of type parameters. Essentially the function declaration is treated like a template for generating specialised code for each call site (though of course the code can be shared between multiple call sites with the same type parameters).</li>
<li><a href="https://en.wikipedia.org/wiki/Type_erasure" rel="noreferrer">Type erasure</a> ─ the generic function is compiled to a single function, which works polymorphically for any type parameters.</li>
</ul>
<p>What practical differences are there between these two choices, beyond the internal implementation details of the compiler ─ i.e., what differences are visible to users of the language? When would one be preferred to the other?</p>

<generics><monomorphization><type-erasure>
How to choose between monomorphisation and type erasure for generics?
<h2>Why not a bit of both?</h2>
<p>This is how Swift does it, AFAIK. for private/internal functions where it knows exactly how it’ll be called, it monomorphises. For public functions in a library and implementations of a protocol from a library, it uses type erasure. For performance, some functions in the standard library emit some monomorphised versions of functions for common types via the <code>@_specialize</code> attribute. See, for example, <a href="https://github.com/apple/swift/blob/570c364cc4e6100a433d7d5d8c397279b7d27bbd/stdlib/public/core/StringRangeReplaceableCollection.swift#L162" rel="noreferrer"><code>String.append(contentsOf:)</code></a>:</p>
<pre class="lang-swift prettyprint-override"><code>  @_specialize(where S == String)
  @_specialize(where S == Substring)
  @_specialize(where S == Array&lt;Character&gt;)
  public mutating func append&lt;S: Sequence&gt;(contentsOf newElements: S)
  where S.Iterator.Element == Character
</code></pre>
<p>This emits monomorphised versions for <code>String</code>, <code>Substring</code>, and <code>Array&lt;Character&gt;</code>, but also a type-erased version that e.g. <code>Set&lt;Character&gt;</code> will use.</p>

CC BY-SA 4.0
2023-05-21T15:04:04.433Z
2023-05-21T15:04:04.433Z
Bbrk24
CC BY-SA 4.0
2024-03-07T06:17:12.570Z
I want to use this mechanism, but I encountered a difficult problem. Generally speaking, the generic interface is defined by the library provider, and if the user wants to specialize a custom type, he cannot modify the code in the library.
Aster
CC BY-SA 4.0
2024-03-08T00:34:23.133Z
@Aster Yep, that can be an issue — not necessarily for code generation, but for efficiency, since calls across module boundaries will always use the unspecialized version. IIRC Swift’s solution is to make all public generic functions implicitly `@inlineable`.
Bbrk24
CC BY-SA 4.0
2024-08-02T16:30:13.490Z
Scala 2 also had means to provide specialized functions; TBH I doubt that it is a good idea because it blurs the semantics of the construct.
feldentm
<p>Monomorphization is less expressive than type erasure. The main limitation is that in order to monomorphize, the compiler must know the set of potential types. In some situations, this can be difficult or even impossible.</p>
<h2>When it's difficult</h2>
<p>C++ has this somewhat <a href="https://stackoverflow.com/questions/495021/why-can-templates-only-be-implemented-in-the-header-file">infamous quirk</a> where all generics (&quot;templates&quot;) have to be defined in the header, which defies the separation of <a href="https://en.wikipedia.org/wiki/Translation_unit_(programming)" rel="nofollow noreferrer">translation units</a> philosophy inherited from C. This is because in generics as implemented in C++ have to be instantiated before being converted to object code.</p>
<p>Rust has a similar issue with compilation of generics across different translation units (&quot;crates&quot;). Their solution is to <a href="https://www.reddit.com/r/rust/comments/hbml8s/how_can_rust_compile_crosscrate_generics/" rel="nofollow noreferrer">compile the generic functions into an intermediate language</a> instead of fully compiling them into object files where the generic structure would be lost.</p>
<h2>When it's impossible</h2>
<p>Some uses of generics are fundamentally incompatible with monomorphization because the underlying type is only known at run time. For example, we can't really store a generic into a struct:</p>
<pre><code>struct SortingAlgorithm {
  sort: forall&lt;T&gt; (less: (T, T) -&gt; bool, array: Array&lt;T&gt;) -&gt; Array&lt;T&gt;
}
</code></pre>
<p>This is a structure holding a <em>generic</em> closure, but we don't know a priori what <code>T</code> is: the function pointer is required to accept <em>all</em> possible <code>T</code>.</p>
<p>Another situation that requires type erasure are <a href="https://en.wikipedia.org/wiki/Type_system#Existential_types" rel="nofollow noreferrer">existential types</a>.</p>

CC BY-SA 4.0
2023-07-25T05:22:14.413Z
2024-06-15T07:40:00.243Z
2024-06-15T07:40:00.243Z
Rufflewind
CC BY-SA 4.0
2024-06-14T10:30:27.840Z
I think your existential type example is not an existential type. You can call `sort` on any `T`, instead of one particular `T` captured by `SortingAlgorithm` that you don't know about in the use sites of `SortingAlgorithm`.
osa1
CC BY-SA 4.0
2024-06-15T07:40:08.223Z
Removed incorrect example. Thanks!
Rufflewind
<p>One issue with type erasure is that it requires all possible types that the function might be called with, to have some fixed size in memory; in contrast, a monomorphised function can be specialised to types of different sizes.</p>
<p>In languages like Java, all or most types are the same size, because all values of those types are references to objects. However, even in Java primitive types can have different sizes, making it difficult or impossible to allow assigning primitive types to generic type parameters. This means e.g. <code>ArrayList&lt;Integer&gt;</code> is possible but <code>ArrayList&lt;int&gt;</code> isn't.</p>
<p>In contrast, monomorphisation allows for the size of the type parameters to be unconstrained, which is more flexible. This also means there is no need for boxed types like <code>Integer</code>, which have performance costs due to pointer indirection and memory management. Additionally, monomorphisation can save memory when the type parameter is a <a href="https://runrust.miraheze.org/wiki/Zero-sized_type" rel="nofollow noreferrer">zero-sized type</a>, by not allocating memory for variables or fields whose values don't matter.</p>
<p>For example, a <code>HashTable&lt;T, ()&gt;</code> in Rust can be used to implement a <a href="https://en.wikipedia.org/wiki/Set_(abstract_data_type)" rel="nofollow noreferrer">set</a> without needing to allocate memory for the values in the hashtable. In Java, the equivalent code would allocate an array containing all <code>null</code> values, wasting space.</p>

CC BY-SA 4.0
2023-05-21T14:55:58.603Z
2023-05-21T14:55:58.603Z
kaya3
CC BY-SA 4.0
2023-07-25T05:27:38.917Z
The size of the type does not need to be fixed for type erasure, it just needs to become an extra parameter to the type-erased function.  In general, all the type's attributes can become extra argument(s)
Chris Dodd
CC BY-SA 4.0
2023-07-25T13:42:12.310Z
@ChrisDodd I suppose that's true, but then it also has to become an extra field on the object, and now not all `HashMap` objects have the same layout, which is problematic.
kaya3
CC BY-SA 4.0
2023-07-25T22:45:01.600Z
Only for objects that directly contain a field of a type-erased generic type, which is a different problem.  Even then, the type info can be stored in a separate metadata object rather than in the object directly, though that tends to favor implementations that support botth type-erased and monomorphic generics and can deal with either dynamically.
Chris Dodd
<p>Regarding usability (i.e. programming),</p>
<ul>
<li>C#, and Java (probably), generics feel <em>from the inside</em> as if programming to an interface. Basically the interface constraining the type parameter, or Object if unconstrained. Or if there are several constraints, more or less as if programming to the &quot;intersection&quot; of the constraints (which gives the &quot;union&quot; of the callable methods).</li>
<li>C++ generics (templates) are type-checked separately for every instantiation type, and parts not used are not type-checked, and there is overloading and complex name lookup, so you can do lots of <s>horrendous</s> <s>fabulous</s> interesting things with them.</li>
<li>(Rust generics are monomorphised, but I do not know on which side of the type-checking they fall.)</li>
</ul>
<p>For example, in C# it is (was?) impossible to do generic arithmetic code simply, whereas in C++ it is straightforward.</p>
<p>From the outside all generics give the ability to recover the exact type of the type parameter.</p>

CC BY-SA 4.0
2024-08-02T13:18:51.870Z
2024-08-02T13:18:51.870Z
Pablo H
CC BY-SA 4.0
2024-08-02T13:47:31.730Z
Rust generics are monomorphised but type-checked once, at the declaration site.
kaya3
CC BY-SA 4.0
2024-08-02T13:51:26.907Z
So more of a C#-like experience, then.
Pablo H
<p>The language specification must explain if what is called &quot;generics&quot; here means forall or lambda polymorphism. Both have different semantics, for functions and types:</p>
<pre><code>Iterator[String].class == Iterator[Object].class // true or false?
Iterator[String].map[String] == Iterator[String].map[Integer] // true or false?
</code></pre>
<p>It doesn't really make a difference if the underlying entity is a type or a function. What matters is that the result of the application of the compile time parameters is observable. For functions that's almost always the case, e.g. in stack traces. For types, it is usually the case.</p>
<p>Finally, this isn't really an either or. Languages can allow both kinds of polymoprhism. Tyr has both, because there is no benefit of either approach in general. Both have unique properties and consequences, but comparing them is inadequate. It's like asking should my language have Objects or integers.</p>

CC BY-SA 4.0
2024-08-02T16:28:00.603Z
2024-08-02T16:28:00.603Z
feldentm
<p>Here are a few differences between monomorphisation and type erasure:</p>
<ul>
<li><p><strong>Performance:</strong> Monomorphisation generally leads to better runtime performance because each specialised version of the function is optimised for the specific types used at the call site. This can result in more efficient code and eliminate the need for dynamic dispatch. On the other hand, type erasure can introduce some overhead due to dynamic dispatch or runtime type checks.</p>
</li>
<li><p><strong>Code Size:</strong> Monomorphisation can increase the code size of the compiled program because it generates separate versions of the function for each type combination used. This could lead to some performance implications, but usually this is cancelled out by the fact that each version of the function is optimised for the specific type, as mentioned above. Type erasure, generating a single function only, generally leads to smaller code size.</p>
</li>
<li><p><strong>Compilation Time:</strong> Monomorphisation requires compiling separate versions of the function for each type combination. This can significantly increase compilation time, especially if there are numerous combinations. Type erasure, on the other hand, can reduce compilation time since there's only one version of the function to compile.</p>
</li>
<li><p><strong>Debugging and Error Messages:</strong> Monomorphisation can provide more precise error messages and easier debugging experience because each specialised version of the function has explicit types. Error messages can refer to specific types involved, aiding developers in identifying and fixing issues. In contrast, type erasure might provide less specific error messages since the function works polymorphically for any type parameters.</p>
</li>
</ul>

CC BY-SA 4.0
2023-05-21T14:25:33.393Z
2023-05-21T14:26:59.467Z
2023-05-21T14:26:59.467Z
The Thonnu
CC BY-SA 4.0
2023-05-21T14:26:43.080Z
Monomorphisation can also increase the size of the compiled output ─ does this have implications for performance?
kaya3
CC BY-SA 4.0
2023-05-21T14:29:21.610Z
@kaya3 it could have some implications, but usually they are cancelled out by the fact that each version of the function is optimised for the specific types, as mentioned in the answer. That is a good point though, so I'll add that to the answer.
The Thonnu
CC BY-SA 4.0
2023-05-21T14:32:08.937Z
Do you know if there is any empirical information about the performance differences? It's a good answer regardless, I'm just curious.
kaya3
CC BY-SA 4.0
2023-05-21T14:33:59.537Z
@kaya3 I'm sorry, but I don't know about that.
The Thonnu
# How to choose between monomorphisation and type erasure for generics?
Posted by: username_0 on 2023-05-21
Generic functions in compiled languages can be implemented in (at least) two different ways:

* [Monomorphisation](https://en.wikipedia.org/wiki/Monomorphization) ─ separate versions of the function are compiled for each different assignment of type parameters. Essentially the function declaration is treated like a template for generating specialised code for each call site (though of course the code can be shared between multiple call sites with the same type parameters).
* [Type erasure](https://en.wikipedia.org/wiki/Type_erasure) ─ the generic function is compiled to a single function, which works polymorphically for any type parameters.

What practical differences are there between these two choices, beyond the internal implementation details of the compiler ─ i.e., what differences are visible to users of the language? When would one be preferred to the other?
**Tags:** generics monomorphization type-erasure
---
## 6 answers
### Answer by username_8 on 2023-05-21. Score: 4 | Accepted answer
Here are a few differences between monomorphisation and type erasure:

* **Performance:** Monomorphisation generally leads to better runtime performance because each specialised version of the function is optimised for the specific types used at the call site. This can result in more efficient code and eliminate the need for dynamic dispatch. On the other hand, type erasure can introduce some overhead due to dynamic dispatch or runtime type checks.
* **Code Size:** Monomorphisation can increase the code size of the compiled program because it generates separate versions of the function for each type combination used. This could lead to some performance implications, but usually this is cancelled out by the fact that each version of the function is optimised for the specific type, as mentioned above. Type erasure, generating a single function only, generally leads to smaller code size.
* **Compilation Time:** Monomorphisation requires compiling separate versions of the function for each type combination. This can significantly increase compilation time, especially if there are numerous combinations. Type erasure, on the other hand, can reduce compilation time since there's only one version of the function to compile.
* **Debugging and Error Messages:** Monomorphisation can provide more precise error messages and easier debugging experience because each specialised version of the function has explicit types. Error messages can refer to specific types involved, aiding developers in identifying and fixing issues. In contrast, type erasure might provide less specific error messages since the function works polymorphically for any type parameters.
> **Comments:**
> **username_0** (2023-05-21): Monomorphisation can also increase the size of the compiled output ─ does this have implications for performance?  
> **username_8** (2023-05-21): @kaya3 it could have some implications, but usually they are cancelled out by the fact that each version of the function is optimised for the specific types, as mentioned in the answer. That is a good point though, so I'll add that to the answer.  
> **username_0** (2023-05-21): Do you know if there is any empirical information about the performance differences? It's a good answer regardless, I'm just curious.  
> **username_8** (2023-05-21): @kaya3 I'm sorry, but I don't know about that.  
---
### Answer by username_1 on 2023-05-21. Score: 5
Why not a bit of both?
This is how Swift does it, AFAIK. for private/internal functions where it knows exactly how it’ll be called, it monomorphises. For public functions in a library and implementations of a protocol from a library, it uses type erasure. For performance, some functions in the standard library emit some monomorphised versions of functions for common types via the @_specialize attribute. See, for example, String.append(contentsOf:):
  @_specialize(where S == String)
  @_specialize(where S == Substring)
  @_specialize(where S == Array)
  public mutating func append(contentsOf newElements: S)
  where S.Iterator.Element == Character

This emits monomorphised versions for String, Substring, and Array, but also a type-erased version that e.g. Set will use.
> **Comments:**
> **username_2** (2024-03-07): I want to use this mechanism, but I encountered a difficult problem. Generally speaking, the generic interface is defined by the library provider, and if the user wants to specialize a custom type, he cannot modify the code in the library.  
> **username_1** (2024-03-08): @Aster Yep, that can be an issue — not necessarily for code generation, but for efficiency, since calls across module boundaries will always use the unspecialized version. IIRC Swift’s solution is to make all public generic functions implicitly `@inlineable`.  
> **username_3** (2024-08-02): Scala 2 also had means to provide specialized functions; TBH I doubt that it is a good idea because it blurs the semantics of the construct.  
---
### Answer by username_4 on 2023-07-25. Score: 5
Monomorphization is less expressive than type erasure. The main limitation is that in order to monomorphize, the compiler must know the set of potential types. In some situations, this can be difficult or even impossible.
When it's difficult
C++ has this somewhat infamous quirk where all generics ("templates") have to be defined in the header, which defies the separation of translation units philosophy inherited from C. This is because in generics as implemented in C++ have to be instantiated before being converted to object code.
Rust has a similar issue with compilation of generics across different translation units ("crates"). Their solution is to compile the generic functions into an intermediate language instead of fully compiling them into object files where the generic structure would be lost.
When it's impossible
Some uses of generics are fundamentally incompatible with monomorphization because the underlying type is only known at run time. For example, we can't really store a generic into a struct:
struct SortingAlgorithm {
  sort: forall (less: (T, T) -> bool, array: Array) -> Array
}

This is a structure holding a generic closure, but we don't know a priori what T is: the function pointer is required to accept all possible T.
Another situation that requires type erasure are existential types.
> **Comments:**
> **username_5** (2024-06-14): I think your existential type example is not an existential type. You can call `sort` on any `T`, instead of one particular `T` captured by `SortingAlgorithm` that you don't know about in the use sites of `SortingAlgorithm`.  
> **username_4** (2024-06-15): Removed incorrect example. Thanks!  
---
### Answer by username_0 on 2023-05-21. Score: 4
One issue with type erasure is that it requires all possible types that the function might be called with, to have some fixed size in memory; in contrast, a monomorphised function can be specialised to types of different sizes.

In languages like Java, all or most types are the same size, because all values of those types are references to objects. However, even in Java primitive types can have different sizes, making it difficult or impossible to allow assigning primitive types to generic type parameters. This means e.g. `ArrayList` is possible but `ArrayList` isn't.

In contrast, monomorphisation allows for the size of the type parameters to be unconstrained, which is more flexible. This also means there is no need for boxed types like `Integer`, which have performance costs due to pointer indirection and memory management. Additionally, monomorphisation can save memory when the type parameter is a [zero-sized type](https://runrust.miraheze.org/wiki/Zero-sized_type), by not allocating memory for variables or fields whose values don't matter.

For example, a `HashTable` in Rust can be used to implement a [set](https://en.wikipedia.org/wiki/Set_(abstract_data_type)) without needing to allocate memory for the values in the hashtable. In Java, the equivalent code would allocate an array containing all `null` values, wasting space.
> **Comments:**
> **username_6** (2023-07-25): The size of the type does not need to be fixed for type erasure, it just needs to become an extra parameter to the type-erased function.  In general, all the type's attributes can become extra argument(s)  
> **username_0** (2023-07-25): @ChrisDodd I suppose that's true, but then it also has to become an extra field on the object, and now not all `HashMap` objects have the same layout, which is problematic.  
> **username_6** (2023-07-25): Only for objects that directly contain a field of a type-erased generic type, which is a different problem.  Even then, the type info can be stored in a separate metadata object rather than in the object directly, though that tends to favor implementations that support botth type-erased and monomorphic generics and can deal with either dynamically.  
---
### Answer by username_7 on 2024-08-02. Score: 1
Regarding usability (i.e. programming),

* C#, and Java (probably), generics feel *from the inside* as if programming to an interface. Basically the interface constraining the type parameter, or Object if unconstrained. Or if there are several constraints, more or less as if programming to the "intersection" of the constraints (which gives the "union" of the callable methods).
* C++ generics (templates) are type-checked separately for every instantiation type, and parts not used are not type-checked, and there is overloading and complex name lookup, so you can do lots of ~~horrendous~~ ~~fabulous~~ interesting things with them.
* (Rust generics are monomorphised, but I do not know on which side of the type-checking they fall.)

For example, in C# it is (was?) impossible to do generic arithmetic code simply, whereas in C++ it is straightforward.

From the outside all generics give the ability to recover the exact type of the type parameter.
> **Comments:**
> **username_0** (2024-08-02): Rust generics are monomorphised but type-checked once, at the declaration site.  
> **username_7** (2024-08-02): So more of a C#-like experience, then.  
---
### Answer by username_3 on 2024-08-02. Score: 1
The language specification must explain if what is called "generics" here means forall or lambda polymorphism. Both have different semantics, for functions and types:
Iterator[String].class == Iterator[Object].class // true or false?
Iterator[String].map[String] == Iterator[String].map[Integer] // true or false?

It doesn't really make a difference if the underlying entity is a type or a function. What matters is that the result of the application of the compile time parameters is observable. For functions that's almost always the case, e.g. in stack traces. For types, it is usually the case.
Finally, this isn't really an either or. Languages can allow both kinds of polymoprhism. Tyr has both, because there is no benefit of either approach in general. Both have unique properties and consequences, but comparing them is inadequate. It's like asking should my language have Objects or integers.
---
