为什么这个C++字符串长度计算功能比另一个更快？

Question

我们的讲师解释说这个函数计算字符串的长度......

int strlen_1(const char *str) {
    const char *temp = str;
    while(*temp != '\0') {
        temp++;
    }
    return temp - str;
}

...会比这个更快地计算...

int strlen_03(const char *str) {
    int i;
    for (i = 0; *(str+i) != '\0'; i++);
    return i;

我认为他说它与算术计算有关,就像在第一个任何算术微积分完成时一样,但我无法理解,我看到它们都处于同一水平.换句话说,你能解释一下原因吗？

PS.我理解指针,我可以理解发生了什么,就像是通过一个单元逐步存储存储在"RAM单元"中的数组元素.

提前致谢.

Answer 1

暂时忽略优化并只查看纸张算法:

前者重复执行此计算:

addr++

通过差异计算得出的结果

addr1 - addr0

后者重复执行这些计算

addr0 + i
i++

结果由价值回报计算

i

换句话说,在循环中完成了两倍的工作量,以便在计算最终结果时做一半的工作.

进入优化的ASM,第一个在我的clang上生成-O3:

0x100000ee4:  cmpb   $0, 1(%rbx)
0x100000ee8:  leaq   1(%rbx), %rbx
0x100000eec:  sete   %al
0x100000eef:  testb  $1, %al
0x100000ef1:  je     0x100000ee4

第二个产生这个:

0x100000f09:  incl   %ebx
0x100000f0b:  cmpb   $0, (%rax)
0x100000f0e:  leaq   1(%rax), %rax
0x100000f12:  sete   %cl
0x100000f15:  testb  $1, %cl
0x100000f18:  je     0x100000f09

我遗漏了返回值的常数一次性因为它们不是循环复杂性的核心.优化器非常好,注意唯一的主要区别是单一:

0x100000f09:  incl   %ebx

这是你的 i

Answer 2

这是一个微优化,现代编译器最终可能会为两者生成相同的程序集,但对于非优化版本,这就是原因:

int strlen_1(const char *str) 
{
    const char *temp = str; // declare the iterator
    while(*temp != '\0')   // dereference the pointer
                           // test the iterator 
    {
        temp++; // increment the iterator
    }
    return temp - str; // pointer subtraction
}

对于长度为N的字符串,这将为您提供3N + 2个操作.

int strlen_03(const char *str) 
{
    int i; // declare your iterator
    for (i = 0; *(str+i) != '\0'; i++); // initialize the iterator
                                        // add i to str
                                        // dereference that pointer value
                                        // test it against \0
                                        // increment i
    return i;
}

对于相同的字符串,这将为您提供4N + 2个操作.

同样,现代编译器可能会为您解决这个问题,即使在大多数字符串的非优化形式(仅限非常长的字符串)中,这个小循环也不太可能产生太大的差别.