内联缓存
| 此條目翻譯自其他語言維基百科，需要相關領域的編者協助校對翻譯。 |
| 此條目需要精通或熟悉相关主题的编者参与及协助编辑。 |
内联缓存（Inline caching）是部分编程语言的运行时系统采用的优化技术，最早为Smalltalk开发[1]。内联缓存的目标是通过记住以前直接在调用点上方法查询的结果来加快运行时方法绑定的速度。内联缓存对动态类型语言尤为有用，其中大多数（如非全部）方法绑定发生在运行时，因此虚方法表通常无法使用。
运行时方法绑定 编辑
下面的ECMAScript函数接收一个对象，调用其toString方法，并在脚本嵌入的页面上显示结果。
function dump(obj) { document.write(obj.toString()); } 由于没有指定对象的类型，并且有潜在的方法重载，所以不可能提前判断toString方法被调用的具体实现，因而就必须在运行时执行动态查询。在不采用某种形式缓存的语言运行时中，每次调用方法都将执行该查询。因为方法可能在多个继承链下定义，所以动态查询可能是一个昂贵的操作。
为取得更好的性能，许多语言运行时采用某种形式的非内联缓存，其中将有限数量的方法查找结果存储在关联数据结构中。这可以大大提高性能，只要执行的程序“缓存友好”，即有一组经常被调用的方法。这个数据结构通常称为第一级方法查找缓存（first-level method lookup cache）[1]。
内联缓存 编辑
内联缓存的概念基于观察到的经验，即发生在特定调用点（call site）的对象通常是相同的类型。在这种情况下，存储方法查询内联结果可以大幅提升性能，即直接抵达调用点。为做到这个过程，调用点会被分配不同的状态。在最初，调用点被认作“未初始化”。当语言运行时到达特定的未初始化调用点，它会执行一次动态查询，在调用点存储结果并将其状态改为“单态”。如果语言运行时再次来到相同的调用点，它接收此信息并直接调用，不再执行任何查找。考虑到同一调用点可能出现不同类型的对象，语言运行时也必须向代码插入守卫条件。通常来说，这被插入到被叫方的前导代码而非调用点，以便更好利用分支預測器和节约空间，因为前导代码中的一个副本可以与多个呼叫点的副本关联。如果处于“单态”状态的调用站遇到期望类型之外的类型，则必须改回“未初始化”状态并再次执行全动态查找。
典范实现[1]是一个常量寄存器加载，后跟一个调用指令。“未初始化（uninitialized）”状态称为“未链接（unlinked）”更佳。寄存器加载了消息选择器（通常是某个对象的地址），而调用是查找当前接收器的类中消息的一个例程，采用上面提过的一级方法查找缓存。然后，运行时例程重写指令，改变载入指令以载入具有当前接收器类型的寄存器，以及调用指令以调用目标方法的前导代码，将调用点“链接”到目标方法。随后继续立即执行前导代码。前导代码将导出当前接收器的类型，并与寄存器中的类型比较；如果认可接收器为同一类型，则继续执行该方法。如果不是，则前导代码再次调用运行时，并可能采用各种策略，其中一种是重新链接新的接收器类型的调用点。
单态内联缓存 编辑
如果一个特定调用点经常看到不同类型的对象，内联缓存的性能优势很容易被调用点状态的频繁变化引起的开销所抵消。以下示例构成单态内联缓存的最坏情况：
var values = [1, "a", 2, "b", 3, "c", 4, "d"]; for (var i in values) { document.write(values[i].toString()); } 同样，方法toString在一个无法事先预知类型的对象上调用。更重要的是，对象类型会随着周遭循环的每一次迭代而改变。单态内联缓存的天真实现会因此不断在“未初始化”与“单态”状态之间转换。为了防止这种情况发生，单态内联缓存的大多数实现支持第三种状态，通常称为“复态（megamorphic）”状态。当某个特定调用点看到预定数量的不同类型时则会进入该状态。一旦某个调用点进入“复态”状态，它就会像“未初始化”状态那样表现，除了它不会再进入“单态”状态（某些单态内联缓存的实现会在一段时间或者执行一次完整的垃圾回收周期后将“复态”调用点改回“未初始化”状态）。
多态内联缓存 编辑
为更好地处理经常看到有限数量不同类型的调用点，一些语言运行时采用称为多态内联缓存（polymorphic inline caching）的技术。[2]通过多态内联缓存，一旦处于其“单态”状态的调用点看到第二种类型，它不会回转到“未初始化”状态，而是切换到称为“多态”的新状态。多态调用点根据当前呈递的类型决定调用已知、有限的某一种方法。换句话说，通过多态内联缓存可以在同一个调用点记录多个方法查找结果。由于程序中的每个调用点都可能会看到系统中的每个类型，因此每个调用点上的记录上限通常是查找结果的上限。一旦达到上限，调用点就变成“复态（megamorphic）”并且不再执行更多内联缓存。
变形内联缓存 编辑
如果运行时同时采用单态和多态内联缓存，那么在稳定状态下，唯一的未链接的发送将是来自多态内联缓存结束的发送falling-off。由于这种发送速度很慢，因此优化这些网站现在可能比较有收益。创建代码来执行特定调用点的一级方法查找可以实现一个单态内联缓存。在这个方案中，一旦一个send falls-off在一个多态内联缓存的末尾，就会创建一个特定于调用点的选择器的高速缓存（如果已存在则共享），并且发送站点被重新链接来调用它。这样的代码可以比普通的一级方法查询探测器更有效率，因为选择器现在是一个常量，可以降低寄存器压力，查询和调用代码的执行无需进入运行时，并且调度可以从分支預測器中受益。
根据测量[3]显示，在大型Smalltalk程序中，所有活动方法的发送点有大约1/3维持未链接，其余2/3中，90%为单态（monomorphic），9%为多态（polymorphic），1%（准确来说0.9%）为复态（megamorphic）。
参见 编辑
- 记忆化（memoization）
参考资料 编辑
- ^ 1.0 1.1 1.2 L. Peter Deutsch, Allan M. Schiffman, "Efficient implementation of the smalltalk-80 system", POPL '84: Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, January 1984
- ^ 2.0 2.1 2.2 Hölzle, U., Chambers, C., AND Ungar, D. 1991. Optimizing dynamically-typed object-oriented languages with polymorphic inline caches. In Proceedings of the ECOOP ’91 Conference. Lecture Notes in Computer Science, vol. 512. Springer-Verlag, Berlin.
- ^ PICs [was v8 first impressions] on the Strongtalk mailing list
外部链接 编辑
- Article on Inline Caching in the Cog Smalltalk VM （页面存档备份，存于互联网档案馆）