内联缓存

内联缓存是用于运行时优化的流行技术。它于1984年在Deutsch＆amp; Schiffman的论文《 smalltalk-80系统的高效实现》 [PDF]，但在当今的动态语言实现中却有着悠久的历史。像Hotspot JVM，V8和SpiderMonkey这样的运行时都使用它来提高为这些虚拟机编写的代码的性能。

在本博客文章中，我将尝试使用专门为此博客文章构建的小型且相对无用的字节码解释器来提取内联缓存的本质。该演示中的缓存策略是一种类似于Inline Caching满足Quickening [PDF]的思想的技术，因为它缓存函数指针而不是使用JIT编译器。

在许多已编译的编程语言（如C和C ++）中，类型和属性位置在编译时是已知的。这样可以使代码如下所示：

编译器精确地知道left和right是什么类型（它是Foo），以及方法add在可执行文件中的位置。如果实现位于头文件中，则甚至可以内联它，并且do_add可以优化为单个指令。从objdump中检出程序集：

0000000000401160＆lt; _Z6do_add3FooS_＆gt ;: 401160：48 83 ec 18 sub $ 0x18，％rsp 401164：89 7c 24 0c mov％edi，0xc（％rsp）401168：48 8d 7c 24 0c lea 0xc（％rsp），％rdi 40116d ：e8 0e 00 00 00 callq 401180＆lt; _ZN3Foo3addES_＆gt; 401172：48 83 c4 18加$ 0x18，％rsp 401176：c3 retq

它所做的只是将参数保存到堆栈中，调用Foo :: add，然后还原堆栈。

在更动态的编程语言中，通常无法在运行时启动时确定任何给定变量绑定的类型。我们将以Python为例，说明动态性如何使这一难题变得棘手，但是这种约束广泛适用于Ruby，JavaScript等。

由于Python的各种动态功能，编译器通常无法知道类型值是什么，因此在读取left.add时将无法运行什么代码。该程序将被编译为几个Python字节码指令，它们执行非常通用的LOAD_METHOD / CALL_METHOD操作：

＆gt;＆gt;＆gt; import dis＆gt;＆gt; dis.dis（＆＃34;＆＃34;＆＃34; ... def do_add（left，right）：... return left.add（right）...＆＃34;＆＃34;＆＃ 34;）[snip]在0x7f0b40cf49d0的文件对象do_add的反汇编中，文件＆＃34;＆lt; dis＆gt;＆＃34 ;，第2行>：3 0 LOAD_FAST 0（左）2 LOAD_METHOD 0（添加）4 LOAD_FAST 1 （右）6 CALL_METHOD 1 8 RETURN_VALUE＆gt;＆gt;

该LOAD_METHOD Python字节码指令与x86移动指令的不同之处在于，LOAD_METHOD的偏移量不为左，而是命名为＆＃34; add＆＃34;。它必须去弄清楚如何从左侧的类型读取添加内容-可能会因通话而异。

实际上，即使键入了参数（这是Python3中的新功能），也会生成相同的代码。左写：Foo表示左是Foo或子类。

这不是一个简单的过程，例如“以类型指定的给定偏移量获取属性”。运行时必须找出什么样的对象addis。可能只是一个函数，或者是一个属性，或者是一些自定义描述符协议。无法将其变成动静！

尽管动态运行时不预先知道给定操作码的变量类型，但它们最终会确定何时运行代码。第一次有人调用do_add时，LOAD_METHOD将去查找左类型。它将使用它来查找属性add，然后丢弃类型信息。但是第二次有人调用do_add时，会发生同样的事情。为什么运行时不存储有关类型和方法的信息并保存查找工作？

这种想法是“好吧，左边可能是任何类型的对象，最好不要对此做任何假设。”尽管从技术上讲这是正确的，但Deutsch＆amp; Schiffman发现“在代码的给定点，接收器通常与上次执行代码的同一点的接收器具有相同的类”。

注意：对于接收者，它们表示从中加载属性的事物。这是一些面向对象的编程术语。

这是巨大的。这意味着，即使在这种充满动态行为的海洋中，人类实际上也不是那么有创造力，而是倾向于编写在给定位置只能看到少数类型的函数。

Smalltalk-80论文描述了一种运行时，它通过向函数添加“内联缓存”来利用这一点。这些内联缓存跟踪在代码的每个点看到的变量类型，以便运行时可以使用该信息做出优化决策。

我把一台只有几个操作的小型堆栈机放在一起。有很少的功能可以避免从主要焦点上转移注意力：内联缓存。扩展此示例将是一项极好的练习。

这个运行时的设计涉及两种类型的对象（int和strs）。对象被实现为带标签的并集，但就本博客文章而言，表示形式并不重要。

typedef枚举{kInt，kStr，} ObjectType; typedef struct {ObjectType类型;联合{const char * str_value; int int_value; }; }对象;

这些类型具有方法，例如添加和打印。方法名称用枚举（Symbol）表示，尽管字符串也可以使用。

类型信息的表示并不重要。只知道有一个名为lookup_method的函数，而且它非常慢。最终，我们将要缓存其结果。

无法直接调用这些方法。在本演示中，调用这些方法的唯一方法是通过专门构建的操作码。例如，操作码ADD有两个参数。它在左侧查找kAdd并调用它。 PRINT是相似的。

typedef enum {//从arguments数组的索引arg＆＃39;处加载一个值。 ARG，//添加堆栈[-2] +堆栈[-1]。 ADD，//弹出堆栈的顶部并打印。 PRINT，//停止机器。 HALT，}操作码;

字节码由一系列操作码/参数对表示，每个对占用一个字节。只有ARG需要争论。其他说明忽略它们。

byte bytecode [] = {/ * 0：* / ARG，0，/ * 2：* / ARG，1，/ * 4：* / ADD，0，/ * 6：* / PRINT，0，/ * 8： * / HALT，0};

该程序使用其两个参数，将它们加在一起，打印结果，然后停止解释器。

您可能会想，“怎么有一条加载参数的指令却没有调用指令？”好吧，解释器不支持呼叫。只有一个顶级函数eval_code。它获取一个对象，使用给定的参数评估其字节码，然后返回。扩展解释器以支持函数调用将是另一个不错的练习。

解释器实现是一个相当简单的switch语句，注意它采用了函数式事物（Code）和参数数组的表示形式。 nargs仅用于边界检查。

typedef无符号字符字节； typedef struct {ObjectType键；方法值; } CachedValue; typedef struct {//`num_opcodes＆＃39;的数组； （op，arg）对（总大小为num_opcodes＆＃39; * 2）。字节*字节码; int num_opcodes; //`num_opcodes＆＃39;的数组元素。 CachedValue *缓存； }代码;静态无符号kBytecodeSize = 2;无效eval_code_uncached（代码*代码，对象*参数，整数nargs）{int pc = 0; #define STACK_SIZE 100对象stack_array [STACK_SIZE];对象* stack = stack_array; #define PUSH（x）* stack ++ =（x）#define POP（）*-stack while（true）{操作码op =代码-＆gt;字节码[pc];字节arg =代码->字节码[pc + 1];开关（op）{case ARG：CHECK（arg＆lt; nargs＆amp;＆＃34; out of bounds arg＆＃34;）; PUSH（args [arg]）;休息;案例ADD：{对象权限= POP（）;剩余对象= POP（）;方法method = lookup_method（左，type，kAdd）；对象结果=（*方法）（左，右）;推（结果）;休息; } case PRINT：{对象obj = POP（）;方法method = lookup_method（obj.type，kPrint）; （*方法）（obj）;休息; } HALT：返回；默认值：fprintf（stderr，＆＃34;未知操作码％d \ n＆＃34;，op）;中止（）; } pc + = kBytecodeSize; }}

ADD和PRINT都使用lookup_method找出与给定的（类型，符号）对相对应的功能指针。两种操作码都会丢弃结果。多么悲伤。让我们弄清楚如何保存其中的一些数据。也许我们可以使用Code中的缓存插槽。

由于Smalltalk-80论文告诉我们，接收器的类型不太可能在字节码中的给定点之间随调用而改变，因此让我们为每个操作码缓存一个方法地址。与任何缓存一样，我们必须同时存储键（对象类型）和值（方法地址）。

如果为空，则查找该方法并将其使用当前类型作为缓存键存储在缓存中。使用缓存的值。

如果它有一个条目并且该条目是当前类型的，请使用cachedvalue。

最后，如果它有一个条目并且该条目是用于其他类型的，则使缓存无效。重复执行与空箱相同的步骤。

这是一个简单的单态（一个元素）实现，应能提供最大的性能。一个好的练习是，如果解释器看到许多类型，则将该缓存系统扩展为多态的（多个元素）。为此，您将要查看Hölzle，Chambers和Ungar的《使用多态内联高速缓存优化动态类型的面向对象的语言》。

出于此内联缓存演示的目的，我们将重点介绍ADD中的缓存查找。在我们的简单运行时中，这是一个相当随意的选择，因为操作码之间的缓存实现不会有所不同。

看起来很适合我们。每个元素都有一个键和一个值，每个Code对象都有一个数组，每个操作码一个。

void eval_code_cached（Code * code，Object * args，int nargs）{// ... #define CACHE_AT（pc）代码-> caches [（pc）/ kBytecodeSize] while（true）{// ...切换（ op）{// ... case ADD：{对象权限= POP（）;剩余对象= POP（）; CachedValue已缓存= CACHE_AT（pc）;方法method =已缓存。价值; if（method == NULL || cached。key！= left。type）{//情况1和3 method = lookup_method（left。type，kAdd）; CACHE_AT（pc）=（CachedValue）{。键=左。类型，。值=方法}; }对象结果=（*方法）（left，right）;推（结果）;休息; } // ...} pc + = kBytecodeSize; }}

现在，我们不再总是调用lookup_method，而是首先进行两次快速检查。如果我们有一个缓存的值并且匹配，则使用它。实际上，除了对代码->高速缓存的读取和写入之外，没有多少。

让我们将它们放在一起以获得满意的结果。我们可以使用前面添加了两个参数的sampleprogram。

我们称呼它四次。第一次，我们将使用integerarguments调用它，并且它将缓存integer方法。第二次，它将使用缓存的整数方法。第三次，我们将使用stringarguments调用它，并将缓存string方法。第四次，它将使用缓存的字符串方法。

int main（）{字节字节码[] = {/ * 0：* / ARG，0，/ * 2：* / ARG，1，/ * 4：* / ADD，0，/ * 6：* / PRINT，0 ，/ * 8：* / HALT，0};对象int_args [] = {new_int（5），new_int（10），};对象str_args [] = {new_str（＆＃34; hello＆＃34;），new_str（＆＃34; world＆＃34;），};代码= new_code（bytecode，sizeof bytecode / kBytecodeSize）;无效（* eval）（）= eval_code_cached; eval（＆amp; code，int_args，ARRAYSIZE（int_args））; eval（＆amp; code，int_args，ARRAYSIZE（int_args））; eval（＆amp; code，str_args，ARRAYSIZE（str_args））; eval（＆amp; code，str_args，ARRAYSIZE（str_args））; }

从表面上看，至少它在起作用。 5 + 10 == 15和＆＃34; hello＆＃34; +＆＃34;世界＆＃34; ==＆＃34; Hello world＆＃34;毕竟。

为了深入了解缓存系统的行为，我添加了一些日志记录语句。这将帮助我们确信缓存代码可以正确执行。

月桂树％。/ a。在4int处更新缓存：15在4int处使用缓存的值：15在4str处更新缓存：＆＃34; hello world＆＃34;在4str处使用缓存的值：＆＃34; hello world＆＃34;

内联高速缓存可能是加速字节码解释器的好方法。我希望这篇文章可以帮助您了解内联缓存。如果没有，请写信给我。

这个非常简单的演示可以做很多改进，下面列出其中一些：

将通用操作码（如ADD）重写为类型专用的操作码（如ADD_INT）。这些操作码仍将必须检查传入的类型，但可以使用直接调用指令，甚至可以内联专门的实现。使用快速精通的有效解释[PDF]中提到了该技​​术，并且该技术已由JVM使用。

并非所有操作码都需要缓存，但无论如何我们都会为其分配缓存。 如何消除这些浪费的缓存插槽？ 而不是存储缓存的函数指针，而是建立一种处理不同类型案例的程序集存根的“链接列表”。 在Deutsch＆amp; 希夫曼论文。 例如，请参阅Matthew Gaudet撰写的这篇出色的文章，其中用伪代码对其进行了解释。 弄清楚如果运行时允许可变类型会发生什么。 您将如何使所有相关的缓存失效？ 热线网络：←上一个〜下一个→此博客是开源的。 看到错误？ 继续并提出更改建议。