为什么这个版本的 strrev 比我的快？
Why is this version of strrev faster than mine?
我看不懂汇编代码，所以我的假设可能是完全错误的！
这是我的代码：
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;
}
}
这里是 asm 输出：
000000000000073a <reverse>:
73a: 55 push %rbp
73b: 48 89 e5 mov %rsp,%rbp
73e: 48 83 ec 20 sub [=11=]x20,%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 [=11=]x0,-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 [=11=]x1,-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 [=13=]x20,%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 [=13=]x0,-0xc(%rbp)
804: 8b 45 fc mov -0x4(%rbp),%eax
807: 83 e8 01 sub [=13=]x1,%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 [=13=]x1,-0xc(%rbp)
858: 83 6d f8 01 subl [=13=]x1,-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().[=17 时我不转换=]
这里的那个片段：size - i - 1
这会破坏您的性能，因为实际上每次循环迭代都会执行该计算。
您关于使用“较少内存”的假设是错误的。在这两种算法中，这些变量甚至都没有出现在内存中，而是纯粹保存在寄存器中。因此，首先没有要消除的内存访问，您的优化所取得的唯一成果是引入了额外的算法，这现在正在减慢循环速度。
x86 架构可以在一条指令中处理的最复杂的寻址形式是 variable[variable + constant]。比这更复杂，指针运算必须用多条指令来执行。
此外，编译器展开了代码，正确地估计了最多连续 3 次迭代的效果。对于带有 i 和 j 的代码，这意味着每 3 次迭代仅递增一次，并在其间使用常量偏移量。对于您的代码，这意味着一遍又一遍地重做地址计算。
这两个函数都是错误的。
例如，第一个函数无法正确处理长度为奇数的字符串。
这是一个演示程序。
#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;
}
语句 i++ 和 j++ 可以翻译成一条汇编指令，使寄存器递增 1。
当你做算术索引时，它必须加载size到寄存器，用i减去它并写入另一个寄存器。 while循环中有4个这样的操作。
首先：如果你想比较任何东西，你需要确保你比较的是两段行为相同的代码。无论如何...
Why is the linux version faster(I assume it is, because there are less instructions)
你不能只计算指令的数量就得出指令少的指令最快的结论。
就像 C 代码一样，汇编代码中也可以有循环。
例如，一段程序集可能在相同的 3 条指令上循环 100 次，而另一段（做同样的事情）可能已经将循环展开到（例如）200 条指令而没有任何循环。
所以即使第二个有更多的指令，它仍然可能快得多。
还有许多其他原因导致您不能仅通过比较汇编代码来找到最快的代码段。 hw-level 处存在多项高级功能，例如分支预测、缓存效果、out-of-order 执行、指令 inter-dependencies 影响流水线停顿等。这些事情如何影响特定代码段的执行时间只有“特定 [=23 领域的极端专家” =]" 单看汇编代码就可以判断了。如果您不是“极端专家”，找到最快代码段的唯一好方法是测量执行时间。
保持简单，避免任何显式索引：
#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) */
}
}
指针比较在这里是well-defined，因为它们都是同一'array'（或连续内存区域）中元素的地址。这会产生适合指令缓存的紧密 loop，并且易于理解。此外，我建议使用 -O2 进行任何实际分析。
我看不懂汇编代码，所以我的假设可能是完全错误的！
这是我的代码：
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;
}
}
这里是 asm 输出：
000000000000073a <reverse>:
73a: 55 push %rbp
73b: 48 89 e5 mov %rsp,%rbp
73e: 48 83 ec 20 sub [=11=]x20,%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 [=11=]x0,-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 [=11=]x1,-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 [=13=]x20,%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 [=13=]x0,-0xc(%rbp)
804: 8b 45 fc mov -0x4(%rbp),%eax
807: 83 e8 01 sub [=13=]x1,%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 [=13=]x1,-0xc(%rbp)
858: 83 6d f8 01 subl [=13=]x1,-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().[=17 时我不转换=]
这里的那个片段：size - i - 1
这会破坏您的性能，因为实际上每次循环迭代都会执行该计算。
您关于使用“较少内存”的假设是错误的。在这两种算法中，这些变量甚至都没有出现在内存中，而是纯粹保存在寄存器中。因此，首先没有要消除的内存访问，您的优化所取得的唯一成果是引入了额外的算法，这现在正在减慢循环速度。
x86 架构可以在一条指令中处理的最复杂的寻址形式是 variable[variable + constant]。比这更复杂，指针运算必须用多条指令来执行。
此外，编译器展开了代码，正确地估计了最多连续 3 次迭代的效果。对于带有 i 和 j 的代码，这意味着每 3 次迭代仅递增一次，并在其间使用常量偏移量。对于您的代码，这意味着一遍又一遍地重做地址计算。
这两个函数都是错误的。
例如，第一个函数无法正确处理长度为奇数的字符串。
这是一个演示程序。
#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;
}
语句 i++ 和 j++ 可以翻译成一条汇编指令，使寄存器递增 1。
当你做算术索引时，它必须加载size到寄存器，用i减去它并写入另一个寄存器。 while循环中有4个这样的操作。
首先：如果你想比较任何东西，你需要确保你比较的是两段行为相同的代码。无论如何...
Why is the linux version faster(I assume it is, because there are less instructions)
你不能只计算指令的数量就得出指令少的指令最快的结论。
就像 C 代码一样，汇编代码中也可以有循环。
例如，一段程序集可能在相同的 3 条指令上循环 100 次，而另一段（做同样的事情）可能已经将循环展开到（例如）200 条指令而没有任何循环。
所以即使第二个有更多的指令，它仍然可能快得多。
还有许多其他原因导致您不能仅通过比较汇编代码来找到最快的代码段。 hw-level 处存在多项高级功能，例如分支预测、缓存效果、out-of-order 执行、指令 inter-dependencies 影响流水线停顿等。这些事情如何影响特定代码段的执行时间只有“特定 [=23 领域的极端专家” =]" 单看汇编代码就可以判断了。如果您不是“极端专家”，找到最快代码段的唯一好方法是测量执行时间。
保持简单，避免任何显式索引：
#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) */
}
}
指针比较在这里是well-defined，因为它们都是同一'array'（或连续内存区域）中元素的地址。这会产生适合指令缓存的紧密 loop，并且易于理解。此外，我建议使用 -O2 进行任何实际分析。