Method dispatch using a vtable (a pointer, embedded in the object, pointing to a record of methods) is way faster than practically any other form of dynamic dispatch (except calls of known functions, of course). To support it, you pretty much need some form of single inheritance/subtyping (C++ does support multiple inheritance, but it significantly complicates the implementation). Rust's single-dispatch type-classes and Go's interfaces are dispatched in a similar way, but the record of functions is passed along the pointer to object as a "fat pointer". Servo people figured out that that is too wasteful/slow compared to C++-style vtable approach.

I assume it's based on (this is a bit hand wavy) the fact that in an OO language, calling the method merely needs to resolve the address space of the method. With pattern matching, you first have to perform the pattern match to figure out what instruction to execute, and then that resolves to an address.

That is, because your data and function are bundled together, having the data means you also know what function to call. Decoupling them, as in a functional paradigm, and passing the data into a pattern match, you have to perform some logic upon the data to figure out what function to apply to it.

But, a series of pattern matching expressions can compile down to a bunch of sealed/final classes that descend from a common base class. In that case, it would still end up using a vtable[1]. I think this is how it works in F# and Scala.

[1] I think that the JITs for the CLR and JVM can do better than vtables in the cases of sealed/final classes.

I am sure it doesn't work with way in either scala or F#. You can use classes to represent structure, but the matching is still extrinsic and can't use a table given the flexibility of both languages (you don't just match on class).

Just curious… why not? Isn't a class definition just a type constructor? For instance, if I have a class, Foo, with three types of fields: int, bool, and string, isn't that the same as:

    Foo of int * bool * string
 

I don't have a full PC handy, but, while learning F# a few years ago, I remember using Reflector to analyze an assembly generated by FSC.exe and the pattern match turned into a class hierarchy.

It may not work for all kinds of pattern matching, but that seems like the most straightforward way of handling sum types. What am I missing?

I doubt that was what was going on, but I can't find any documentation right now on how F# optimizes case matches. If it was doing that, it would have to apply those classes to all instances of the patterns, which seems unlikely in the face of separate compilation as "Foo of int * bool * string" could be constructed in a far away place. Well, if Foo was a local type that wouldn't escape, perhaps they could optimize it in the module, but it still seems unlikely.

OO languages have trouble optimizing constructs such as interfaces (and other forms of multiple inheritance) because the v-table is no longer very linear. Now throw in arbitrary predicates and you are pretty much back to linear search. Probably the state of the art can be found in GHC, but even they probably fall back to linear in a lot of cases.

Looks like you're correct; I just examined some F# code in LINQPad 4, and the IL has a bunch of `isinst` instructions to check the type at runtime, and no `callvirts` to the one pattern matching expression that I created.

https://gist.github.com/noblethrasher/af1b382fa6e0423bf8bd