Python中`x in range(...)`成员检查的异常速度现象探究

测试背景与结果 #

测试中定义r = range(1500, 2500)，分别针对取值小于区间范围、位于区间范围内、大于区间范围三种场景，对x in r操作开展基准性能测试，得到结果如下：

1000 in r :   58 ns ± 0 ns
2000 in r :  101 ns ± 1 ns
3000 in r :   58 ns ± 0 ns

从表面逻辑看，小于下界的1000、大于上界的3000检查速度快于区间内的2000似乎符合直觉：边界外的值不需要完整校验所有规则就能返回False，区间内的值需要完成全部校验才能返回True。但这里有两个容易让人困惑的问题：

• range对象的成员检查逻辑是否会动态选择优先校验哪一侧边界？
• 为什么两类边界外场景的检查速度完全一致，且都比区间内值的检查快近一倍？

基准测试代码 #

本次测试使用的代码如下：

from timeit import repeat
from statistics import mean, stdev

setup = 'r = range(1500, 2500)'

n = 10**4
for _ in range(3):
    for x in 1000, 2000, 3000:
        code = f'{x} in r'
        ts = repeat(code, setup, number=n, repeat=100)
        ts = [t/n * 1e9 for t in sorted(ts)[:10]]
        print(code, ':  %3d ns ± %d ns' % (mean(ts), stdev(ts)))
    print()

核心原理 #

range的成员检查逻辑 不存在动态选择校验边界顺序的机制，整个判断流程是CPython源码中写死的固定逻辑，针对默认步长为1的正序range，执行顺序为：

1. 快速路径判断：如果待检查值刚好等于range的起点或终点，直接返回True
2. 下界判断：如果待检查值小于range起点，直接返回False
3. 上界判断：如果待检查值大于等于range终点，直接返回False
4. 步长校验：计算「待检查值 - 起点」的结果，判断该值能否被步长整除，能整除返回True，否则返回False

对照测试结果就能解释所有性能差异：

• 对1000（小于下界）：执行到第2步就直接返回False，仅需2次快速相等判断+1次整数比较
• 对3000（大于上界）：执行到第3步直接返回False，仅需2次快速相等判断+2次整数比较
• 对2000（区间内）：需要走完所有4步，除了比较操作外，还要额外执行减法、取余两个算术操作，耗时显著更高

至于1000和3000检查耗时完全一致的原因非常简单：整数比较是单CPU周期级别的操作，两者差的1次比较带来的耗时差小于当前基准测试的纳秒级统计分辨率，因此最终表现为耗时相同。

注：针对负步长的range，源码会自动调整上下界判断的逻辑适配步长方向，整体判断流程的开销分布和正序range完全一致。

内容的提问来源于stack exchange，提问作者Kelly Bundy