Перестановка переменных с и без вспомогательной переменной - что быстрее?

Question

Полагаю, вы все слышали о «проблеме обмена»; ТАК полно вопросов об этом. Версию свопа без использования третьей переменной часто считают более быстрой, поскольку у вас на одну переменную меньше. Я хотел знать, что происходит за кулисами, и написал следующие две программы:

int main () {
    int a = 9;
    int b = 5;
    int swap;

    swap = a;
    a = b;
    b = swap;

    return 0;
}

и версия без третьей переменной:

int main () {
    int a = 9;
    int b = 5;

    a ^= b;
    b ^= a;
    a ^= b;

    return 0;
}

Я сгенерировал ассемблерный код с помощью clang и получил его для первой версии (которая использует третью переменную):

...
Ltmp0:
    movq   %rsp, %rbp
Ltmp1:
    movl   $0, %eax
    movl   $0, -4(%rbp)
    movl   $9, -8(%rbp)
    movl   $5, -12(%rbp)
    movl   -8(%rbp), %ecx
    movl   %ecx, -16(%rbp)
    movl   -12(%rbp), %ecx
    movl   %ecx, -8(%rbp)
    movl   -16(%rbp), %ecx
    movl   %ecx, -12(%rbp)
    popq   %rbp
    ret
Leh_func_end0:
...

и это для второй версии (которая не использует третью переменную):

...
Ltmp0:
    movq    %rsp, %rbp
Ltmp1:
    movl   $0, %eax
    movl   $0, -4(%rbp)
    movl   $9, -8(%rbp)
    movl   $5, -12(%rbp)
    movl   -12(%rbp), %ecx
    movl   -8(%rbp), %edx
    xorl   %ecx, %edx
    movl   %edx, -8(%rbp)
    movl   -8(%rbp), %ecx
    movl   -12(%rbp), %edx
    xorl   %ecx, %edx
    movl   %edx, -12(%rbp)
    movl   -12(%rbp), %ecx
    movl   -8(%rbp), %edx
    xorl   %ecx, %edx
    movl   %edx, -8(%rbp)
    popq   %rbp
    ret
Leh_func_end0:
...

Второй длиннее, но я не очень разбираюсь в ассемблерном коде, поэтому я понятия не имею, означает ли это, что он медленнее, поэтому я хотел бы услышать мнение кого-то более знающего об этом.

Какая из перечисленных версий подкачки переменных быстрее и занимает меньше памяти?

Answer 1

Посмотрите на некоторые оптимизированные сборки. Из

void swap_temp(int *restrict a, int *restrict b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

void swap_xor(int *restrict a, int *restrict b){
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

gcc -O3 -std=c99 -S -o swapping.s swapping.c произведено

    .file   "swapping.c"
.text
.p2align 4,,15
.globl swap_temp
.type   swap_temp, @function
swap_temp:
.LFB0:
.cfi_startproc
movl    (%rdi), %eax
movl    (%rsi), %edx
movl    %edx, (%rdi)
movl    %eax, (%rsi)
ret
.cfi_endproc
.LFE0:
.size   swap_temp, .-swap_temp
.p2align 4,,15
.globl swap_xor
.type   swap_xor, @function
swap_xor:
.LFB1:
.cfi_startproc
movl    (%rsi), %edx
movl    (%rdi), %eax
xorl    %edx, %eax
xorl    %eax, %edx
xorl    %edx, %eax
movl    %edx, (%rsi)
movl    %eax, (%rdi)
ret
.cfi_endproc
.LFE1:
.size   swap_xor, .-swap_xor
.ident  "GCC: (SUSE Linux) 4.5.1 20101208 [gcc-4_5-branch revision 167585]"
.section    .comment.SUSE.OPTs,"MS",@progbits,1
.string "Ospwg"
.section    .note.GNU-stack,"",@progbits

Для меня swap_temp выглядит настолько эффективно, насколько это возможно.

Answer 2

Проблема со своп-трюком XOR заключается в том, что он строго последовательный. Это может показаться обманчиво быстрым, но на самом деле это не так. Есть инструкция под названием XCHG, которая меняет два регистра, но это также может быть медленнее, чем просто использование 3 MOVs, из-за своей атомарной природы. Общая техника с temp - отличный выбор;)

Answer 3

Чтобы получить представление о стоимости, представьте, что каждая команда имеет свою стоимость, а также косвенная адресация имеет свою стоимость.

movl   -12(%rbp), %ecx

Для этой строки потребуется что-то вроде единицы времени для доступа к значению в регистре ecx, одна единица времени для доступа к rbp, другая для применения смещения (-12) и больше единиц времени (скажем,произвольно 3) для перемещения значения с адреса, хранящегося в ecx, на адрес, указанный в -12 (% rbp).

Если вы посчитаете все операции в каждой строке и во всей строке, второй метод наверняка будет стоить дороже, чем первый.