Python位运算与divmod性能差异：divmod(n,16)为何耗时更长？

背景与测试环境 #

• 开发一款Python应用，通过反复截断被除数末尾数字并转换为更小数字来判断整除性
• 运行环境：Windows 10系统、Python 3.7.10、P5处理器，基于PyCharm开发
• 测试目的：对比右移4位实现除以16与divmod()的性能

测试代码 #

import math
import datetime
from sys import getsizeof

def PrintTime(startTime, message):
    seconds_in_day = 24 * 3600
    later_time = datetime.datetime.now()
    difference = later_time - first_time
    time_diff = 10 ** 6 * (difference.days * seconds_in_day + difference.seconds) + difference.microseconds
    print(message + str(time_diff / 10 ** 6))

myVariable = 3 ** 100000 - 1
hLength = math.ceil(math.log(myVariable)/math.log(16))
dLength = math.ceil(math.log(myVariable)/math.log(10))
print('Length in hex' + ' ' + str(hLength) + '. Decimal length ' + str(dLength) + ' Size of myVariable ' + str(getsizeof(myVariable)))
n = myVariable

first_time = datetime.datetime.now()
for i1 in range(0, hLength - 1):
    a = n >> 4
    b = n & 0xF
    n = n - 1761 * b
PrintTime(first_time, 'Hex truncation time: ')

n = myVariable
first_time = datetime.datetime.now()
for i2 in range(0, hLength - 1):
   n, r = divmod(n, 10)
PrintTime(first_time, 'divmod time - base 10: ')

n = myVariable
first_time = datetime.datetime.now()
for i2 in range(0, dLength - 1):
   n, r = divmod(n, 16)
PrintTime(first_time, 'divmod time - base 16: ')

测试输出 #

Length in hex 39625. Decimal length 47713 Size of myVariable 21160
Hex truncation time: 0.614306
divmod time - base 10: 0.526677
divmod time - base 16: 1.42582

疑问解答 #

首先纠正测试代码里的细节：第二个测试对divmod(n,10)执行了39624次，第三个测试对divmod(n,16)执行了47712次——次数差了约20%，但性能差三倍，显然次数不是核心原因。

Python整数的内部存储是二进制，不存在“转十进制运算再转回十六进制”的情况，性能差异的核心原因在于：

• divmod(n,10)有专门优化：十进制是日常最常用的进制，CPython底层对除以10、取余10这类操作做了大量针对性优化，能高效处理大整数的十进制截断，速度自然更快。
• divmod(n,16)未触发位运算优化：虽然16是2的幂次，理论上可以用右移、按位与这类高效位操作实现，但Python的divmod函数并没有针对所有2的幂次做特殊映射，而是走通用的大整数除法逻辑，执行流程更复杂，速度也就慢很多。

另外，第三个测试的循环次数更多，进一步拉大了时间差，但即使修正循环次数到一致，divmod(n,16)还是会比divmod(n,10)慢不少，核心还是底层优化的差异。

内容的提问来源于stack exchange，提问作者Sin Keong Tong