Variable swap avec et sans variable auxiliaire – qui est plus rapide?

Je suppose que vous avez tous entendu parler du «problème d’échange»; SO est plein de questions à ce sujet. La version de l’échange sans utilisation d’une troisième variable est souvent considérée comme étant plus rapide, car vous avez une variable de moins. Je voulais savoir ce qui se passait derrière les rideaux et ai écrit les deux programmes suivants:

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

et la version sans troisième variable:

 int main () { int a = 9; int b = 5; a ^= b; b ^= a; a ^= b; return 0; } 

J’ai généré le code assembleur à l’aide de clang et je l’ai obtenu pour la première version (qui utilise une troisième variable):

 ... 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: ... 

et ceci pour la deuxième version (qui n’utilise pas une troisième variable):

 ... 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: ... 

La seconde est plus longue mais je ne connais pas grand chose au code assembleur, je ne sais donc pas si cela signifie que c’est plus lent. J’aimerais donc connaître l’opinion de quelqu’un de plus au courant.

Laquelle des versions ci-dessus d’un échange de variable est plus rapide et prend moins de mémoire?

Regardez un assemblage optimisé. De

 void swap_temp(int *ressortingct a, int *ressortingct b){ int temp = *a; *a = *b; *b = temp; } void swap_xor(int *ressortingct a, int *ressortingct b){ *a ^= *b; *b ^= *a; *a ^= *b; } 

gcc -O3 -std=c99 -S -o swapping.s swapping.c produit

  .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 .ssortingng "Ospwg" .section .note.GNU-stack,"",@progbits 

Pour moi, swap_temp semble aussi efficace que possible.

Le problème avec l’astuce d’échange XOR est qu’il est ssortingctement séquentiel. Cela peut sembler incroyablement rapide, mais en réalité, ce n’est pas le cas. Il existe une instruction appelée XCHG qui échange deux registres, mais elle peut aussi être plus lente que d’utiliser simplement 3 MOVs , en raison de sa nature atomique. La technique courante avec temp est un excellent choix;)

Pour avoir une idée du coût, imaginez que chaque commande ait un coût à exécuter et que l’adressage indirect ait son propre coût.

 movl -12(%rbp), %ecx 

Cette ligne nécessite quelque chose comme une unité de temps pour accéder à la valeur dans le registre ecx, une unité de temps pour accéder à rbp, une autre pour appliquer le décalage (-12) et plusieurs unités de temps (disons arbitrairement 3) adresse stockée dans ecx à l’adresse indiquée à partir de -12 (% rbp).

Si vous comptez toutes les opérations de chaque ligne et de toutes les lignes, la seconde méthode est certainement plus coûteuse que la première.