<p>I <a href="https://www.cl.cam.ac.uk/%7Ejdy22/papers/modular-implicits.pdf" rel="noreferrer">read</a> that, in GHC:</p>
<blockquote>
<p>Type classes are implemented using a type-directed implicit parameter-passing mechanism. Each constraint on a type is treated as a parameter containing a dictionary of the methods of the type class. The corresponding argument is implicitly inserted by the compiler using the appropriate type class instance.</p>
</blockquote>
<p>I think this is describing a form of <a href="https://en.wikipedia.org/wiki/Dynamic_dispatch" rel="noreferrer">dynamic dispatch</a> - although implemented differently to the common approach (which uses vtables).</p>
<p>But, Haskell (the language itself, not the implementation) doesn't make any distinction between static and dynamic dispatch (unlike Rust and C++, with <code>dyn</code> and <code>virtual</code>). So why does GHC effectively use dynamic dispatch everywhere, when static dispatch is (1) possible and (2) would be faster? (which is because, respectively:</p>
<ol>
<li>The concrete type of every value can be known at compile-time</li>
<li>Static dispatch could allow more specialisation, and remove the need to pass an extra parameter around to every polymorphic function, both of which would improve performance</li>
</ol>
<p>)</p>
<p>In fact, I will make this into a more general question: in a language with parametric polymorphism, how should we choose between static and dynamic dispatch?</p>

<haskell><static-dispatch><polymorphism><dynamic-dispatch>
Static or dynamic dispatch for parametric polymorphism
CC BY-SA 4.0
2023-05-17T20:23:19.923Z
GHC tends to rely on function inlining to take out the cost of dynamic dispatch. Once you inline the function and have the vtable available statically, those previously-dynamic calls aren't dynamic anymore. Effectively, you've monomorphized the function without the cost of generating code bloat. Functional languages *love* inlining functions, which works well because functional programmers love writing very short functions.
Silvio Mayolo
CC BY-SA 4.0
2023-05-17T21:47:22.703Z
One way of answering this question is to see how the choice plays out in Rust: an [object-safe trait](https://doc.rust-lang.org/1.8.0/book/trait-objects.html) can be used dynamically or statically. Dynamic bloats code less but has slower dispatch. You can have a list of trait objects (dynamic) but not a heterogeneous vec of things that implement the same trait.
Max Heiber
<p>As @Silvio Mayolo mentions in the comments, GHC Haskell does transform code to this “dictionary-passing style” by adding vtable arguments, but the result doesn’t necessarily require dynamic dispatch. In fact, Haskell 2010 never strictly requires it; only if you use certain extensions, such as existential types, does the compiler strictly <em>need</em> to emit the code to dispatch dynamically.</p>
<p>The reason to desugar this way is basically that it’s a simple, naïve transformation that’s easy to get right, and which automatically handles both situations. If the type is known, then the function can be specialised, and the vtable is constant, so by inlining it can be constant-folded away. If the type <em>isn’t</em> known, then the same desugaring still produces a correct result. (I would guess GHC also has some optimisations to do this less naïvely, I’m just not very familiar with it.)</p>
<p>It’s worth noting that this is <em>far</em> better than the usual OOP technique of putting a vtable pointer in every single object header! Especially for a container of elements of the same type, that O(<em>n</em>) extra space can add up.</p>
<p>When the only difference between static and dynamic dispatch is your choice of whether to emit a static or dynamic call instruction, you should absolutely prefer static dispatch. It can let a linker do link-time optimisation, and it gives the CPU a better chance of prefetching predictable code, instead of stalling while it awaits new instructions from the next level of cache (or worse, main memory).</p>
<p>This also applies to cases when the polymorphism is truly parametric—that is, when compilation preserves parametricity. In GHC Haskell again, type parameters of kind <code>*</code> / <code>Type</code> / <code>TYPE 'LiftedRep</code> all have the same runtime representation, namely a pointer. So the same code will be generated regardless of the type, and static dispatch is purely a win, by saving an indirection.</p>
<p>However, if compilation is <em>not</em> parametric, and a function might be specialised for different runtime representations—as it can be in Haskell, and normally <em>is</em> in Rust—then there are many more tradeoffs to consider, more than I can hope to cover here. Broadly speaking, specialisation means spending more time compiling and linking, generating <em>more</em> code in the hope that it’s <em>better</em> code. Typically, this lowers local costs like CPU cycle counts, but also raises global costs like instruction cache miss rate.</p>

CC BY-SA 4.0
2023-05-18T03:14:29.503Z
2023-05-18T03:14:29.503Z
Jon Purdy
# Static or dynamic dispatch for parametric polymorphism
Posted by: username_0 on 2023-05-17
I [read](https://www.cl.cam.ac.uk/%7Ejdy22/papers/modular-implicits.pdf) that, in GHC:

> Type classes are implemented using a type-directed implicit parameter-passing mechanism. Each constraint on a type is treated as a parameter containing a dictionary of the methods of the type class. The corresponding argument is implicitly inserted by the compiler using the appropriate type class instance.

I think this is describing a form of [dynamic dispatch](https://en.wikipedia.org/wiki/Dynamic_dispatch) - although implemented differently to the common approach (which uses vtables).

But, Haskell (the language itself, not the implementation) doesn't make any distinction between static and dynamic dispatch (unlike Rust and C++, with `dyn` and `virtual`). So why does GHC effectively use dynamic dispatch everywhere, when static dispatch is (1) possible and (2) would be faster? (which is because, respectively:

1. The concrete type of every value can be known at compile-time
2. Static dispatch could allow more specialisation, and remove the need to pass an extra parameter around to every polymorphic function, both of which would improve performance

)

In fact, I will make this into a more general question: in a language with parametric polymorphism, how should we choose between static and dynamic dispatch?
**Tags:** haskell static-dispatch polymorphism dynamic-dispatch
> **Comments:**
> **username_1**: GHC tends to rely on function inlining to take out the cost of dynamic dispatch. Once you inline the function and have the vtable available statically, those previously-dynamic calls aren't dynamic anymore. Effectively, you've monomorphized the function without the cost of generating code bloat. Functional languages *love* inlining functions, which works well because functional programmers love writing very short functions.  
> **username_2**: One way of answering this question is to see how the choice plays out in Rust: an [object-safe trait](https://doc.rust-lang.org/1.8.0/book/trait-objects.html) can be used dynamically or statically. Dynamic bloats code less but has slower dispatch. You can have a list of trait objects (dynamic) but not a heterogeneous vec of things that implement the same trait.  
---
## 1 answers
### Answer by username_3 on 2023-05-18. Score: 7
As @Silvio Mayolo mentions in the comments, GHC Haskell does transform code to this “dictionary-passing style” by adding vtable arguments, but the result doesn’t necessarily require dynamic dispatch. In fact, Haskell 2010 never strictly requires it; only if you use certain extensions, such as existential types, does the compiler strictly *need* to emit the code to dispatch dynamically.

The reason to desugar this way is basically that it’s a simple, naïve transformation that’s easy to get right, and which automatically handles both situations. If the type is known, then the function can be specialised, and the vtable is constant, so by inlining it can be constant-folded away. If the type *isn’t* known, then the same desugaring still produces a correct result. (I would guess GHC also has some optimisations to do this less naïvely, I’m just not very familiar with it.)

It’s worth noting that this is *far* better than the usual OOP technique of putting a vtable pointer in every single object header! Especially for a container of elements of the same type, that O(*n*) extra space can add up.

When the only difference between static and dynamic dispatch is your choice of whether to emit a static or dynamic call instruction, you should absolutely prefer static dispatch. It can let a linker do link-time optimisation, and it gives the CPU a better chance of prefetching predictable code, instead of stalling while it awaits new instructions from the next level of cache (or worse, main memory).

This also applies to cases when the polymorphism is truly parametric—that is, when compilation preserves parametricity. In GHC Haskell again, type parameters of kind `*` / `Type` / `TYPE 'LiftedRep` all have the same runtime representation, namely a pointer. So the same code will be generated regardless of the type, and static dispatch is purely a win, by saving an indirection.

However, if compilation is *not* parametric, and a function might be specialised for different runtime representations—as it can be in Haskell, and normally *is* in Rust—then there are many more tradeoffs to consider, more than I can hope to cover here. Broadly speaking, specialisation means spending more time compiling and linking, generating *more* code in the hope that it’s *better* code. Typically, this lowers local costs like CPU cycle counts, but also raises global costs like instruction cache miss rate.
---
