为什么方法调度有时会变慢？

Question

阅读caml-list上的一些旧帖子我发现Jacques Garrigues的以下帖子:http://caml.inria.fr/pub/ml-archives/caml-list/2007/11/24e8215c8d844b05db58ed3f79c9645f.en.html

我关心的引用如下:

对任意对象的方法调用可能很慢.这是因为,由于子类型的原因,在某些情况下无法知道方法在表中的位置,并且必须进行二进制搜索.

任何人都可以解释为什么会这样吗？为什么确切的子类型(在这种情况下我假设继承)会影响这个？这是OCaml实现的情况还是其他语言也受此影响？

请指出我有关此的更多资源,谷歌已经失败了我.

Answer 1

我认为delnan的评论是,在OCaml中,"Subtyping!= inheritance"对解释持有洞察力.

$ rlwrap ocaml
        OCaml version 4.00.1

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

f上面的函数接受任何o具有方法x : int和的对象y : int.请注意,不是从某些类继承的对象,c其中可以提前修复这些方法的偏移量.具有这些方法的任何对象.我想这很难实现,可能是雅克在他的信息中提到的案例之一.

@rgrinberg你说"哈希表查找"就好像它是最便宜的实现,但事实并非如此.与具有编译时常量索引的数组查找相比,散列表查找和二进制搜索(显然实际使用)显着(对于此抽象级别)较慢. (4认同)

Answer 2

任何人都可以解释为什么会出现这种情况吗？

通过标称类型，可以在编译时为每个方法分配一个唯一的整数，以便可以通过索引到数组来找到虚拟函数。对于结构类型（如在 OCaml 中），这是无法完成的，因此结构的散列（即方法名称）用于在字典中搜索虚拟方法的函数指针。

为什么子类型（我在本例中假设是继承）会影响这一点？

子类型是虚拟调度的先决条件。

OCaml 的实现是这种情况还是其他语言也受到这种情况的影响？

只是 OCaml 的实现。在 F# 中，我使用反射和运行时代码生成来实现相同的效果，而不会影响调用时性能。