为什么python中的字符串比较如此之快？

Question

当我解决以下示例算法问题时,我很好奇理解字符串比较在python中如何工作的内部:

给定两个字符串,返回最长公共前缀的长度

解决方案1: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:binarySearch

另一种方法是将两个字符串平分以创建两个前缀子字符串.如果前缀相等,我们知道公共前缀点至少与中点一样长.否则,公共前缀点至少不大于中点.然后我们可以递归以找到前缀长度.

阿卡二进制搜索.

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个字符.

此图表显示两件事:

1. 正如预期的那样,两种算法在前缀长度增加时线性地变差.
2. 性能以charByChar更快的速度降低.

为什么binarySearch这么好？我认为这是因为

1. 字符串比较binarySearch可能是由幕后的解释器/ CPU优化的.
2. charByChar 实际上为访问的每个字符创建新字符串,这会产生很大的开销.

为了验证这一点,我对比较和切片字符串的性能进行了基准测试,标记为cmp和slice分别在下面.

图B.

此图显示了两个重要的事项:

1. 正如所料,比较和切片随长度线性增加.
2. 相对于算法性能,比较和切片的成本与长度的增长非常缓慢,如图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的代码,发现以下2 个的代码,但我不知道这是哪里的字符串比较发生.

这个问题

• cpython中的字符串比较发生在哪里？
• 有CPU优化吗？是否有特殊的x86指令进行字符串比较？如何查看cpython生成的汇编指令？您可以假设我使用的是最新的python3,Intel Core i5,OS X 10.11.6.
• 为什么比较长字符串比比较每个字符要快得多？

---

奖金问题: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 char的字符串的成本在哪里.

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

binarySearch(s1, s2) = costOfHalfOfEachString * log_2(s1Len)

log_2 是将字符串分成两半直到达到长度为1的字符串的次数

costOfHalfOfEachString = slice(s1Len, s1Len / 2) + slice(s2Len, s1Len / 2) + cmp(s1Len / 2)

因此,大O binarySearch将会增长

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？

Answer 1

TL:DR:切片比较是一些Python开销+高度优化memcmp(除非有UTF-8处理？).理想情况下,使用slice比较来查找小于128个字节或其他内容的第一个不匹配,然后一次循环一个char.

或者,如果它是一个选项并且问题很重要,则制作一个asm-optimized的修改后的副本,该副本memcmp返回第一个差异的位置,而不是等于/不等于; 它将==以与整个字符串中的一个一样快的速度运行.Python有办法在库中调用本机C/asm函数.

这是一个令人沮丧的限制,即CPU可以做到这一点极快,但是Python不(据我所知)给你访问一个优化的比较循环,告诉你错配的位置,而不是仅仅等于/大于/小于.

使用CPython,解释器开销在简单的Python循环中支配实际工作的成本是完全正常的.使用优化的构建块构建算法是值得的,即使这意味着要完成更多的工作.这就是为什么NumPy很好,但是逐个元素循环遍历是非常糟糕的.速度差异可能是这样的20倍至100,为与CPython的编译C(ASM)环路一个字节的时间比较(由数字,而是一个数量级之内可能是正确的).

比较内存块是否相等可能是Python循环与整个列表/切片上操作之间最大的不匹配之一.它的高度优化的解决方案(例如,大多数的libc实现(包括OS X)具有一个手动向量化手工编码ASM一个共同的问题memcmp,使用SIMD比较并行地16个或32个字节,并运行多比字节AT-更快C或汇编中的a-time循环).因此,另一个因素是16到32(如果内存带宽不是瓶颈)乘以Python和C循环之间20到100速度差异的因子.或者取决于您的优化memcmp程度,每个周期可能"仅"6或8个字节.

对于中等大小的缓冲区,L2或L1d缓存中的数据很热,因此memcmp在Haswell或更高版本的CPU上,每个周期需要16或32个字节是合理的.(i3/i5/i7命名是从Nehalem开始的;单独的i5不足以告诉我们你的CPU.)

我不确定你的比较中的一个或两个是否必须处理UTF-8并检查等价类或不同的方法来编码相同的字符.最糟糕的情况是,如果您的Python一次性循环必须检查潜在的多字节字符,但您的切片比较可以使用memcmp.

在Python中编写高效版本:

我们只是完全对抗的语言来获得效率:你的问题是几乎完全一样的C标准库函数memcmp,除非你想要的位置的第一个区别,而不是的-/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开销期间工作,因此我们不需要粒度很大.但是对于非常大的字符串,如果8k不会使内存带宽饱和,那么可能会使其达到64k(你的L2缓存是256kiB; i5确实告诉我们那么多).

怎么memcmp这么快:

我在Intel Core i5上运行它,但我想我会在大多数现代CPU上得到相同的结果.

即使在C中,为什么memcmp比for循环检查快得多？ memcmp比一个字节一次比较循环更快,因为即使C编译器也不擅长(或完全无法)自动矢量化搜索循环.

即使没有硬件SIMD支持,memcmp即使在没有16字节或32字节SIMD的简单CPU上,优化也可以一次检查4或8个字节(字大小/寄存器宽度).

但是大多数现代CPU和所有x86-64都有SIMD指令. SSE2是x86-64的基线,可作为32位模式的扩展.

SSE2或AVX2 memcmp可以使用pcmpeqb/ pmovmskb并行比较16或32个字节.(我不打算详细介绍如何在x86 asm或C intrinsics中编写memcmp.谷歌分别和/或在x86指令集引用中查找那些asm指令.如http:// felixcloutier. com/x86/index.html.另请参阅用于asm和性能链接的x86标签wiki.例如,为什么Skylake比Broadwell-E在单线程内存吞吐量方面要好得多？有一些关于单核内存带宽限制的信息.)

我在他们的开源网站上找到了2005年Apple的x86-64memcmp(AT&T语法汇编语言)的旧版本.它肯定会更好; 对于大缓冲区,它应该对齐一个源指针并且仅movdqu用于另一个源指针,movdqu然后允许pcmpeqb使用内存操作数而不是2x movdqu,即使字符串相对于彼此未对齐. xorl $0xFFFF,%eax/ jnz对于cmp/jcc可以宏保险但xor / jcc不能保险的CPU来说,它也不是最佳的.

展开同时检查整个64字节高速缓存行也会隐藏循环开销.(这与大块相同,然后在找到命中时循环回来). 的glibc的AVX2- movbe版本做这与vpand结合在主大缓冲区循环比较的结果,最后合并为一个vptest也设置标志从结果.(较小的代码大小,但不小于vpand/ vpmovmskb/ cmp/ jcc;但没有下行,可能更低的延迟,以减少分支错误预测对循环退出的惩罚).Glibc在动态链接时进行动态CPU调度; 它在支持它的CPU上选择此版本.

希望Apple memcmp现在更好; 但是,我在最近的Libc目录中根本没有看到它的来源.希望他们在运行时发送到Haswell和后来的CPU的AVX2版本.

LLoopOverChunks版本I链接的循环仅在Haswell上每~2.5个循环运行1次迭代(每个输入16个字节); 10个融合域uops.但对于一个天真的C循环来说,这仍然比每个周期的1个字节快得多,或者比Python循环的情况要差得多.

的Glibc的L(loop_4x_vec):循环是18稠合域微指令,并因此可以在每个时钟周期仅仅略小于32个字节(从每个输入)运行,当数据在L1D缓存热.否则它将成为L2带宽的瓶颈.如果他们没有在循环内部使用额外的指令递减单独的循环计数器,并且在循环外部计算了一个结束指针,那么它可能是17微秒.

在Python解释器自己的代码中查找指令/热点

我怎样才能深入查找代码调用的C指令和CPU指令？

在Linux可以运行perf record python ...,然后perf report -Mintel看看哪些功能CPU在花费了大部分时间,并且在这些功能的指令是最热的.你会得到像我在这里发布的结果:为什么float()比int()更快？.(深入查看任何函数以查看运行的实际机器指令,显示为汇编语言,因为perf内置了反汇编程序.)

有关在每个事件上对调用图进行采样的更细微的视图,请参阅linux perf:如何解释和查找热点.

(如果你正在寻找真正优化程序,你想知道哪些函数调用是昂贵的,所以你可以尽量避免它们摆在首位.剖析的只是"自我"的时候会发现热点,但你不会总是知道哪些不同的调用者导致给定循环运行大部分迭代.请参阅Mike Dunlavey关于该问题的答案.)

但是对于这个特定的情况,分析运行切片比较版本而不是大字符串的解释器应该有希望找到memcmp我认为它将花费大部分时间的循环. (或者对于char-at-a-time版本,找到"热门"的解释器代码.)

然后,您可以直接查看循环中的asm指令.从函数名称开始,假设您的二进制文件有任何符号,您可以找到源代码.或者,如果您使用调试信息构建了Python版本,则可以直接从配置文件信息访问源代码.(不是禁用优化的调试版本,只使用完整符号).