为什么 python 中的字符串比较如此之快？
Why is string comparison so fast in python?
当我解决以下示例算法问题时，我很想了解 python 中字符串比较的内部原理：
Given two strings, return the length of the longest common prefix
方案一：charByChar
我的直觉告诉我，最佳解决方案是在两个单词的开头以一个光标开始，并向前迭代，直到前缀不再匹配。像
def charByChar(smaller, bigger):
assert len(smaller) <= len(bigger)
for p in range(len(smaller)):
if smaller[p] != bigger[p]:
return p
return len(smaller)
为简化代码，该函数假定第一个字符串的长度 smaller 始终小于或等于第二个字符串的长度 bigger。
解决方案 2：二进制搜索
另一种方法是平分两个字符串以创建两个前缀子字符串。如果前缀相等，我们知道公共前缀点至少与中点一样长。否则公共前缀点至少不大于中点。然后我们可以递归查找前缀长度。
又名二进制搜索。
def binarySearch(smaller, bigger):
assert len(smaller) <= len(bigger)
lo = 0
hi = len(smaller)
# binary search for prefix
while lo < hi:
# +1 for even lengths
mid = ((hi - lo + 1) // 2) + lo
if smaller[:mid] == bigger[:mid]:
# prefixes equal
lo = mid
else:
# prefixes not equal
hi = mid - 1
return lo
起初我假设 binarySearch 会比较慢，因为字符串比较会多次比较所有字符，而不是像 charByChar.
那样只比较前缀字符
令人惊讶的是，binarySearch 经过一些初步的基准测试后发现速度要快得多。
图A
上面显示了随着前缀长度的增加，性能是如何受到影响的。后缀长度保持不变，为 50 个字符。
这张图显示了两件事：
- 正如预期的那样，随着前缀长度的增加，两种算法的性能都呈线性下降。
charByChar 的性能以更快的速度下降。
为什么 binarySearch 好多了？我想是因为
- The string comparison in
binarySearch is presumably optimized by the interpreter / CPU behind the scenes.
charByChar actually creates new strings for each character accessed and this produces significant overhead.
为了验证这一点，我对比较和切片字符串的性能进行了基准测试，下面分别标记为 cmp 和 slice。
图B
这张图显示了两个重要的事情：
- 不出所料，比较和切片随长度线性增加。
- 相对于算法性能，比较和切片的成本随着长度的增加非常缓慢，如图 A。请注意，这两个数字都达到了长度为 10 亿个字符的字符串。因此，比较1个字符10亿次的代价要比比较10亿个字符一次的代价要大的多。但这仍然没有回答为什么...
Cpython
为了找出 cpython 解释器如何优化字符串比较，我为以下函数生成了字节码。
In [9]: def slice_cmp(a, b): return a[0] == b[0]
In [10]: dis.dis(slice_cmp)
0 LOAD_FAST 0 (a)
2 LOAD_CONST 1 (0)
4 BINARY_SUBSCR
6 LOAD_FAST 1 (b)
8 LOAD_CONST 1 (0)
10 BINARY_SUBSCR
12 COMPARE_OP 2 (==)
14 RETURN_VALUE
我查看了 cpython 代码并找到了以下 two pieces 代码，但我不确定这是进行字符串比较的地方。
问题
- Where in the cpython does string comparison occur?
- Is there a CPU optimization? Is there a special x86 instruction which does string comparison? How can I see what assembly instructions are generated by cpython? You may assume I am using python3 latest, Intel Core i5, OS X 10.11.6.
- Why is comparing a long string so much faster than comparing each of it's characters?
附加问题：charByChar 何时性能更高？
如果与字符串的其余长度相比前缀足够小，则在某些时候在 charByChar 中创建子字符串的成本会低于在 binarySearch 中比较子字符串的成本.
为了描述这种关系，我深入研究了运行时分析。
运行时分析
为了简化下面的等式，我们假设 smaller 和 bigger 大小相同，我将它们称为 s1 和 s2。
charByChar
charByChar(s1, s2) = costOfOneChar * prefixLen
哪里
costOfOneChar = cmp(1) + slice(s1Len, 1) + slice(s2Len, 1)
其中 cmp(1) 是比较两个长度为 1 个字符的字符串的成本。
slice是访问一个char的开销，相当于charAt(i)。 Python 具有不可变字符串，访问 char 实际上会创建一个长度为 1 的新字符串。slice(string_len, slice_len) 是将长度为 string_len 的字符串切成大小为 slice_len 的切片的成本.
所以
charByChar(s1, s2) = O((cmp(1) + slice(s1Len, 1)) * prefixLen)
二进制搜索
binarySearch(s1, s2) = costOfHalfOfEachString * log_2(s1Len)
log_2是将字符串分成两半直到达到长度为1的字符串的次数。其中
costOfHalfOfEachString = slice(s1Len, s1Len / 2) + slice(s2Len, s1Len / 2) + cmp(s1Len / 2)
所以binarySearch的big-O会根据
增长
binarySearch(s1, s2) = O((slice(s2Len, s1Len) + cmp(s1Len)) * log_2(s1Len))
根据我们之前对
成本的分析
如果我们假设 costOfHalfOfEachString 大约是 costOfComparingOneChar 那么我们可以将它们都称为 x。
charByChar(s1, s2) = O(x * prefixLen)
binarySearch(s1, s2) = O(x * log_2(s1Len))
如果我们把它们等同起来
O(charByChar(s1, s2)) = O(binarySearch(s1, s2))
x * prefixLen = x * log_2(s1Len)
prefixLen = log_2(s1Len)
2 ** prefixLen = s1Len
所以 O(charByChar(s1, s2)) > O(binarySearch(s1, s2) 当
2 ** prefixLen = s1Len
所以插入上面的公式，我重新生成了图 A 的测试，但字符串总长度 2 ** prefixLen 预计两种算法的性能大致相等。
然而，显然 charByChar 表现得更好。通过反复试验，两种算法的性能在 s1Len = 200 * prefixLen
时大致相等
为什么关系是 200x？
这既取决于实现又取决于硬件。在不知道你的目标机器和具体分布的情况下，我不能肯定地说。但是，我强烈怀疑底层硬件与大多数硬件一样具有内存块指令。除其他事项外，这可以以并行和流水线方式比较一对任意长的字符串（达到寻址限制）。例如，它可以在每个时钟周期一个片上比较 8 字节片。这比摆弄字节级索引快 很多。
TL:DR：切片比较是一些 Python 开销 + 高度优化的 memcmp（除非有 UTF-8 处理？）。理想情况下，使用 slice 比较来找到第一个小于 128 字节或类似内容的不匹配，然后一次循环一个字符。
或者，如果这是一个选项并且问题很重要，请制作一个 asm 优化的 memcmp 的修改副本，returns 第一个差异的位置，而不是 equal/not-equal ;它将 运行 与整个字符串中的单个 == 一样快。 Python 可以调用库中的原生 C / asm 函数。
这是一个令人沮丧的限制，CPU 可以非常快地执行此操作，但 Python 不会（AFAIK）让您访问优化的比较循环，该循环告诉您不匹配的位置而不是等于/大于/小于。
在一个简单的 Python 循环中，解释器开销在实际工作成本中占主导地位是完全正常的，CPython。使用优化的构建块构建算法是值得的，即使这意味着需要做更多的工作。这就是为什么 NumPy 很好，但是逐个元素地遍历矩阵却很糟糕。速度差异可能是 20 到 100 的一个因素，对于 CPython 与编译的 C (asm) 循环，用于一次比较一个字节（组成数字，但可能在一个顺序内震级）。
比较内存块是否相等可能是 Python 循环与在整个列表/切片上操作之间最大的不匹配之一。这是高度优化解决方案的常见问题（例如，大多数 libc 实现（包括 OS X）都有一个手动矢量化的手工编码 asm memcmp，它使用 SIMD 并行比较 16 或 32 字节，并且运行s much 比 C 或汇编中的一次一个字节的循环快）。因此，还有另一个 16 到 32 的因数（如果内存带宽不是瓶颈）乘以 Python 和 C 循环之间的 20 到 100 速度差异的因数。或者取决于您的 memcmp 的优化程度，可能 "only" 每个周期 6 或 8 个字节。
对于中型缓冲区的 L2 或 L1d 缓存中的热数据，在 Haswell 或更高版本 CPU 上 memcmp 每个周期预计 16 或 32 字节是合理的。 （i3/i5/i7 命名以 Nehalem 开头；仅 i5 不足以告诉我们很多关于您的 CPU。）
我不确定你的比较是否有一个或两个必须处理 UTF-8 并检查等效性 类 或不同的方式来编码相同的字符。最坏的情况是，如果您的 Python 一次一个字符循环必须检查潜在的多字节字符，但您的切片比较只能使用 memcmp.
在Python中写一个高效的版本：
我们只是为了提高效率而完全与语言作斗争：你的问题几乎与 C 标准库函数 memcmp 完全相同，除了你想要 position[=133] =] 的第一个差异而不是 - / 0 / + 结果告诉你哪个字符串更大。搜索循环是相同的，只是函数在找到结果后所做的事情有所不同。
您的二进制搜索不是使用快速比较构建块的最佳方式。切片比较仍然有 O(n) 成本，而不是 O(1)，只是常数因子小得多。您可以而且应该避免重复比较缓冲区的开始，方法是 使用切片比较大块，直到发现不匹配，然后返回具有较小块大小的最后一个块。
# I don't actually know Python; consider this pseudo-code
# or leave an edit if I got this wrong :P
chunksize = min(8192, len(smaller))
# possibly round chunksize down to the next lowest power of 2?
start = 0
while start+chunksize < len(smaller):
if smaller[start:start+chunksize] == bigger[start:start+chunksize]:
start += chunksize
else:
if chunksize <= 128:
return char_at_a_time(smaller[start:start+chunksize], bigger[start:start+chunksize])
else:
chunksize /= 8 # from the same start
# TODO: verify this logic for corner cases like string length not a power of 2
# and/or a difference only in the last character: make sure it does check to the end
我选择 8192 是因为您的 CPU 有一个 32kiB L1d 缓存，所以两个 8k 切片的总缓存占用空间为 16k，是您的 L1d 的一半。当循环发现不匹配时，它将重新扫描 1k 块中的最后 8kiB，这些比较将循环 L1d 中仍然热的数据。 （请注意，如果 == 发现不匹配，它可能只触及到该点的数据，而不是整个 8k。但是 HW 预取将继续超出那个范围。）
因子 8 应该是使用大切片快速定位与不需要对相同数据进行多次传递之间的良好平衡。当然，这是一个可调参数，还有块大小。 Python 和 asm 之间的不匹配越大，这个因素应该越小以减少 Python 循环迭代。）
希望 8k 足够大以隐藏 Python 循环/切片开销；在来自解释器的 memcmp 调用之间的 Python 开销期间，硬件预取应该仍然有效，因此我们不需要 g运行 性太大。但是对于非常大的字符串，如果 8k 不会使内存带宽饱和，那么可能会达到 64k（您的 L2 缓存是 256kiB；i5 确实告诉了我们很多）。
memcmp到底怎么这么快：
I am running this on Intel Core i5 but I would imagine I would get the same results on most modern CPUs.
即使在 C 中，Why is memcmp so much faster than a for loop check? memcmp 也比一次一个字节的比较循环更快，因为即使是 C 编译器也不擅长（或完全不能）自动向量化搜索循环。
即使没有硬件 SIMD 支持，优化的 memcmp 也可以一次检查 4 或 8 个字节（字大小/寄存器宽度），即使在没有 16 字节或 32 字节的简单 CPU 上也是如此字节 SIMD.
但是大多数现代 CPU 和所有 x86-64 都有 SIMD 指令。 SSE2 is baseline for x86-64，并在 32 位模式下作为扩展可用。
SSE2 或 AVX2 memcmp 可以使用 pcmpeqb / pmovmskb 并行比较 16 或 32 字节。 （我不打算详细介绍如何在 x86 asm 中或使用 C 内在函数编写 memcmp。Google 分别地，and/or 在 x86 指令集参考中查找这些 asm 指令。比如http://felixcloutier.com/x86/index.html. See also the x86 tag wiki for asm and performance links. e.g. 有一些关于单核内存带宽限制的信息。）
我在他们的开源网站上找到了 an old version from 2005 of Apple's x86-64 memcmp（使用 AT&T 语法汇编语言）。肯定会更好；对于大缓冲区，它应该对齐一个源指针并且只使用 movdqu 用于另一个，允许 movdqu 然后 pcmpeqb 内存操作 运行d 而不是 2x movdqu，即使字符串相对于彼此未对齐。 xorl [=34=]xFFFF,%eax / jnz 在 CPU 上也不是最优的，其中 cmp/jcc 可以宏融合但 xor / jcc 不能。
一次展开检查整个 64 字节缓存行也会隐藏循环开销。 （这与大块的想法相同，然后在找到命中时循环返回）。 Glibc's AVX2-movbe version 与 vpand 一起执行此操作以在主大缓冲区循环中组合比较结果，最终组合是 vptest，它还根据结果设置标志。 （比 vpand/vpmovmskb/cmp/jcc 更小的代码大小，但不低于 uops；但没有缺点，而且延迟可能更低，以减少 b运行ch - 错误预测循环退出的惩罚）。 Glibc 在动态 link 时间进行动态 CPU 调度；它在支持它的 CPU 上选择这个版本。
希望 Apple 的 memcmp 最近更好；不过，我在最近的 Libc 目录中根本看不到它的源代码。希望他们在 运行 时间为 Haswell 和之后的 CPUs 发送 AVX2 版本。
我 linked 版本中的 LLoopOverChunks 循环在 Haswell 上每 ~2.5 个周期仅 运行 1 次迭代（每个输入 16 个字节）； 10 个融合域微指令。但这仍然比天真的 C 循环每个周期 1 个字节快得多，或者比 Python 循环差得多。
Glibc 的 L(loop_4x_vec): 循环是 18 个融合域 uops，因此当数据在 L1d 缓存中处于热状态时，每个时钟周期 运行 仅略小于 32 字节（来自每个输入） .否则会成为 L2 带宽的瓶颈。如果他们没有在循环内使用额外的指令递减一个单独的循环计数器，并在循环外计算一个结束指针，它可能是 17 微指令。
在Python解释器自己的代码中寻找指令/热点
How could I drill down to find the C instructions and CPU instructions that my code calls?
在 Linux 上，您可以 运行 perf record python ... 然后 perf report -Mintel 查看 CPU 花费最多时间的函数以及其中的指令这些功能是最热门的。您会得到类似于我在此处发布的结果：Why is float() faster than int()?。 （深入到任何函数以查看 运行 的实际机器指令，显示为汇编语言，因为 perf 内置了反汇编程序。）
有关对每个事件的调用图进行采样的更细微的视图，请参阅 linux perf: how to interpret and find hotspots。
（当你想要真正优化一个程序时，你想知道哪些函数调用是昂贵的，所以你可以首先尝试避免它们。分析"self" 时间会找到热点，但您不会总是知道哪些不同的调用者导致给定循环 运行 大多数迭代。请参阅 Mike Dunlavey 对该性能问题的回答。）
但是对于这种特定情况，分析解释器 运行 在大字符串上使用切片比较版本应该有望找到 memcmp 循环，我认为它将花费大部分时间。（或者对于一次一个字符的版本，找到 "hot" 的解释器代码。）
然后就可以直接看到循环中有哪些asm指令了。从函数名称，假设您的二进制文件有任何符号，您可能可以找到源代码。或者，如果您有一个使用调试信息构建的 Python 版本，您可以直接从配置文件信息获取源代码。 （不是禁用优化的调试版本，只有完整的符号）。
当我解决以下示例算法问题时，我很想了解 python 中字符串比较的内部原理：
Given two strings, return the length of the longest common prefix
方案一：charByChar
我的直觉告诉我，最佳解决方案是在两个单词的开头以一个光标开始，并向前迭代，直到前缀不再匹配。像
def charByChar(smaller, bigger):
assert len(smaller) <= len(bigger)
for p in range(len(smaller)):
if smaller[p] != bigger[p]:
return p
return len(smaller)
为简化代码，该函数假定第一个字符串的长度 smaller 始终小于或等于第二个字符串的长度 bigger。
解决方案 2：二进制搜索
另一种方法是平分两个字符串以创建两个前缀子字符串。如果前缀相等，我们知道公共前缀点至少与中点一样长。否则公共前缀点至少不大于中点。然后我们可以递归查找前缀长度。
又名二进制搜索。
def binarySearch(smaller, bigger):
assert len(smaller) <= len(bigger)
lo = 0
hi = len(smaller)
# binary search for prefix
while lo < hi:
# +1 for even lengths
mid = ((hi - lo + 1) // 2) + lo
if smaller[:mid] == bigger[:mid]:
# prefixes equal
lo = mid
else:
# prefixes not equal
hi = mid - 1
return lo
起初我假设 binarySearch 会比较慢，因为字符串比较会多次比较所有字符，而不是像 charByChar.
令人惊讶的是，binarySearch 经过一些初步的基准测试后发现速度要快得多。
图A
上面显示了随着前缀长度的增加，性能是如何受到影响的。后缀长度保持不变，为 50 个字符。
这张图显示了两件事：
- 正如预期的那样，随着前缀长度的增加，两种算法的性能都呈线性下降。
charByChar的性能以更快的速度下降。
为什么 binarySearch 好多了？我想是因为
- The string comparison in
binarySearchis presumably optimized by the interpreter / CPU behind the scenes.charByCharactually creates new strings for each character accessed and this produces significant overhead.
为了验证这一点，我对比较和切片字符串的性能进行了基准测试，下面分别标记为 cmp 和 slice。
图B
这张图显示了两个重要的事情：
- 不出所料，比较和切片随长度线性增加。
- 相对于算法性能，比较和切片的成本随着长度的增加非常缓慢，如图 A。请注意，这两个数字都达到了长度为 10 亿个字符的字符串。因此，比较1个字符10亿次的代价要比比较10亿个字符一次的代价要大的多。但这仍然没有回答为什么...
Cpython
为了找出 cpython 解释器如何优化字符串比较，我为以下函数生成了字节码。
In [9]: def slice_cmp(a, b): return a[0] == b[0]
In [10]: dis.dis(slice_cmp)
0 LOAD_FAST 0 (a)
2 LOAD_CONST 1 (0)
4 BINARY_SUBSCR
6 LOAD_FAST 1 (b)
8 LOAD_CONST 1 (0)
10 BINARY_SUBSCR
12 COMPARE_OP 2 (==)
14 RETURN_VALUE
我查看了 cpython 代码并找到了以下 two pieces 代码，但我不确定这是进行字符串比较的地方。
问题
- Where in the cpython does string comparison occur?
- Is there a CPU optimization? Is there a special x86 instruction which does string comparison? How can I see what assembly instructions are generated by cpython? You may assume I am using python3 latest, Intel Core i5, OS X 10.11.6.
- Why is comparing a long string so much faster than comparing each of it's characters?
附加问题：charByChar 何时性能更高？
如果与字符串的其余长度相比前缀足够小，则在某些时候在 charByChar 中创建子字符串的成本会低于在 binarySearch 中比较子字符串的成本.
为了描述这种关系，我深入研究了运行时分析。
运行时分析
为了简化下面的等式，我们假设 smaller 和 bigger 大小相同，我将它们称为 s1 和 s2。
charByChar
charByChar(s1, s2) = costOfOneChar * prefixLen
哪里
costOfOneChar = cmp(1) + slice(s1Len, 1) + slice(s2Len, 1)
其中 cmp(1) 是比较两个长度为 1 个字符的字符串的成本。
slice是访问一个char的开销，相当于charAt(i)。 Python 具有不可变字符串，访问 char 实际上会创建一个长度为 1 的新字符串。slice(string_len, slice_len) 是将长度为 string_len 的字符串切成大小为 slice_len 的切片的成本.
所以
charByChar(s1, s2) = O((cmp(1) + slice(s1Len, 1)) * prefixLen)
二进制搜索
binarySearch(s1, s2) = costOfHalfOfEachString * log_2(s1Len)
log_2是将字符串分成两半直到达到长度为1的字符串的次数。其中
costOfHalfOfEachString = slice(s1Len, s1Len / 2) + slice(s2Len, s1Len / 2) + cmp(s1Len / 2)
所以binarySearch的big-O会根据
binarySearch(s1, s2) = O((slice(s2Len, s1Len) + cmp(s1Len)) * log_2(s1Len))
根据我们之前对
成本的分析如果我们假设 costOfHalfOfEachString 大约是 costOfComparingOneChar 那么我们可以将它们都称为 x。
charByChar(s1, s2) = O(x * prefixLen)
binarySearch(s1, s2) = O(x * log_2(s1Len))
如果我们把它们等同起来
O(charByChar(s1, s2)) = O(binarySearch(s1, s2))
x * prefixLen = x * log_2(s1Len)
prefixLen = log_2(s1Len)
2 ** prefixLen = s1Len
所以 O(charByChar(s1, s2)) > O(binarySearch(s1, s2) 当
2 ** prefixLen = s1Len
所以插入上面的公式，我重新生成了图 A 的测试，但字符串总长度 2 ** prefixLen 预计两种算法的性能大致相等。
然而，显然 charByChar 表现得更好。通过反复试验，两种算法的性能在 s1Len = 200 * prefixLen
为什么关系是 200x？
这既取决于实现又取决于硬件。在不知道你的目标机器和具体分布的情况下，我不能肯定地说。但是，我强烈怀疑底层硬件与大多数硬件一样具有内存块指令。除其他事项外，这可以以并行和流水线方式比较一对任意长的字符串（达到寻址限制）。例如，它可以在每个时钟周期一个片上比较 8 字节片。这比摆弄字节级索引快 很多。
TL:DR：切片比较是一些 Python 开销 + 高度优化的 memcmp（除非有 UTF-8 处理？）。理想情况下，使用 slice 比较来找到第一个小于 128 字节或类似内容的不匹配，然后一次循环一个字符。
或者，如果这是一个选项并且问题很重要，请制作一个 asm 优化的 memcmp 的修改副本，returns 第一个差异的位置，而不是 equal/not-equal ;它将 运行 与整个字符串中的单个 == 一样快。 Python 可以调用库中的原生 C / asm 函数。
这是一个令人沮丧的限制，CPU 可以非常快地执行此操作，但 Python 不会（AFAIK）让您访问优化的比较循环，该循环告诉您不匹配的位置而不是等于/大于/小于。
在一个简单的 Python 循环中，解释器开销在实际工作成本中占主导地位是完全正常的，CPython。使用优化的构建块构建算法是值得的，即使这意味着需要做更多的工作。这就是为什么 NumPy 很好，但是逐个元素地遍历矩阵却很糟糕。速度差异可能是 20 到 100 的一个因素，对于 CPython 与编译的 C (asm) 循环，用于一次比较一个字节（组成数字，但可能在一个顺序内震级）。
比较内存块是否相等可能是 Python 循环与在整个列表/切片上操作之间最大的不匹配之一。这是高度优化解决方案的常见问题（例如，大多数 libc 实现（包括 OS X）都有一个手动矢量化的手工编码 asm memcmp，它使用 SIMD 并行比较 16 或 32 字节，并且运行s much 比 C 或汇编中的一次一个字节的循环快）。因此，还有另一个 16 到 32 的因数（如果内存带宽不是瓶颈）乘以 Python 和 C 循环之间的 20 到 100 速度差异的因数。或者取决于您的 memcmp 的优化程度，可能 "only" 每个周期 6 或 8 个字节。
对于中型缓冲区的 L2 或 L1d 缓存中的热数据，在 Haswell 或更高版本 CPU 上 memcmp 每个周期预计 16 或 32 字节是合理的。 （i3/i5/i7 命名以 Nehalem 开头；仅 i5 不足以告诉我们很多关于您的 CPU。）
我不确定你的比较是否有一个或两个必须处理 UTF-8 并检查等效性 类 或不同的方式来编码相同的字符。最坏的情况是，如果您的 Python 一次一个字符循环必须检查潜在的多字节字符，但您的切片比较只能使用 memcmp.
在Python中写一个高效的版本：
我们只是为了提高效率而完全与语言作斗争：你的问题几乎与 C 标准库函数 memcmp 完全相同，除了你想要 position[=133] =] 的第一个差异而不是 - / 0 / + 结果告诉你哪个字符串更大。搜索循环是相同的，只是函数在找到结果后所做的事情有所不同。
您的二进制搜索不是使用快速比较构建块的最佳方式。切片比较仍然有 O(n) 成本，而不是 O(1)，只是常数因子小得多。您可以而且应该避免重复比较缓冲区的开始，方法是 使用切片比较大块，直到发现不匹配，然后返回具有较小块大小的最后一个块。
# I don't actually know Python; consider this pseudo-code
# or leave an edit if I got this wrong :P
chunksize = min(8192, len(smaller))
# possibly round chunksize down to the next lowest power of 2?
start = 0
while start+chunksize < len(smaller):
if smaller[start:start+chunksize] == bigger[start:start+chunksize]:
start += chunksize
else:
if chunksize <= 128:
return char_at_a_time(smaller[start:start+chunksize], bigger[start:start+chunksize])
else:
chunksize /= 8 # from the same start
# TODO: verify this logic for corner cases like string length not a power of 2
# and/or a difference only in the last character: make sure it does check to the end
我选择 8192 是因为您的 CPU 有一个 32kiB L1d 缓存，所以两个 8k 切片的总缓存占用空间为 16k，是您的 L1d 的一半。当循环发现不匹配时，它将重新扫描 1k 块中的最后 8kiB，这些比较将循环 L1d 中仍然热的数据。 （请注意，如果 == 发现不匹配，它可能只触及到该点的数据，而不是整个 8k。但是 HW 预取将继续超出那个范围。）
因子 8 应该是使用大切片快速定位与不需要对相同数据进行多次传递之间的良好平衡。当然，这是一个可调参数，还有块大小。 Python 和 asm 之间的不匹配越大，这个因素应该越小以减少 Python 循环迭代。）
希望 8k 足够大以隐藏 Python 循环/切片开销；在来自解释器的 memcmp 调用之间的 Python 开销期间，硬件预取应该仍然有效，因此我们不需要 g运行 性太大。但是对于非常大的字符串，如果 8k 不会使内存带宽饱和，那么可能会达到 64k（您的 L2 缓存是 256kiB；i5 确实告诉了我们很多）。
memcmp到底怎么这么快：
I am running this on Intel Core i5 but I would imagine I would get the same results on most modern CPUs.
即使在 C 中，Why is memcmp so much faster than a for loop check? memcmp 也比一次一个字节的比较循环更快，因为即使是 C 编译器也不擅长（或完全不能）自动向量化搜索循环。
即使没有硬件 SIMD 支持，优化的 memcmp 也可以一次检查 4 或 8 个字节（字大小/寄存器宽度），即使在没有 16 字节或 32 字节的简单 CPU 上也是如此字节 SIMD.
但是大多数现代 CPU 和所有 x86-64 都有 SIMD 指令。 SSE2 is baseline for x86-64，并在 32 位模式下作为扩展可用。
SSE2 或 AVX2 memcmp 可以使用 pcmpeqb / pmovmskb 并行比较 16 或 32 字节。 （我不打算详细介绍如何在 x86 asm 中或使用 C 内在函数编写 memcmp。Google 分别地，and/or 在 x86 指令集参考中查找这些 asm 指令。比如http://felixcloutier.com/x86/index.html. See also the x86 tag wiki for asm and performance links. e.g.
我在他们的开源网站上找到了 an old version from 2005 of Apple's x86-64 memcmp（使用 AT&T 语法汇编语言）。肯定会更好；对于大缓冲区，它应该对齐一个源指针并且只使用 movdqu 用于另一个，允许 movdqu 然后 pcmpeqb 内存操作 运行d 而不是 2x movdqu，即使字符串相对于彼此未对齐。 xorl [=34=]xFFFF,%eax / jnz 在 CPU 上也不是最优的，其中 cmp/jcc 可以宏融合但 xor / jcc 不能。
一次展开检查整个 64 字节缓存行也会隐藏循环开销。 （这与大块的想法相同，然后在找到命中时循环返回）。 Glibc's AVX2-movbe version 与 vpand 一起执行此操作以在主大缓冲区循环中组合比较结果，最终组合是 vptest，它还根据结果设置标志。 （比 vpand/vpmovmskb/cmp/jcc 更小的代码大小，但不低于 uops；但没有缺点，而且延迟可能更低，以减少 b运行ch - 错误预测循环退出的惩罚）。 Glibc 在动态 link 时间进行动态 CPU 调度；它在支持它的 CPU 上选择这个版本。
希望 Apple 的 memcmp 最近更好；不过，我在最近的 Libc 目录中根本看不到它的源代码。希望他们在 运行 时间为 Haswell 和之后的 CPUs 发送 AVX2 版本。
我 linked 版本中的 LLoopOverChunks 循环在 Haswell 上每 ~2.5 个周期仅 运行 1 次迭代（每个输入 16 个字节）； 10 个融合域微指令。但这仍然比天真的 C 循环每个周期 1 个字节快得多，或者比 Python 循环差得多。
Glibc 的 L(loop_4x_vec): 循环是 18 个融合域 uops，因此当数据在 L1d 缓存中处于热状态时，每个时钟周期 运行 仅略小于 32 字节（来自每个输入） .否则会成为 L2 带宽的瓶颈。如果他们没有在循环内使用额外的指令递减一个单独的循环计数器，并在循环外计算一个结束指针，它可能是 17 微指令。
在Python解释器自己的代码中寻找指令/热点
How could I drill down to find the C instructions and CPU instructions that my code calls?
在 Linux 上，您可以 运行 perf record python ... 然后 perf report -Mintel 查看 CPU 花费最多时间的函数以及其中的指令这些功能是最热门的。您会得到类似于我在此处发布的结果：Why is float() faster than int()?。 （深入到任何函数以查看 运行 的实际机器指令，显示为汇编语言，因为 perf 内置了反汇编程序。）
有关对每个事件的调用图进行采样的更细微的视图，请参阅 linux perf: how to interpret and find hotspots。
（当你想要真正优化一个程序时，你想知道哪些函数调用是昂贵的，所以你可以首先尝试避免它们。分析"self" 时间会找到热点，但您不会总是知道哪些不同的调用者导致给定循环 运行 大多数迭代。请参阅 Mike Dunlavey 对该性能问题的回答。）
但是对于这种特定情况，分析解释器 运行 在大字符串上使用切片比较版本应该有望找到 memcmp 循环，我认为它将花费大部分时间。（或者对于一次一个字符的版本，找到 "hot" 的解释器代码。）
然后就可以直接看到循环中有哪些asm指令了。从函数名称，假设您的二进制文件有任何符号，您可能可以找到源代码。或者，如果您有一个使用调试信息构建的 Python 版本，您可以直接从配置文件信息获取源代码。 （不是禁用优化的调试版本，只有完整的符号）。