Classes from Object-Oriented Programming languages such as C++ allow types to declare a pre-selected list of overridable functions.

Typeclasses in Haskell are a general-purpose way to write functions whose implementations change depending on the type of a parameter.

They’re used very differently in practice, but this article will:

  • Describe how vtables implement C++ classes
  • Show that Haskell constructs a very similar data structure in typeclass-using code

Classes

C++ has the concept of a “class” - a record together with functions that manipulate it. The class creates a new namespace for the functions, so that different classes can have functions with the same name. Each function also takes the record as an implicit argument.

Here is an example of a class:

// Example 1
struct x {
int n;
void f();
void g();
void h();
};

void all_funcs_x(x _x) {
_x.f();
_x.g();
_x.h();
}

and here is how it might translate into C:

// Example 1
typedef struct x {
int n;
} x;

void x_f(x*);
void x_g(x*);
void x_h(x*);

void all_funcs_x(x _x) {
x_f(&_x);
x_g(&_x);
x_h(&_x);
}

A C++ compiler infers the namespace from a variable’s type, while a C programmer would have to remember which variant of f he wanted to invoke.

C++ also supports subtyping: x is a subtype of y if every record field and function in y is also in x. The narrower type x is responsible for declaring that it is a subtype of y, and then it doesn’t have to repeat the fields and functions it derived from y.

// Example 2

struct y : x { };

void all_funcs_y(y _y) {
all_funcs_x(_y);
}

Notice that all_funcs_x was invoked on an argument of type y even though we earlier declared it to take an x. Conceptually, a new function y_cast_x is created that converts the x into a y by copying its record fields. The C++ compiler will silently insert calls to this function to convert y into x by dropping extra fields; but will not convert x into y, since it has no way of knowing how to repopulate them.

// Example 2
typedef struct y {
int n;
} y;

x y_cast_x(y _y) {
x _x;
_x.n = _y.n;
return _x;
}

void all_funcs_y(y _y) {
all_funcs_x(y_cast_x(_y));
}

In practice, a C++ compiler will organize the fields so that y_cast_x is free when used with references or pointers.

Notice that f, g, and h must refer to x’s namespace. They can’t refer to y, because the functions have no way of knowing what the “original type” of _x was. They are only given a copy without the extraneous fields. So if y declared its own f, g, and h functions in its own y namespace, these would be ignored and the ones in x’s namespace called instead.

C++ also allows you to declare that certain functions should be looked up in the most-specific namespace available.

// Example 3
struct x {
int n;
virtual void f();
virtual void g();
virtual void h();
};

void all_funcs_x(x _x) {
_x.f();
_x.g();
_x.h();
}

This is implemented by creating a new implicit type x_vtable that has references to f, g, and h, adding an implicit field for it to x, and then copying these references during each call to y_cast_x:

// Example 3
typedef struct x_vtable {
void (*f)(); // 64-bit pointers to functions
void (*g)();
void (*h)();
} x_vtable;

typedef struct y_vtable {
void (*f)();
void (*g)();
void (*h)();
} y_vtable;

x_vtable yvtable_cast_xvtable(y_vtable yvt) {
x_vtable xvt;
xvt.f = yvt.f;
xvt.g = yvt.g;
xvt.h = yvt.h;
return xvt;
}

typedef struct x {
x_vtable *_xvt;
int n;
} x;

typedef struct y {
y_vtable *_yvt;
int n;
};

x y_cast_x(y _y) {
x _x;
_x.n = _y.n;
_x->_xvt = yvtable_cast_xvtable(_y->_xvt);
return _x;
}

void all_funcs_x(x _x) {
(*((_x._xvt)->f))(&_x);
(*((_x._xvt)->g))(&_x);
(*((_x._xvt)->h))(&_x);
}

void all_funcs_y(y _y) {
all_funcs_x(y_cast_x(_y));
}

There is also an implicit subtyping relation between x_vtable and y_vtable, and the compilers arrange the fields such that yvtable_cast_xvtable is usually free in the same manner than y_cast_x is usually free.

The compiler can be made to output its vtables.

// Example 3
// g++ -fdump-class-hierarchy -O3 -c x.cpp
Vtable for x
x::_ZTV1x: 5u entries
0 (int (*)(...))0
8 (int (*)(...))(& _ZTI1x)
16 (int (*)(...))x::f
24 (int (*)(...))x::g
32 (int (*)(...))x::h

Class x
size=16 align=8
base size=12 base align=8
x (0x0x7fb0516125a0) 0
vptr=((& x::_ZTV1x) + 16u)

Besides the three functions we intended, we also get an offset-to-top parameter at offset 0 and a typeinfo pointer at offset 8. The first is used for multiple-inheritance, and the second is a pointer to a type_info object. The vtable usually points to offset 16 to simplify code generation and not offset 0, so negative offsets are used when accessing the first two.

Why are functions not virtual by default? Two reasons:

  • The data in a C-style struct can be copied with memcpy and reused in other programs(or later versions of the same program). vtables are absolute pointers, so a simple bytewise copy is unusable except by the original program.
  • They are slightly slower, because every implicit cast might cause an extra 64-bit pointer to be written, every virtual function call adds a layer of indirection, and - most importantly - virtual function calls prevent inlining.

You can see the indirections in the disassembly.

// void all_funcs_x(x& _x) {
$ g++ -O3 -fPIC -c x.cpp
$ 0000000000000000 <_Z11all_funcs_xR1x>:
0: push rbx
1: mov rax,QWORD PTR [rdi]
4: mov rbx,rdi
7: call QWORD PTR [rax]
9: mov rax,QWORD PTR [rbx]
c: mov rdi,rbx
f: call QWORD PTR [rax+0x8]
12: mov rax,QWORD PTR [rbx]
15: mov rdi,rbx
18: pop rbx
19: mov rax,QWORD PTR [rax+0x10]
1d: jmp rax
1f: nop

The vtable pointer is located at offset 0 in x, so the first mov copies it into rax. Then, because the vtable points at the first function f, the call and jmp instructions use offsets 0, 0x8, 0x10 to call f, g, and h.

Here’s the version using non-virtual function calls:

$ g++ -O3 -fPIC -c x.cpp
0000000000000000 <_Z11all_funcs_xR1x>:
0: push rbx
1: mov rbx,rdi
4: call 9 <_Z11all_funcs_xR1x+0x9>
9: mov rdi,rbx
c: call 11 <_Z11all_funcs_xR1x+0x11>
11: mov rdi,rbx
14: pop rbx
15: jmp 1a <_Z11all_funcs_xR1x+0x1a>

$ objdump -r x.o
RELOCATION RECORDS FOR [.text]:
OFFSET TYPE VALUE
0000000000000005 R_X86_64_PLT32 _ZN1x1fEv-0x0000000000000004
000000000000000d R_X86_64_PLT32 _ZN1x1gEv-0x0000000000000004
0000000000000016 R_X86_64_PLT32 _ZN1x1hEv-0x0000000000000004

Those three relocations means that non-virtual function calls are actually available to the linker, which patches their addresses in at link-time. Thus, non-virtual calls always go to the same target regardless of what inputs are passed in, while virtual calls look at the argument to decide which function to call.

Typeclasses

A Haskell typeclass is a collection of related functions shared by many types. Typeclass instances give rules for finding a specific implementation for any given type. The simplest rule is that a concrete type is given a specific implementation:

class TC a where
f :: a -> IO ()
g :: a -> IO ()
h :: a -> IO ()

data X = X
instance TC X where
f _ = return ()
g _ = return ()
h _ = return ()

all_funcs :: TC a => a -> IO ()
all_funcs x = do
f x
g x
h x

In all_funcs above, a is a type such that the compiler knows how to find implementations for f, g, and h(the TC typeclass).

In an object-oriented language like C++, the rules for locating an implementation might involve traversing the class hierarchy upwards until you find the first defined function with the same name. Depending on the language, this could be greatly complicated by multiple inheritance, roles/traits, or adding methods to the class at runtime. Typeclasses should generalize any situation where it is possible to locate the implementation at compile-time.

Foreign C code

To start with, we need the non-virtual case. In the previous section, we showed that the virtual/non-virtual distinction can be observed by looking for relocations in the resulting object file. So we want to write Haskell that emits relocations that are resolved at link-time.

In C, every function by default is exposed to the linker and available to be called from other modules; and you have to explicitly mark functions as static to hide them from the linker. Haskell depends very heavily on inlining, so functions are hidden by default and you have to explicitly mark linker visibility using the Foreign Function Interface.

{-# LANGUAGE ForeignFunctionInterface, MagicHash #-}

module ClassX where

import Foreign.Ptr
import GHC.Prim

data X = X Int#

foreign import ccall "f" f :: Ptr X -> IO ()
foreign import ccall "g" g :: Ptr X -> IO ()
foreign import ccall "h" h :: Ptr X -> IO ()

all_funcs :: Ptr X -> IO ()
all_funcs x = do
f x
g x
h x

foreign export ccall "all_funcs" all_funcs :: Ptr X -> IO ()

The full disassembly generated by these function calls is a bit long, but I can go over the section immediately wrapping the f x call. I use ====> to mark where a block transfers control to the next.

$ ghc -fPIC -O2 X.hs
$ objdump -M intel -d X.o

0000000000000058 <c1Xm_info>:
58: sub rsp,0x8
5c: mov rdi,QWORD PTR [rbx+0x7]
60: xor eax,eax
====> 62: call 67 <c1Xm_info+0xf> # RELOCATION
67: add rsp,0x8
6b: lea rbx,[rip+0x0] # RELOCATION
72: add rbp,0x8
76: jmp QWORD PTR [rbp+0x0]

$ readelf -r X.o
Relocation section '.rela.text' at offset 0x11e8 contains 87 entries:
Offset Sym. Name + Addend
00000000003d .data + 13c
====> 000000000063 f - 4
00000000006e ghczmprim_GHCziTuple_Z - 3

The compiler generates 3 relocations for this expression. The latter two are the most relevant:

  • f - 4: This is the location of our f function.
  • ghczmprim_GHCziTuple_Z - 3: This is a library function that generates an empty tuple.

The important point here is that the location of f is resolved by the linker, so it is a fixed implementation comparable to the earlier C code.

Clearly C has a more efficient FFI for calling into foreign C code than Haskell does. But Haskell programmers usually use the module system to import and export code, rather than depending entirely on the linker. You also can’t export typeclass constraints via the FFI, which I need in order to claim that they are similar to C++’s vtables.

Haskell Modules

Let’s look at that again without the FFI:

module ClassX where

import SomeFuncs(X, f,g,h)

import Foreign.Ptr

all_funcs :: Ptr X -> IO ()
all_funcs x = do
f x
g x
h x

module SomeFuncs where

import Foreign.Ptr
import GHC.Prim
import Data.Word
import Foreign.Storable
import GHC.Storable

data X = X Int#

f :: Ptr X -> IO ()
f ptr = writeWord64OffPtr (castPtr ptr) 0 0x12345678
g :: Ptr X -> IO ()
g ptr = writeWord64OffPtr (castPtr ptr) 0 0x87654321
h :: Ptr X -> IO ()
h ptr = writeWord64OffPtr (castPtr ptr) 0 0x12344321

The constants make it easier to locate the implementation of all_funcs in the disassembly:

00000000000000a0 <ClassX_allzufuncs_info>:
====> a0: jmp 18 <ClassX_allzufuncs1_info>

0000000000000018 <ClassX_allzufuncs1_info>:
18: lea rax,[rbp-0x8]
1c: cmp rax,r15
1f: jb 3a <ClassX_allzufuncs1_info+0x22>
====> 21: lea rax,[rip+0x30] # 58 <c1WD_info>
28: mov QWORD PTR [rbp-0x8],rax
2c: mov rbx,r14
2f: add rbp,0xfffffffffffffff8
33: test bl,0x7
36: jne 58 <c1WD_info>
38: jmp QWORD PTR [rbx]
3a: lea rbx,[rip+0x0] # RELOCATION
41: jmp QWORD PTR [r13-0x8]

0000000000000058 <c1WD_info>:
58: mov rax,QWORD PTR [rbx+0x7]
5c: mov QWORD PTR [rax],0x12345678
63: mov ebx,0x87654321
68: mov QWORD PTR [rax],rbx
6b: mov QWORD PTR [rax],0x12344321
====> 72: mov rax,QWORD PTR [rip+0x0] # RELOCATION
79: lea rbx,[rax+0x1]
7d: add rbp,0x8
81: jmp QWORD PTR [rbp+0x0]

Relocation section '.rela.text' at offset 0xb48 contains 2 entries:
Offset Sym. Name + Addend
00000000003d ClassX_allzufuncs1_clo - 4
====> 000000000075 ghczmprim_GHCziTuple_Z - 4

GHC inlines the 3 pointer writes, and boxes up an empty tuple to return. Thus, the choice of function is determined at compile-time(and therefore link-time), which for our purposes agrees with the non-virtual function case from C.

That FFI imports and exports are matched by the linker, and that module imports are inlined probably won’t surprise anybody. But it’s good to confirm these easy cases as a baseline before making claims about typeclasses.

Typeclasses

C++ generates all of its vtables at compile-time. Haskell seems to create its typeclass dictionaries on the heap at the first function with a typeclass constraint, and then passes a pointer to child calls that use it. This indicates to me two possible performance implications:

  • Move the typeclass constraint as high up in your program’s dependency graph as possible, to avoid repeatedly creating typeclass dictionaries.
  • Use 6 or fewer functions in a given typeclass, which is the number of 64-bit integer registers available in the x64 System V ABI. Functions 7 or higher require twice as many mov instructions.

Here’s a big typeclass to demonstrate these:

module ClassX where

class TC a where
f1 :: a -> IO ()
f2 :: a -> IO ()
f3 :: a -> IO ()
f4 :: a -> IO ()
f5 :: a -> IO ()
f6 :: a -> IO ()
f7 :: a -> IO ()
f8 :: a -> IO ()

all_tc :: TC a => a -> IO ()
all_tc x = do
f1 x
f2 x
f3 x
f4 x
f5 x
f6 x
f7 x
f8 x

Looking at the f4 x call the instruction I’ve marked with ***** locates its typeclass dictionary entry at [rbx+0x1f], with 0x1f = sizeof(pointer) * 4 - 1. This demonstrates that most typeclass dictionaries in the above example are passed via pointer.

# ghc -ddump-cmm -fPIC -dynamic -O2 X.hs
0000000000000150 <ClassX_f4_info>:
150: lea rax,[rbp-0x8]
154: cmp rax,r15
157: jb 0x22
====> 159: lea rax,[rip+0x30] # 0x190
160: mov QWORD PTR [rbp-0x8],rax
164: mov rbx,r14
167: add rbp,0xfffffffffffffff8
16b: test bl,0x7
16e: jne 0x40
180: jmp QWORD PTR [rbx]

0000000000000190 <c29T_info>:
***** 190: mov rbx,QWORD PTR [rbx+0x1f]
194: add rbp,0x8
====> 198: jmp 19d <c29T_info+0xd> # RELOCATION

Relocation section '.rela.text' at offset 0x2070 contains 37 entries:
Offset Info Type Sym. Value Sym. Name + Addend
====> 000000000199 003700000002 R_X86_64_PC32 0000000000000000 stg_ap_0_fast - 4

To see that typeclass dictionaries are constructed at the entry point, notice this TC_entry function in GHC’s intermediate language C--:

 ClassX.C:TC_entry() //  [R6, R5, R4, R3, R2]
{ info_tbl: [(c2eM,
label: ClassX.C:TC_info
rep:HeapRep static {
Fun {arity: 8
fun_type: ArgGen [False, False, False, False, False, False, False,
False]} })]
stack_info: arg_space: 32 updfr_space: Just 8
}
{offset
c2eM: // global
Hp = Hp + 72;
if (Hp > HpLim) (likely: False) goto c2eQ; else goto c2eP;
c2eQ: // global
HpAlloc = 72;
R1 = ClassX.C:TC_closure;
P64[Sp - 40] = R2;
P64[Sp - 32] = R3;
P64[Sp - 24] = R4;
P64[Sp - 16] = R5;
P64[Sp - 8] = R6;
Sp = Sp - 40;
call (stg_gc_fun)(R1) args: 72, res: 0, upd: 8;
c2eP: // global
I64[Hp - 64] = ClassX.C:TC_con_info;
P64[Hp - 56] = R2;
P64[Hp - 48] = R3;
P64[Hp - 40] = R4;
P64[Hp - 32] = R5;
P64[Hp - 24] = R6;
P64[Hp - 16] = P64[Sp];
P64[Hp - 8] = P64[Sp + 8];
P64[Hp] = P64[Sp + 16];
R1 = Hp - 63;
Sp = Sp + 24;
call (P64[Sp])(R1) args: 8, res: 0, upd: 8;

The caller into code with a typeclass constraint needs to provide implementations of every function in the typeclass. The typeclass dictionary is passed via the System V ABI to this entry function, which frees up the registers by allocating heap memory and copying them to it.

Haskell keeps a “heap pointer” for efficient heap allocations, just like a stack pointer is used. If the program is out of heap space, it calls into the garbage collector. Otherwise, it’s a few simple pointer copies followed by a jump into the actual typeclass-using code.

Looking at the disassembly, r12 has the heap pointer. One weird point is that heap references are often “off by 1”. The ***** entries above and below are not aligned to an 8-byte boundary. It doesn’t matter, because -0x3f + 0x1f = 0x20, which is the 8-byte aligned offset for the 4th typeclass entry f4.

0000000000000900 <ClassX_CZCTC_info>:
900: add r12,0x48
904: cmp r12,QWORD PTR [r13+0x358]
90b: ja 958 <ClassX_CZCTC_info+0x58>
90d: lea rax,[rip+0x0] # RELOCATION
914: mov QWORD PTR [r12-0x40],rax
919: mov QWORD PTR [r12-0x38],r14
91e: mov QWORD PTR [r12-0x30],rsi
923: mov QWORD PTR [r12-0x28],rdi
928: mov QWORD PTR [r12-0x20],r8
92d: mov QWORD PTR [r12-0x18],r9
932: mov rax,QWORD PTR [rbp+0x0]
936: mov QWORD PTR [r12-0x10],rax
93b: mov rax,QWORD PTR [rbp+0x8]
93f: mov QWORD PTR [r12-0x8],rax
944: mov rax,QWORD PTR [rbp+0x10]
948: mov QWORD PTR [r12],rax
***** 94c: lea rbx,[r12-0x3f]
951: add rbp,0x18
955: jmp QWORD PTR [rbp+0x0]

The typeclass dictionary is very similar to the C++ vtable data structure. It has no offset-to-top member, but I suspect the TC_con_info serves a similar purpose to the type_info field.

I would guess that GHC generates these data structures at runtime to prevent a combinatorial explosion of pregenerated typeclass dictionaries when using more advanced typeclass rules.

Specialized Typeclasses

GHC can sometimes specialize a generic typeclass-using function. This causes the typeclass dictionary to be inlined, which removes the need for a separate entry constructor and allocation.

all_tc_x below is a specialization of all_tc above.

data X = X
instance TC X where
f1 x = return ()
f2 x = return ()
f3 x = return ()
f4 x = return ()
f5 x = return ()
f6 x = return ()
f7 x = return ()
f8 x = return ()

all_tc_x :: X -> IO ()
all_tc_x x = do
all_tc x
all_tc x
all_tc x
all_tc x
all_tc x
all_tc x
all_tc x
all_tc x
all_tc x
all_tc x

all_tc_x2 :: IO ()
all_tc_x2 = all_tc_x X

foreign export ccall "all_tc_x2" all_tc_x2 :: IO ()

The specialized version inlines the definitions for the typeclass dictionary, which enables GHC to reduce the entire output to an empty tuple allocation. That’s just 4 instructions, ignoring the FFI wrapper code.

0000000000000730 <all_tc_x2>:
730: sub rsp,0x18
734: call 739 <all_tc_x2+0x9>
====> 739: mov rdx,QWORD PTR [rip+0x0] # RELOCATION
740: mov rsi,QWORD PTR [rip+0x0] # RELOCATION
747: mov rdi,rax
74a: mov QWORD PTR [rsp],rax
74e: call 753 <all_tc_x2+0x23> # RELOCATION
753: lea rdx,[rsp+0x8]
758: mov rsi,rax
75b: mov rdi,rsp
75e: call 763 <all_tc_x2+0x33> # RELOCATION
763: mov rsi,QWORD PTR [rsp]
767: lea rdi,[rip+0x0] # RELOCATION
76e: call 773 <all_tc_x2+0x43>
773: mov rdi,QWORD PTR [rsp]
777: call 77c <all_tc_x2+0x4c> # RELOCATION
77c: add rsp,0x18
780: ret

Relocation section '.rela.text' at offset 0xd50 contains 39 entries:
Offset Sym. Name + Addend
====> 00000000073c ClassX_zdfstableZZC0ZZ - 4

0000000000000610 <ClassX_zdfstableZZC0ZZCmainZZCClassXZZCallzzutczzux2_info>:
====> 610: jmp 5c8 <ClassX_zdfstableZZC0ZZCmainZZCClassXZZCallzzutczzux1_info>

00000000000005c8 <ClassX_zdfstableZZC0ZZCmainZZCClassXZZCallzzutczzux1_info>:
====> 5c8: mov rax,QWORD PTR [rip+0x0] # RELOCATION
5cf: lea rbx,[rax+0x1]
5d3: jmp QWORD PTR [rbp+0x0]

Relocation section '.rela.text' at offset 0xd50 contains 39 entries:
Offset Sym. Name + Addend
====> 0000000005cb ghczmprim_GHCziTuple_Z - 4

You can write specialized versions like above, or use the SPECIALIZE pragma to generate them. Using a separate specialized function may make it easier to see that specialization is happening, however.

Conclusion

Both abstract classes and typeclasses carry along an implicit array of function pointers. C++ generates this array at compile-time, while Haskell generates it at runtime. Once generated, it’s passed along as a simple pointer that generic code can index into to find an overridable implementation for a function.

Future programming language implementation articles may cover:

  • Multi-parameter typeclasses, typeclass hierarchies, and typeclasses over recursive higher-order types
  • Dependent types
  • JIT compilation
  • Garbage collectors
  • Type-checking