10
$\begingroup$

I read 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 - 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?

$\endgroup$
2
  • 4
    $\begingroup$ 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. $\endgroup$ Commented May 17, 2023 at 20:23
  • 1
    $\begingroup$ One way of answering this question is to see how the choice plays out in Rust: an object-safe trait 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. $\endgroup$
    – Max Heiber
    Commented May 17, 2023 at 21:47

1 Answer 1

7
$\begingroup$

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, naï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 naï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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .