Why is method dispatch sometimes slow?

Question

Reading some old posts on caml-list I came across the following post by Jacques Garrigues: http://caml.inria.fr/pub/ml-archives/caml-list/2007/11/24e8215c8d844b05db58ed3f79c9645f.en.html

The quote that I care about is the following:

Method calls on arbitrary objects can be slow. This is because, due to subtyping, in some situations there is no way to know where the method will be in the table, and a binary search has to be done.

Can anybody explain why this is the case? Why exactly subtyping (inheritance I'm assuming in this case) is affecting this? Is this the case for OCaml's implementation or do other languages suffer from this as well?

Please point me towards further resources regarding this, google has failed me.

Answer 1

I think that delnan's comment that, in OCaml, “Subtyping != inheritance” holds the insight to the explanation.

$ rlwrap ocaml
        OCaml version 4.00.1

# let f o = o#x + o#y ;;
val f : < x : int; y : int; .. > -> int = <fun>
# 

Function f above accepts any object o that has methods x : int and y : int. Not objects that inherit from some class c in which an offset for these methods could have been fixed in advance, mind you. Any object with these methods. I guess this is difficult to implement, and may be one of the cases Jacques is referring to in his message.

Answer 2

Can anybody explain why this is the case?

With nominal typing each method can be assigned a unique integer at compile time so a virtual function can be found by indexing into an array. With structural typing (as in OCaml) this cannot be done so a hash of the structure (i.e. method name) is used to search for virtual method's function pointer in a dictionary.

Why exactly subtyping (inheritance I'm assuming in this case) is affecting this?

Subtypes are a prerequisite for virtual dispatch.

Is this the case for OCaml's implementation or do other languages suffer from this as well?

Just OCaml's implementation. In F#, I have used reflection and run-time code generation to achieve the same effect with no such invoke-time performance hit.