为什么 strlen() 比手动循环检查空终止字符快大约 20 倍？

Question

最初的问题反响不佳，并得到了很多反对票。所以我想我应该修改这个问题，使其更容易阅读，并希望对看到它的人有更多帮助。最初的问题是为什么 strlen() 比手动循环字符串并查找 ' ' 字符快 20 倍。我认为这个问题是有根据的，因为我在任何地方读到 strlen() 查找字符串长度的技术本质上都是循环的，直到找到空终止字符“”。这是对 C 字符串的常见批评，原因不止一个。正如许多人指出的那样，C 库中的函数是由聪明的程序员创建的，以最大限度地提高性能。

感谢 ilen2，他为我提供了一种非常聪明的方法，使用按位运算符一次检查 8 个字节，我设法得到了一些东西，在大于大约 8 到 15 个字符的字符串上，运行速度比 strlen() 更快，并且当字符串相当大时，比 strlen() 快很多倍。例如，奇怪的是， strlen() 似乎与要完成的字符串的长度呈线性时间相关。另一方面，无论字符串长度如何，自定义字符串都花费几乎相同的时间（我测试了最多几百个）。不管怎样，我的结果相当令人惊讶，我在关闭优化的情况下完成了这些结果，我不知道它们的有效性。非常感谢 ilen2 提供的链接和 John Zwinck。有趣的是，John Zwinck 建议使用 SIMD 作为 strlen() 更快的可能性，但我对此一无所知。

Answer 1

strlen()

是一个非常受欢迎的功能，你可以打赌，一些非常聪明的人花了几天甚至几个月的时间来优化它。一旦你的算法正确，接下来的事情就是，你能一次检查多个字节吗？答案当然是可以，使用 SIMD (SSE) 或其他技巧。如果您的处理器一次可以运行 128 位，则每个时钟运行 16 个字符，而不是 1 个。

Answer 2

以下是

strlen()

在 MSVC 中的工作原理：

; Function compile flags: /Ogtpy
; File D:\P\MT\prftst.cpp
;   COMDAT ?testR@@YAXXZ
_TEXT   SEGMENT
len$ = 8
?testR@@YAXXZ PROC                  ; testR, COMDAT

; 44   :    volatile ui64 len = strlen(str);

  00000 48 8d 0d 00 00
    00 00        lea     rcx, OFFSET FLAT:?str@@3PADA ; str
  00007 48 c7 c0 ff ff
    ff ff        mov     rax, -1
  0000e 66 90        npad    2  ; >>> xchg  ax,ax 
$LL3@testR:
  00010 48 ff c0     inc     rax
  00013 80 3c 01 00  cmp     BYTE PTR [rcx+rax], 0
  00017 75 f7        jne     SHORT $LL3@testR
  00019 48 89 44 24 08   mov     QWORD PTR len$[rsp], rax

; 45   : }

  0001e c3       ret     0
?testR@@YAXXZ ENDP                  ; testR
_TEXT   ENDS

无需非常流利的组装即可获得它。非常简单的算法，只是循环遍历每个字符并测试它是否不为0。现在，我认为编译器实际上每次看到它时都会内联这个函数。它不位于任何库中，它的代码是由编译器本身生成的。

另请注意，如果您将指针提供给在编译时声明的

const char *

，编译器将作弊并执行以下操作：

; Function compile flags: /Ogtpy
; File D:\P\MT\prftst.cpp
;   COMDAT ?testR@@YAXXZ
_TEXT   SEGMENT
len$ = 8
?testR@@YAXXZ PROC                  ; testR, COMDAT

; 60   :    volatile ui64 len = strlen(str200);

  00000 48 c7 44 24 08
    c8 00 00 00  mov     QWORD PTR len$[rsp], 200 ; 000000c8H

; 61   : }

  00009 c3       ret     0
?testR@@YAXXZ ENDP                  ; testR
_TEXT   ENDS

是的。它只是粘贴了编译时已知的 const cstring 文字大小！

我认为这实际上可能是你的测试如此奇怪的原因。始终在

strlen()

数组上测试

char[]

，而不用文字对其进行初始化。

memset()

main()

中的数组，这样编译器永远不会知道字符串的大小，并且将被迫在运行时计算它。

此外，始终使用

volatile

变量来放入

strlen()

结果，这将强制编译器实际计算大小。

在循环函数中使用

#pragma optimize( "", off )

和

#pragma optimize( "", on )

，并使用您正在测试的实际代码调用包装函数。此包装函数必须具有

__declspec(noinline)

说明符。