作者：修玉同(音弦)

在 2021 年早些时候，Python 作者 Guido van Rossum 被微软返聘持续进行 CPython 相干工作，他们提出了一个 faster-python 打算，打算在 4 年内将 CPython 的性能晋升 5 倍，整个我的项目被凋谢在 GitHub 的 faster-cpython Group，通过 Activity 可见该项目标一部分 ideas 曾经有了相应的代码实现和验证。

本文将就该我的项目中的一个重要提案 PEP 659 进行解读和源码剖析，并从中学习在 bytecode level 进行虚拟机性能优化的思路和伎俩，心愿能对大家有所启发。

提案解读

PEP 659 创立于 2021 年 4 月，全称为 Specializing Adaptive Interpreter，这里有两个关键词：Specializing 和 Adaptive，这里能够简略了解为对 特定地位 的代码进行适配（Adaptive），替换 为非凡的代码（Specializing）从而进步特定地位操作的执行速度。比方通过观察发现某个查问 dict 的代码在屡次执行过程中 dict 没有变动，那么咱们能够针对这段代码进行优化，将 dict entry 的 index 间接缓存起来，这样在下次查问时就防止了 hashtable 查找的过程从而进步性能，这里的察看就对应到 Adaptive，替换代码的过程则对应到 Specializing。

下面的例子并不精确，只是帮忙大家对 Specializing Adaptive Interpreter 有一个初步的印象，上面咱们将摘录提案中的要害语句进行解读。

首先要明确的一点是，PEP 659 并不是一个 JIT 计划，因为它的初衷在于让那些无奈间接应用 PyPy 等蕴含 JIT Compiler 的用户也能享受到 faster CPython 的红利。例如在 iOS 平台下，用户过程受限于 codesign 动态创建的可执行的代码页在缺页中断时会因为未蕴含非法签名而被回绝，因而无奈间接应用蕴含 JIT Compiler 的 Python 虚拟机。

看到这里可能有些人会放心，不应用 JIT 单纯从虚拟机层面进行优化的空间和收益如何呢？在 PEP 659 中作者也给出了一些解释：

Specialization is typically done in the context of a JIT compiler, but research shows specialization in an interpreter can boost performance significantly, even outperforming a naive compiler.

即钻研发现仅仅在 Interpreter 层面进行 Specialization 优化也能够取得显著的性能晋升，性能收益甚至能够超过一些高级的 JIT 计划，作者在这里还援用了一篇本人之前的论文，感兴趣的同学能够自行去 PEP 659 提案的参考文献局部查看。

到这里咱们也就明确了 PEP 659 不蕴含 JIT Compiler，简略地说就是它不生成代码，它只是代码的搬运工，咱们须要穷举所有可能的优化状况，并且提前准备好代码，在察看到匹配的优化条件时将字节码进行替换，当发现不满足优化条件时还必须可能优雅的退回到优化前的代码以保障程序的正确性。

为了能更好的穷举优化状况和切换代码，须要抉择适合的优化粒度，提案原文是：

By using adaptive and speculative specialization at the granularity of individual virtual machine instructions, we get a faster interpreter that also generates profiling information for more sophisticated optimizations in the future.

即在虚拟机指令层面进行优化，而不是像 JIT 那样在一个区域或者函数维度进行优化，这样能够针对特定指令进行细分，例如在 CPython 中获取 globals 和 builtins 都是通过 LOAD_GLOBAL 指令，首先在 globals 中查找，查找失败后再 fallback 到 builtins 中查找，在这里可能的状况只有 2 种，因而咱们能够为虚拟机新增两条指令 LOAD_GLOBAL_MODULE 和 LOAD_GLOBAL_BUILTIN，当发现某段字节码中的 LOAD_GLOBAL 始终在查找 globals 时，咱们能够将其优化为前者，反之优化为后者，同时能够对 globals 和 builtins dict 的 entry index 进行缓存防止反复拜访 dict 的 hashtable，当发现不满足优化条件（例如查找失败，或是 dict 被批改）时再回滚到 LOAD_GLOBAL 指令保障程序的正确性。

上述从 LOAD_GLOBAL 到 LOAD_GLOBAL_MODULE / LOAD_GLOBAL_BUILTIN 的过程实际上就是 PEP 题目中的 Specializing，而抉择将指令替换为 LOAD_GLOBAL_MODULE 还是 LOAD_GLOBAL_BUILTIN 的过程其实就是 Adaptive，它的职责是察看特定代码中的指令的执行状况，认为其抉择正确的优化指令，察看的过程也是虚拟机代码执行的过程，因而在这里还须要额定引入一个 Adaptive 指令 LOAD_GLOBAL_ADAPATIVE 用来执行察看和替换逻辑。

尽管说 Specializing 可能通过缩小判断和减少缓存来提速，但从原始指令到 Adaptive 指令，从 Adaptive 察看得出 Specializing 指令的过程也是有损耗的，因而须要基于肯定的策略进行优化，而不是无脑的尝试优化所有代码中的指令，原文中提到：

Typical optimizations for virtual machines are expensive, so a long “warm up” time is required to gain confidence that the cost of optimization is justified.

即对虚拟机的 Specializing 优化是低廉的，这种低廉体现在咱们须要在字节码执行的大循环中插入优化代码，甚至在每一次循环都须要额定的解决逻辑，而很多代码可能都只会执行一次，如果对他们进行优化纯属浪费时间，因而咱们须要找出那些须要优化的代码，这样代码的一个次要特点是被高频调用，咱们能够对每个 PyCodeObject (CPython 中保留字节码和环境信息的对象) 减少计数器，只有执行次数超过某个阈值才执行优化逻辑，这个过程被称之为 warm up。

在虚拟机层面，当某个字节码对象 PyCodeObject 被执行（能够简略了解为一段 Python 代码对应的字节码被执行）或是产生相对跳转时，代码对象的 co_warmup 计数器会被累加，当达到阈值后这段字节码中所有可优化指令都会被替换为 Adaptive 指令进行察看和特殊化，尔后这些指令只会在 Adaptive 和 Specializing 之间转换，当 Specializing 指令的优化条件被毁坏时，咱们不会立刻回滚到 Adaptive 指令，而是容许肯定次数的 miss 以防止出现优化和去优化之间的平稳，同样的当去优化回滚到 Adaptive 指令后咱们也会暂停察看和优化逻辑，让指令依照原始逻辑运行一段时间，这个过程被称为 deferred，整个过程的状态图如下：

[]()

到这里咱们曾经对 PEP 659 的原理和大抵工作过程有了理解，但为了高性能的实现这个优化器还有很多细节须要探讨，例如哪些指令须要优化，如何优雅的替换指令和还原，如何设计指令缓存等，这些具体问题单纯从实践层面剖析太过干燥和艰涩，因而接下来咱们将联合 Python 3.11 中 PEP 659 的源码实现来进行解说。

源码剖析

实际上 PEP 659 的基础设施和局部优化指令曾经在 CPython 3.11 的分支上有所体现，咱们这里以 LOAD_GLOBAL 革新为例对上述流程进行粗疏剖析，之所以抉择 LOAD_GLOBAL 是因为它在虚拟机层面的操作较为简单，只波及到两个命名空间的查找，优化和去优化判断也比拟间接，足够清晰的阐明问题又不会因为指令的艰涩给大家的浏览带来艰难。

整个优化过程次要包含 Warmup, Adaptive, Specializing & Deoptimize 这几个阶段，上面咱们将就各阶段的性能和外围代码做一些剖析和解说。

Warmup

如上文所述，warmup 解决的问题是找到真正高频执行的代码，防止优化那些尔后再也不会被执行到的代码，这里咱们不须要计算代码执行的频率，只须要设定一个阈值，并对特定的字节码对象 PyCodeObject 的执行次数计数，当达到阈值时认为实现了 warmup，因而在这里咱们为 PyCodeObject 引入了一个新字段 co_warmup：

/* Bytecode object */
struct PyCodeObject {
    PyObject_HEAD
    // The hottest fields (in the eval loop) are grouped here at the top.
    PyObject *co_consts;        /* list (constants used) */
    PyObject *co_names;         /* list of strings (names used) */
     // ...
    int co_warmup;              /* Warmup counter for quickening */
     // ...

   /* Quickened instructions and cache, or NULL
     This should be treated as opaque by all code except the specializer and
     interpreter. */
    union _cache_or_instruction *co_quickened;
};

在 PyCodeObject 对象被创立时，co_warmup 的初始值被设定为 QUICKENING_WARMUP_DELAY，它是一个负值，每当 PyCodeObject 被执行或是在代码内产生相对跳转时 co_warmup 会 +1，当达到阈值 0 后则进入优化逻辑：

#define QUICKENING_WARMUP_DELAY 8
/* We want to compare to zero for efficiency, so we offset values accordingly */
#define QUICKENING_INITIAL_WARMUP_VALUE (-QUICKENING_WARMUP_DELAY)

static void
init_code(PyCodeObject *co, struct _PyCodeConstructor *con) {
    // ...
    co->co_warmup = QUICKENING_INITIAL_WARMUP_VALUE;
    co->co_quickened = NULL;
}

Adaptive

当 co_warmup 被累加到 0 后，会走到 _Py_Quicken 函数执行优化逻辑，因为波及到字节码调整，官网在这里为原始字节码 co_code 拷贝了一份正本寄存在 quickened 中，尔后的所有批改都产生在 quickened 中：

/* Bytecode object */
struct PyCodeObject {
    PyObject_HEAD
    // The hottest fields (in the eval loop) are grouped here at the top.
    PyObject *co_consts;        /* list (constants used) */
    PyObject *co_names;         /* list of strings (names used) */
   _Py_CODEUNIT *co_firstinstr; /* Pointer to first instruction, used for quickening. */
    // ...
    PyObject *co_code;          /* instruction opcodes */
  
   /* Quickened instructions and cache, or NULL
     This should be treated as opaque by all code except the specializer and
     interpreter. */
    union _cache_or_instruction *co_quickened;
};

typedef uint16_t _Py_CODEUNIT;

int
_Py_Quicken(PyCodeObject *code) {if (code->co_quickened) {return 0;}
    Py_ssize_t size = PyBytes_GET_SIZE(code->co_code);
    int instr_count = (int)(size/sizeof(_Py_CODEUNIT));
    if (instr_count > MAX_SIZE_TO_QUICKEN) {
        code->co_warmup = QUICKENING_WARMUP_COLDEST;
        return 0;
    }
    int entry_count = entries_needed(code->co_firstinstr, instr_count);
    SpecializedCacheOrInstruction *quickened = allocate(entry_count, instr_count);
    if (quickened == NULL) {return -1;}
    _Py_CODEUNIT *new_instructions = first_instruction(quickened);
    memcpy(new_instructions, code->co_firstinstr, size);
    optimize(quickened, instr_count);
    code->co_quickened = quickened;
    code->co_firstinstr = new_instructions;
    return 0;
}

看到下面的代码你可能会纳闷为什么 quickened 蕴含了除去字节码以外的额定空间，实际上仅仅通过指令替换是难以实现优化的，咱们还须要对指令操作的对象尽可能进行缓存，以 LOAD_GLOBAL 为例，最坏状况咱们须要查 2 次字典，第一次查 globals，第二次查 builtins，在 CPython 中字典底层是 hashtable，因而在产生 hash 碰撞时它的复杂度是大于 O(1) 的。为了优化变动不频繁的字典，咱们能够将 key 对应的 hashtable index 进行缓存，显然这些缓存和指令是一一对应的，因而 quickened 的额定空间的作用就是存储优化后指令的额定信息。

quickened 是一个双向数组，右边寄存是 cache，左边寄存字节码，在数组的最左端额定调配了一个 cache entry 用来存储 cache count，通过 cache count 咱们能够疾速定位到字节码数组，后面看到的 first_instruction 就是通过 cache_count 从 quickened 定位到 instr 0 的：

/* We layout the quickened data as a bi-directional array:
 * Instructions upwards, cache entries downwards.
 * first_instr is aligned to a SpecializedCacheEntry.
 * The nth instruction is located at first_instr[n]
 * The nth cache is located at ((SpecializedCacheEntry *)first_instr)[-1-n]
 * The first (index 0) cache entry is reserved for the count, to enable finding
 * the first instruction from the base pointer.
 * The cache_count argument must include space for the count.
 * We use the SpecializedCacheOrInstruction union to refer to the data
 * to avoid type punning.

 Layout of quickened data, each line 8 bytes for M cache entries and N instructions:

 <cache_count>                              <---- co->co_quickened
 <cache M-1>
 <cache M-2>
 ...
 <cache 0>
 <instr 0> <instr 1> <instr 2> <instr 3>    <--- co->co_first_instr
 <instr 4> <instr 5> <instr 6> <instr 7>
 ...
 <instr N-1>
*/

每条被优化的指令都须要独立的 cache entries，咱们须要一种伎俩 O(1) 的从指令索引到 cache，在 Python 3 中每条指令包含 8 bit 的 opcode 和 8 bit 的 operand，官网抉择应用 offset + operand 构建二级索引，这里的 offset 用来确定索引的块范畴（这里有点像页表搜寻，offset 代表 PAGE，operand 代表 PAGEOFF），operand 用来修改 offset，被索引笼罩的 operand 则寄存在 cache 中，上述设计在 PEP 659 中的原文如下：

For instructions that need specialization data, the operand in the quickened array will serve as a partial index, along with the offset of the instruction, to find the first specialization data entry for that instruction.

对于 LOAD_GLOBAL 而言，须要缓存的次要是 dict 的版本信息以及 key index，此外还有一些优化器所需的额定信息，具体如下：

1. 字典键值对的版本 dk_version，因为这里同时波及到 globals 和 builtins，咱们须要缓存两个 dk_version，每个 dk_version 都是一个 uint32_t，所以加起来 dk_version 须要一个 8B，也就是一个 cache entry；
2. key 对应的 index，它是一个 uint16_t，因为咱们曾经占用了一个 cache entry，这里只能再应用一个额定的 cache entry；
3. 因为原来的 operand 被用来做 partial index，咱们还须要额定的一个 uint8_t 来存储 original_oparg，这个能够和 2 中的 uint16_t 合并存储；
4. 在提案解读局部咱们提到在 Adaptive, Specilization 和 Deoptimize 之间转换须要一个计数器缓冲来防止平稳，须要一个 counter，官网在这里应用了一个 uint8_t。

综合上述剖析，LOAD_GLOBAL 须要两个 cache entry，第一个存储 orignal_oparg + counter + index，第二个存储 globals 和 builtins 的 dk_version：

typedef struct {
    uint8_t original_oparg;
    uint8_t counter;
    uint16_t index;
} _PyAdaptiveEntry;

typedef struct {
    uint32_t module_keys_version;
    uint32_t builtin_keys_version;
} _PyLoadGlobalCache;

剖析到这里其实施行 Adaptive 策略曾经瓜熟蒂落了，对于 LOAD_GLOBAL 而言无外乎查找 globals 和 builtins，当某个 LOAD_GLOBAL 在 Adaptive 逻辑中命中 globals 时，咱们将其优化为 LOAD_GLOBAL_MODULE，缓存好 index 和 module_keys_version 即可；当某个 LOAD_GLOBAL 没有命中 globals 时，咱们须要同时缓存 module_keys_version 和 builtin_keys_version，这是因为当 globals 发生变化后可能导致下次 LOAD_GLOBAL 不再命中 builtins，在这里咱们将其优化为 LOAD_GLOBAL_BUILTIN，这个优化抉择和缓存的过程实际上就是 Adaptive。

Specializing & Deoptimize

如上文所述，字节码对象 PyCodeObject 在通过了 Warmup 和 Adaptive 过程之后其中可优化指令均已变成了 Specialized 模式，例如 LOAD_GLOBAL 曾经全副以 LOAD_GLOBAL_MODULE 或 LOAD_GLOBAL_BUILTIN 的模式存在（这里先不思考 Deoptimize），用大白话说就是字节码中的指令实现了对以后环境的最优适配，上面咱们来看看这些适配的代码是怎么的。

其实通过下面的剖析，置信大家曾经把适配代码猜个八九不离十了，上面咱们以较为简单的 LOAD_GLOBAL_BUILTIN 为例剖析一下源码：

TARGET(LOAD_GLOBAL_BUILTIN) {
  // ...
    PyDictObject *mdict = (PyDictObject *)GLOBALS();
    PyDictObject *bdict = (PyDictObject *)BUILTINS();
    SpecializedCacheEntry *caches = GET_CACHE();
    _PyAdaptiveEntry *cache0 = &caches[0].adaptive;
    _PyLoadGlobalCache *cache1 = &caches[-1].load_global;
    DEOPT_IF(mdict->ma_keys->dk_version != cache1->module_keys_version, LOAD_GLOBAL);
    DEOPT_IF(bdict->ma_keys->dk_version != cache1->builtin_keys_version, LOAD_GLOBAL);
    PyDictKeyEntry *ep = DK_ENTRIES(bdict->ma_keys) + cache0->index;
    PyObject *res = ep->me_value;
    DEOPT_IF(res == NULL, LOAD_GLOBAL);
    STAT_INC(LOAD_GLOBAL, hit);
    Py_INCREF(res);
    PUSH(res);
    DISPATCH();}

咱们先疏忽 DEOPT_IF 看一下主逻辑，首先取出以后命令的 cache entries，第一个 entry 记录了 index，第二个 entry 记录了 globals 和 builtins 的 dk_version，在缓存命中的状况下咱们只须要从 builtins dict 的 hashtable[index] 取出键值对，将它的 value 返回即可，相比于原来先查 globals dict 再查 builtins dict 着实快了不少。

然而先不要快乐太早，该少的缩小其实一个都少不了，咱们晓得只有 globals 找不到的时候才会去找 builtins，如果 globals 变了那缓存必然会生效，此外咱们的 index 缓存前提也是 builtins dict 不能扭转，综合上述两点咱们必须先确认两个字典的 dk_version 都没变能力继续执行，这其实也是 Deoptimize 的触发条件之一，这正是 DEOPT_IF 所做的事件：

#define DEOPT_IF(cond, instname) if (cond) {goto instname ## _miss;}
#define JUMP_TO_INSTRUCTION(op) goto PREDICT_ID(op)
#define ADAPTIVE_CACHE_BACKOFF 64

static inline void
cache_backoff(_PyAdaptiveEntry *entry) {entry->counter = ADAPTIVE_CACHE_BACKOFF;}

LOAD_GLOBAL_miss: 
{STAT_INC(LOAD_GLOBAL, miss); 
    _PyAdaptiveEntry *cache = &GET_CACHE()->adaptive; 
    cache->counter--; 
    if (cache->counter == 0) {next_instr[-1] = _Py_MAKECODEUNIT(LOAD_GLOBAL_ADAPTIVE, _Py_OPARG(next_instr[-1])); 
        STAT_INC(LOAD_GLOBAL, deopt); 
        cache_backoff(cache); 
    } 
    oparg = cache->original_oparg; 
    STAT_DEC(LOAD_GLOBAL, unquickened); 
    JUMP_TO_INSTRUCTION(LOAD_GLOBAL); 
}

DEOPT_IF 做的事件是跳到指令的 cache miss 分支，对于 LOAD_GLOBAL 是 LOAD_GLOBAL_miss，miss 分支做的事件十分固定，首先能够明确的是它会 fallback 到惯例的 LOAD_GLOBAL 分支（底部的 JUMP_TO_INSTRUCTION），但它永远不会将指令回滚到 LOAD_GLOBAL，只会在 Adaptive 和 Specialized 指令之间转移。为了防止缓存平稳，下面的代码会在 counter 递加到 0 时才进化到 Adaptive 指令，在此之前会始终尝试先拜访缓存。

到这里整个优化和去优化过程咱们就剖析完了，整个流程还是比较复杂的，但具备显著的套路，只有构建好 Cache 和 Adaptive 基础设施，对其余指令的革新就比拟容易了。通过这种形式进行指令减速的一个难点是如何设计缓存以缩小分支，因为 DEOPT_IF 的存在咱们很难间接缩小前置的条件判断，只能将其转化为更高效的模式。

关注【阿里巴巴挪动技术】微信公众号，每周 3 篇挪动技术实际 & 干货给你思考！