如何提高巨型多态调用点的效率？有哪些不同的技术可以使用？

Question

前言

本文旨在提高即时编译器中消息发送的效率。尽管参考了Smalltalk，但这个问题适用于大多数动态JIT编译的语言。

问题

给定一个消息发送站点，它可以被分类为单态、多态或巨态。如果消息发送的接收者始终是相同类型，则为单态发送，例如

10 timesRepeat: [Object new].

new 的接收者始终为 Object。对于这种情况，JIT 会生成单态内联缓存。

有时一个给定的发送站点会引用几种不同的对象类型，例如：

#(1 'a string' 1.5) do: [:element | element print]

在这种情况下，print被发送到不同类型的对象。对于这些情况，JIT通常会发出多态内联缓存。

当消息发送到不仅是一些而是许多不同的对象类型时，就会发生巨型多态消息发送。其中最突出的例子之一是这个：

Behavior>>#new
    ^self basicNew initialize

这里，basicNew创建对象，然后initialize进行初始化。你可以这样做：

Object new
OrderedCollection new
Dictionary new

他们将都执行相同的Behavior>>#new方法。由于initialize在许多类中的实现不同，PIC将很快填满。我对这种发送站点很感兴趣，知道它们只偶尔发生（仅有1%的发送是megamorphic）。

问题

有哪些可能和具体的优化方法可以避免在megamorphic发送站点进行查找？

- melkyades

Answer 1

我已经想到了一些方法，但还想了解更多。当一个PIC（polymorphic inline cache）被填满后，我们就需要调用查找（无论是查找缓存还是全局缓存），但为了优化，我们可以：

• 回收PIC，并且删除所有的记录（很多记录可能是旧的并且不常用）。
• 调用某种特定的巨态查找（例如缓存所有之前分派类型的数组，并以类型哈希值进行访问）。
• 内联包含的方法（内联后，发送站点可能不再是巨态的）。

- melkyades

---

将像 #initialize 这样的巨型选择器提升到附加到接收者的 MethodDictionary 的特殊位置，以便缩短它们的查找时间，这个想法怎么样？ - Leandro Caniglia

这些特殊位置会是什么？它们如何附加到接收器的MethodDictionary中？ - melkyades

我不确定。但是，字典提供了很多将事物附加到它们上的可能性！例如，我会考虑添加一个关联到MD，并使用一些保留的键（比如SmallInteger），并将超多态方法复制到那里。由于所有选择器都是符号（而不是SmallIntegers），因此不会与“常规”消息发生冲突。但再次强调，这只是需要更多思考和一些实验的想法。 - Leandro Caniglia

Answer 2

如下论文所建议的，可以将megamorphic发送更改为使用vtable查找。

考虑到非常少的选择器是megamorphic的，分配选择器索引，其中每个选择器都专门知道其索引，应该会产生紧凑的跳转向量，这些向量可以懒惰地添加到每个使用其megamorphic方法的类中。

Manuel Serrano和Marc Feeley，《属性缓存再探讨》。在编译器构造国际会议（CC'19）上，2019年2月。

http://www.iro.umontreal.ca/~feeley/papers/SerranoFeeleyCC19.pdf

- Ken.Dickey

Answer 3

我们知道调用点是多态的。 我们知道只有1%的发送是多态的。 我们知道"我们将不得不调用查找"。

这意味着我们已经在做类似的事情

methodDictionary at: selector ifAbsent: [并且我们在这里]

所以我们知道这是我们第一次来到这里， 我们知道没有很多多态案例， 所以如果我们在这里，我们应该检查一下是否 这是一个“特殊”的选择器，如果是的话， 我们可以确保我们不再来到这里

methodDictuionary at: selector put: (查找结果)

这将扩展字典，但仅适用于 是“特殊”的选择器，并且仅适用于最顶层的查找（在接收者的类中）。当然，对于接收者中未定义的选择器的每次查找都会产生更多的开销。（每个这样的情况都已经产生了查找的开销）。

Q1：所有多态选择器都是“特殊”的吗？

Q2：我们能否定义“特殊”集合，以便在不使用太多空间的情况下获得足够的速度？

问题3：我们能够足够快地进行这个“特殊”测试吗？

问题4：这算什么，如果是的话，是否足够？

- Jim Sawyer