为什么这个版本的strrev比我的更快？

Question

我无法阅读汇编代码，因此我的假设可能完全错误！

这是我的代码：

void reverse(char* str)
{
    size_t size = strlen(str) / 2;
    char tmp;
    for (int i = 0; i < size; ++i)
    {
        tmp = str[size - i - 1];
        str[size - i - 1] = str[size + i];
        str[size + i] = tmp;
    }
}

这是汇编输出：

000000000000073a <reverse>:
 73a:   55                      push   %rbp
 73b:   48 89 e5                mov    %rsp,%rbp
 73e:   48 83 ec 20             sub    $0x20,%rsp
 742:   48 89 7d e8             mov    %rdi,-0x18(%rbp)
 746:   48 8b 45 e8             mov    -0x18(%rbp),%rax
 74a:   48 89 c7                mov    %rax,%rdi
 74d:   e8 9e fe ff ff          callq  5f0 <strlen@plt>
 752:   48 d1 e8                shr    %rax
 755:   48 89 45 f8             mov    %rax,-0x8(%rbp)
 759:   c7 45 f4 00 00 00 00    movl   $0x0,-0xc(%rbp)
 760:   eb 72                   jmp    7d4 <reverse+0x9a>
 762:   8b 45 f4                mov    -0xc(%rbp),%eax
 765:   48 98                   cltq   
 767:   48 8b 55 f8             mov    -0x8(%rbp),%rdx
 76b:   48 29 c2                sub    %rax,%rdx
 76e:   48 89 d0                mov    %rdx,%rax
 771:   48 8d 50 ff             lea    -0x1(%rax),%rdx
 775:   48 8b 45 e8             mov    -0x18(%rbp),%rax
 779:   48 01 d0                add    %rdx,%rax
 77c:   0f b6 00                movzbl (%rax),%eax
 77f:   88 45 f3                mov    %al,-0xd(%rbp)
 782:   8b 45 f4                mov    -0xc(%rbp),%eax
 785:   48 63 d0                movslq %eax,%rdx
 788:   48 8b 45 f8             mov    -0x8(%rbp),%rax
 78c:   48 01 c2                add    %rax,%rdx
 78f:   48 8b 45 e8             mov    -0x18(%rbp),%rax
 793:   48 01 d0                add    %rdx,%rax
 796:   8b 55 f4                mov    -0xc(%rbp),%edx
 799:   48 63 d2                movslq %edx,%rdx
 79c:   48 8b 4d f8             mov    -0x8(%rbp),%rcx
 7a0:   48 29 d1                sub    %rdx,%rcx
 7a3:   48 89 ca                mov    %rcx,%rdx
 7a6:   48 8d 4a ff             lea    -0x1(%rdx),%rcx
 7aa:   48 8b 55 e8             mov    -0x18(%rbp),%rdx
 7ae:   48 01 ca                add    %rcx,%rdx
 7b1:   0f b6 00                movzbl (%rax),%eax
 7b4:   88 02                   mov    %al,(%rdx)
 7b6:   8b 45 f4                mov    -0xc(%rbp),%eax
 7b9:   48 63 d0                movslq %eax,%rdx
 7bc:   48 8b 45 f8             mov    -0x8(%rbp),%rax
 7c0:   48 01 c2                add    %rax,%rdx
 7c3:   48 8b 45 e8             mov    -0x18(%rbp),%rax
 7c7:   48 01 c2                add    %rax,%rdx
 7ca:   0f b6 45 f3             movzbl -0xd(%rbp),%eax
 7ce:   88 02                   mov    %al,(%rdx)
 7d0:   83 45 f4 01             addl   $0x1,-0xc(%rbp)
 7d4:   8b 45 f4                mov    -0xc(%rbp),%eax
 7d7:   48 98                   cltq   
 7d9:   48 39 45 f8             cmp    %rax,-0x8(%rbp)
 7dd:   77 83                   ja     762 <reverse+0x28>
 7df:   90                      nop
 7e0:   c9                      leaveq 
 7e1:   c3                      retq   

这是另一个版本：

void strrev2(unsigned char *str)
{
    int i;
    int j;
    unsigned char a;
    unsigned len = strlen((const char *)str);
    for (i = 0, j = len - 1; i < j; i++, j--)
    {
        a = str[i];
        str[i] = str[j];
        str[j] = a;
    }
}

还有汇编代码：

00000000000007e2 <strrev2>:
 7e2:   55                      push   %rbp
 7e3:   48 89 e5                mov    %rsp,%rbp
 7e6:   48 83 ec 20             sub    $0x20,%rsp
 7ea:   48 89 7d e8             mov    %rdi,-0x18(%rbp)
 7ee:   48 8b 45 e8             mov    -0x18(%rbp),%rax
 7f2:   48 89 c7                mov    %rax,%rdi
 7f5:   e8 f6 fd ff ff          callq  5f0 <strlen@plt>
 7fa:   89 45 fc                mov    %eax,-0x4(%rbp)
 7fd:   c7 45 f4 00 00 00 00    movl   $0x0,-0xc(%rbp)
 804:   8b 45 fc                mov    -0x4(%rbp),%eax
 807:   83 e8 01                sub    $0x1,%eax
 80a:   89 45 f8                mov    %eax,-0x8(%rbp)
 80d:   eb 4d                   jmp    85c <strrev2+0x7a>
 80f:   8b 45 f4                mov    -0xc(%rbp),%eax
 812:   48 63 d0                movslq %eax,%rdx
 815:   48 8b 45 e8             mov    -0x18(%rbp),%rax
 819:   48 01 d0                add    %rdx,%rax
 81c:   0f b6 00                movzbl (%rax),%eax
 81f:   88 45 f3                mov    %al,-0xd(%rbp)
 822:   8b 45 f8                mov    -0x8(%rbp),%eax
 825:   48 63 d0                movslq %eax,%rdx
 828:   48 8b 45 e8             mov    -0x18(%rbp),%rax
 82c:   48 01 d0                add    %rdx,%rax
 82f:   8b 55 f4                mov    -0xc(%rbp),%edx
 832:   48 63 ca                movslq %edx,%rcx
 835:   48 8b 55 e8             mov    -0x18(%rbp),%rdx
 839:   48 01 ca                add    %rcx,%rdx
 83c:   0f b6 00                movzbl (%rax),%eax
 83f:   88 02                   mov    %al,(%rdx)
 841:   8b 45 f8                mov    -0x8(%rbp),%eax
 844:   48 63 d0                movslq %eax,%rdx
 847:   48 8b 45 e8             mov    -0x18(%rbp),%rax
 84b:   48 01 c2                add    %rax,%rdx
 84e:   0f b6 45 f3             movzbl -0xd(%rbp),%eax
 852:   88 02                   mov    %al,(%rdx)
 854:   83 45 f4 01             addl   $0x1,-0xc(%rbp)
 858:   83 6d f8 01             subl   $0x1,-0x8(%rbp)
 85c:   8b 45 f4                mov    -0xc(%rbp),%eax
 85f:   3b 45 f8                cmp    -0x8(%rbp),%eax
 862:   7c ab                   jl     80f <strrev2+0x2d>
 864:   90                      nop
 865:   c9                      leaveq 
 866:   c3                      retq

为什么第二个版本更快（我认为是因为指令更少），而且为什么objdump为我的代码生成了更多的汇编指令？

我的代码使用的内存更少，但我认为它也会更快，因为我只增加一个变量(i)，并且在使用strlen()时不需要强制类型转换。

- S.Sot

Answer 1

这里的代码：size - i - 1

这将会影响您的性能，因为这个计算实际上在每个循环迭代中都会执行。

您关于使用“更少内存”的假设是错误的。这些变量甚至没有出现在内存中，无论是在哪种算法中，它们都仅保留在寄存器中。因此，首先没有需要消除的内存访问，您的优化所实现的唯一事情就是引入了额外的算术运算，从而减慢了循环速度。

x86架构可以处理的最复杂的寻址形式是variable[variable + constant]。如果比这更复杂，指针算术就必须用多个指令来执行。

此外，编译器展开了代码，正确估计了连续3次迭代的效果。对于带有i和j的代码，这意味着每3次迭代只增加一次，并在之间使用常量偏移量。而对于您的代码，则意味着一遍又一遍地重新进行地址计算。

- Ext3h

---

编译器的选择 - 但在初始加载之后，通常是“是”。 - Michael Dorgan

通常情况下，指针确实是最大的数据类型之一，可以预期无条件地保存在寄存器中，直到寄存器用尽。比指针更大的任何数据类型（例如128位类型）都只适合于特殊的寄存器，而这种寄存器数量相对较少。如果它是一个struct，那么它肯定会被存储到内存中，除非编译器在优化过程中将其拆分开来。 - Ext3h

Answer 2

语句 i++ 和 j++ 可以被翻译为一条汇编指令，将一个寄存器增加 1。

当进行算术索引时，必须将 size 加载到寄存器中，将其与 i 相减并写入另一个寄存器。在 while 循环中有 4 个这样的操作。

- Armin Primadi

Answer 3

首先，如果你想比较什么东西，你需要确保你比较的是行为相同的两段代码。无论如何...

为什么 Linux 版本更快（我假设它更快，因为指令更少）？

你不能只数指令的数量，然后得出指令更少的那个就是最快的结论。

就像 C 代码一样，汇编代码中也可能有循环。

例如，一段汇编代码可能会重复执行相同的三条指令 100 次，而另一段（执行相同操作）则可能展开了循环，变成了（例如）200 条指令，没有任何循环。

因此，即使第二个有更多的指令，它仍然可能显著地更快。

还有许多其他原因，你不能仅仅比较汇编代码来找到最快的代码片段。在硬件层面上存在许多高级功能，例如分支预测、缓存效应、乱序执行、指令间依赖影响流水线停顿等。这些东西如何影响特定代码片段的执行时间，只有“特定处理器/系统的极端专家”才能单凭汇编代码判断。如果你不是“极端专家”，找到最快的代码片段的唯一好方法就是测量执行时间。

- Support Ukraine

Answer 4

这两个函数都是错误的。

例如，第一个函数在处理长度为奇数的字符串时无法正确工作。

下面是一个演示程序。

#include <stdio.h>
#include <string.h>

void reverse(char* str)
{
    size_t size = strlen(str) / 2;
    char tmp;
    for (int i = 0; i < size; ++i)
    {
        tmp = str[size - i - 1];
        str[size - i - 1] = str[size + i];
        str[size + i] = tmp;
    }
}

int main(void) 
{
    char s[] = "123";
    
    reverse( s );
    
    puts( s );
    
    return 0;
}

程序输出为

213

在这个函数中，混合了类型int和size_t，可能导致无限循环。

在第二个函数中，错误地使用了unsigned int类型而不是size_t类型，并且混合了int和unsigned int类型。

void strrev2(unsigned char *str)
{
    int i;
    int j;
    unsigned char a;
    unsigned len = strlen((const char *)str);
    for (i = 0, j = len - 1; i < j; i++, j--)
    {
        a = str[i];
        str[i] = str[j];
        str[j] = a;
    }
}

所以这两个函数都写得非常糟糕。

而且这些函数应该声明为

char * reverse( char * );

所以比较哪个糟糕的函数更快没有太大意义。:)

我认为这样的函数通常是使用汇编语言编写的。

使用C语言，我会按照下面演示程序中所示的方式编写函数。

#include <stdio.h>
#include <string.h>

char * reverse( char * s )
{
    if ( *s )
    {
        for ( char *p = s, *q = s + strlen( s ); p < --q; ++p )
        {
            char c = *p;
            *p = *q;
            *q = c;
        }
    }
    
    return s;
}

int main(void) 
{
    char s[] = "123";
    
    puts( reverse( s ) );
    
    return 0;
}

- Vlad from Moscow

---

@Ext3h，它确实有size_t，ptrdiff_t也是如此。https://port70.net/~nsz/c/c89/c89-draft.html——为什么`strcpy`会返回目标... - Antti Haapala -- Слава Україні

@Ext3h 你错了。字符串标准函数通常约定返回结果字符串的指针。第二个版本很糟糕。混合使用有符号整数和无符号整数可能导致无效的循环。只有低素质的程序员才会称这个版本为理想版本。:) 我没有要补充的。 - Vlad from Moscow

Answer 5

保持简单，避免任何显式索引：

#include <string.h>

...

void my_strrev (char *str)
{
    char *rev = str + strlen(str) - 1;

    while (str < rev)
    {
        char ci = *str, cj = *rev;
        *str++ = cj, *rev-- = ci; /* (exchange) */
    }
}

指针比较在这里是有明确定义的，因为它们都是同一“数组”（或连续内存区域）中元素的地址。这产生了一个紧凑的循环，适合于指令缓存，并且易于理解。此外，我建议对于任何真正的分析，使用-O2。

- Brett Hale

---

当使用 -O2 编译时，您的版本的输出与 VladFromMoscow 的相同。您可能想要检查一下这个链接 https://dev59.com/CGsz5IYBdhLWcg3wDjpo。我不知道那里的答案是否正确，但它们声称指针永远不应该比数组索引更快。 - S.Sot

@S.Sot - 两种方法都是解引用指针。这个版本避免了索引形式。它可能不会更快，但肯定不会更慢。 - Brett Hale