C++使用终结符的位置作为交换空间来反转以空字符结尾的字符串

Question

我正在研究经典的"反向字符串"问题.

对交换空间使用空终止符的位置是个好主意吗？这个想法是保存一个变量的声明.

具体来说,从Kernighan和Ritchie的算法开始:

void reverse(char s[])
{
    int length = strlen(s);
    int c, i, j;

    for (i = 0, j = length - 1; i < j; i++, j--) 
    {
        c = s[i];
        s[i] = s[j];
        s[j] = c;
    }
}

......我们可以改为做以下事吗？

void reverseUsingNullPosition(char s[]) {
    int length = strlen(s);
    int i, j;

    for (i = 0, j = length - 1; i < j; i++, j--) {
        s[length] = s[i]; // Use last position instead of a new var
        s[i] = s[j];
        s[j] = s[length];
    }
    s[length] = 0; // Replace null character
}

注意不再需要"c"变量.我们只是使用数组中的最后一个位置 - 空终止所在的位置 - 作为我们的交换空间.当我们完成后,我们只需更换0.

这是主程序(Xcode):

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

int main(int argc, const char * argv[]) {
    char cheese[] = { 'c' , 'h' , 'e' , 'd' , 'd' , 'a' , 'r' , 0 };
    printf("Cheese is: %s\n", cheese); //-> Cheese is: cheddar

    reverse(cheese);
    printf("Cheese is: %s\n", cheese); //-> Cheese is: raddehc

    reverseUsingNullPosition(cheese);
    printf("Cheese is: %s\n", cheese); //-> Cheese is: cheddar
}

Answer 1

是的,这可以做到.不,这不是一个好主意,因为它使您的程序更难以优化.

char c在本地作用域中声明时,优化程序可以确定该值未在s[j] = c;赋值之外使用,并且可以将临时值放在寄存器中.除了为您有效地消除变量之外,优化器甚至可以确定您正在执行交换,并发出特定于硬件的指令.所有这些都可以为每个角色节省内存访问.

当您使用s[length]临时时,优化器没有那么多的自由.它被强制发送到内存中.由于缓存,这可能同样快,但在嵌入式平台上,这可能会产生重大影响.

Answer 2

首先,这些微观优化在证明相关之前是完全无关紧要的.我们谈论的是C++,你有std::string,std::reverse你甚至不应该考虑这种事实.

在任何情况下,如果您在Xcode上使用-Os编译两个代码,您将获得reverse:

.cfi_startproc
Lfunc_begin0:
    pushq   %rbp
Ltmp3:
    .cfi_def_cfa_offset 16
Ltmp4:
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
Ltmp5:
    .cfi_def_cfa_register %rbp
    pushq   %r14
    pushq   %rbx
Ltmp6:
    .cfi_offset %rbx, -32
Ltmp7:
    .cfi_offset %r14, -24
    movq    %rdi, %r14
Ltmp8:
    callq   _strlen
Ltmp9:
    leal    -1(%rax), %ecx
    testl   %ecx, %ecx
    jle LBB0_3
Ltmp10:
    movslq  %ecx, %rcx
    addl    $-2, %eax
Ltmp11:
    xorl    %edx, %edx
LBB0_2:
Ltmp12:
    movb    (%r14,%rdx), %sil
    movb    (%r14,%rcx), %bl
    movb    %bl, (%r14,%rdx)
    movb    %sil, (%r14,%rcx)
Ltmp13:
    incq    %rdx
    decq    %rcx
    cmpl    %eax, %edx
    leal    -1(%rax), %eax
    jl  LBB0_2
Ltmp14:
LBB0_3:
    popq    %rbx
    popq    %r14
    popq    %rbp
    ret
Ltmp15:
Lfunc_end0:
    .cfi_endproc

并为reverseUsingNullPosition:

    .cfi_startproc
Lfunc_begin1:
    pushq   %rbp
Ltmp19:
    .cfi_def_cfa_offset 16
Ltmp20:
    .cfi_offset %rbp, -16
    movq    %rsp, %rbp
Ltmp21:
    .cfi_def_cfa_register %rbp
    pushq   %rbx
    pushq   %rax
Ltmp22:
    .cfi_offset %rbx, -24
    movq    %rdi, %rbx
Ltmp23:
    callq   _strlen
Ltmp24:
    leal    -1(%rax), %edx
    testl   %edx, %edx
Ltmp25:
    movslq  %eax, %rdi
    jle LBB1_3
Ltmp26:
    movslq  %edx, %rdx
    addl    $-2, %eax
Ltmp27:
    xorl    %esi, %esi
LBB1_2:
Ltmp28:
    movb    (%rbx,%rsi), %cl
    movb    %cl, (%rbx,%rdi)
    movb    (%rbx,%rdx), %cl
    movb    %cl, (%rbx,%rsi)
    movb    (%rbx,%rdi), %cl
    movb    %cl, (%rbx,%rdx)
Ltmp29:
    incq    %rsi
    decq    %rdx
    cmpl    %eax, %esi
    leal    -1(%rax), %eax
    jl  LBB1_2
Ltmp30:
LBB1_3:                                 ## %._crit_edge
    movb    $0, (%rbx,%rdi)
    addq    $8, %rsp
    popq    %rbx
Ltmp31:
    popq    %rbp
    ret
Ltmp32:
Lfunc_end1:
    .cfi_endproc

如果你检查你的内循环

movb    (%r14,%rdx), %sil
movb    (%r14,%rcx), %bl
movb    %bl, (%r14,%rdx)
movb    %sil, (%r14,%rcx)

VS

movb    (%rbx,%rsi), %cl
movb    %cl, (%rbx,%rdi)
movb    (%rbx,%rdx), %cl
movb    %cl, (%rbx,%rsi)
movb    (%rbx,%rdi), %cl
movb    %cl, (%rbx,%rdx)

所以我不会说你正在节省如此多的开销(因为你正在访问阵列更多次),也许是的,也许不是.这教会了你另一件事:认为某些代码比其他代码更高效是无关紧要的,唯一重要的是一个做得好的基准和代码的配置文件.