CodeWars - Langage d'assemblage - Liste de contrôle pour la valeur
Je fais des problèmes de langage d'assemblage sur CodeWars, un site Web avec des problèmes de pratique.
Problème
https://www.codewars.com/kata/545991b4cbae2a5fda000158/train/nasm
Créez une méthode qui accepte une liste et un élément, et retourne true si l'élément appartient à la liste, sinon false.
Solution en C
Pour vous donner une idée de ce que fera le code d'assemblage.
#include <stdbool.h>
#include <stddef.h>
bool include(const int* arr, size_t size, int item)
{
int i = 0;
loop:
if ( i < size ) {
if ( arr[i] == item ) {
return true;
}
i++;
goto loop;
}
return false;
}
Solution dans l'assemblage NASM (Linux x64)
CodeWars a fourni les 7 lignes en haut.
SECTION .text
global include
include:
; bool include(const int* arr, size_t size, int item)
; sizeof(int) = 4 bytes (32bit)
; sizeof(size_t) = 8 bytes (64bit)
;rdi = &arr pointer, 8 bytes
; arr[i] signed int, 4 bytes (dd)
;rsi = size size_t, unsigned int, 8 bytes
;edx = item signed int, 4 bytes
; Avoid using registers that we need to preserve (RBX, RBP, R12-R15). Else we'd have to push and pop them onto the stack.
mov rcx, 0 ; unsigned int i = 0;
loop1:
cmp rcx, rsi ; if ( i < size ) {
jae skip_loop
mov r8d, [rdi + 4 * rcx] ; make a temp variable so we can see this in step debugging
cmp edx, r8d ; if ( arr[i] == item ) {
jne skip_if
mov rax, 1 ; return true;
ret
skip_if:
inc rcx ; i++;
jmp loop1
skip_loop:
mov rax, 0 ; return false;
ret
Des questions
Je suis tout nouveau dans l'assemblage. Tout commentaire sur les modèles et les meilleures pratiques serait apprécié. Par exemple
- Existe-t-il un modèle standard à utiliser lors de l'écriture de boucles?
- Existe-t-il un modèle standard à utiliser lors de l'écriture de if / elseif / else?
- Existe-t-il de meilleurs choix de mots et une meilleure mise en forme pour les étiquettes?
Réponses
Tout d'abord, les accessoires pour les commentaires copieux, en particulier la façon dont vous avez inclus une représentation dans C.La représentation C elle-même a une comparaison signée vs non signée, ce qui peut causer des bogues étranges quand et où vous ne les attendez pas, mais je vais de s'en tenir au code d'assemblage lui-même dans cette revue. Je recommanderais simplement de déclarer le compteur de boucle icomme size_t, car c'est le type de la condition d'arrêt.
J'ai assemblé votre fonction C en utilisant gcc version 10.2.0 avec -O3 -march=native, donc je vais inclure la sortie ici afin que je puisse la parcourir étape par étape, en comparant les deux implémentations. C'est une très bonne idée, au fait, car travailler à rebours sur ce que le compilateur C a fait vous aide à voir le vrai langage d'assemblage, pas seulement à pratiquer les exemples que vous avez écrits. Compiler Explorer est un excellent outil pour cela.
Quoi qu'il en soit, voici mon fichier d'entrée.
#include <stdbool.h>
#include <stddef.h>
bool include(const int* arr, size_t size, int item) {
for (size_t i = 0; i < size; ++i) {
if (arr[i] == item) {
return true;
}
}
return false;
}
Pour l'assembler, j'utilise la commande suivante. Notez l' -masm=intelargument; la syntaxe d'assemblage par défaut est AT&Tpour les outils GNU.
gcc -S -O3 -march=native -masm=intel -o output.asm input.c
Vous pouvez filtrer les métadonnées auxiliaires et leurs étiquettes contenant à l'aide de la commande suivante.
cat output.asm | sed -E '/^\s+\./d;/^\.L[A-Z]/d'
Et voici ma sortie.
include:
test rsi, rsi
je .L4
xor eax, eax
jmp .L3
.L8:
inc rax
cmp rsi, rax
je .L4
.L3:
cmp DWORD PTR [rdi+rax*4], edx
jne .L8
mov eax, 1
ret
.L4:
xor eax, eax
ret
Notez que la première ligne est déjà différente. Dans votre version, vous avez commencé par définir le rcxregistre sur 0, en utilisant l' movinstruction, alors que le compilateur sortait test rsi, rsi. Pourquoi?
Eh bien, comme vous l'avez noté, la convention d'appel de programmation d'assemblage Linux Intel x86-64 dicte que le rsiregistre contient le deuxième argument de votre fonction, dans ce cas, la taille du tableau. À partir de la documentation Intel x86-64 (p. 1866), l' testinstruction effectue un test ET logique sur ses arguments. Si le résultat est zéro, il définit l'indicateur zéro ZFégal à 1. L'instruction suivante a donc du sens, puisque l'instruction "jump near if equal" ( je) est exécutée lorsque le drapeau zéro est positionné ( ZF=1).
En d'autres termes, le sous-programme commence par vérifier si le tableau d'entrée contient réellement des éléments avant d'en faire quoi que ce soit. Notez que vous ne recherchiez pas ce cas de bord dans votre code d'origine (et que vous n'avez pas vérifié que le pointeur de tableau ne l'était pas NULL), et c'est un excellent exemple de compilateurs géniaux. Matt Godbolt (le gars qui a créé Compiler Explorer) a une excellente discussion sur ce genre de choses que je vous recommande vivement de vérifier si vous aimez ce genre de chose.
Quoi qu'il en soit, si vous regardez l' .L4étiquette, vous remarquerez qu'elle est sémantiquement équivalente à votre skip_loop. Cependant, vous définissez littéralement le raxregistre (c'est-à-dire la valeur de retour de la fonction) égal à zéro en y movinsérant un 0, alors que le compilateur utilise l' xorinstruction exclusive ou sur eaxavec lui-même, qui sera évidemment toujours zéro. Vous n'avez pas tort sémantiquement de le faire comme vous l'avez fait, mais vous pouvez lire cet article de SO qui décrit en détail pourquoi vous devriez opter pour la xor eax, eaxméthode. La version courte, c'est qu'elle est plus efficace, et la version plus longue, c'est qu'elle est beaucoup plus efficace, mais il y a d'autres avantages, comme la consommation d'énergie. Cet article est cependant beaucoup plus détaillé et c'est une excellente lecture.
Votre boucle elle-même me semble correcte. Le compilateur a utilisé le raxregistre pour le compteur de boucles, que vous et le compilateur avez ensuite utilisé pour obtenir la valeur du tableau à l'index approprié. La seule vraie différence entre les deux versions est que le compilateur a utilisé une jmpinstruction de saut inconditionnel pour sauter la première partie de sa boucle principale, qui contenait l'incrément du compteur de boucle, alors que votre code avait cette dernière.
Je ne pense vraiment pas que cette différence ait un impact réel, car les deux implémentations contiennent deux sauts conditionnels, qui ont un impact significatif sur les performances car ils déclenchent des récupérations d'instructions inconditionnelles et impliquent des fonctionnalités de processeur plus avancées comme la prédiction de branche , qui elle-même introduit des problèmes via une optimisation appelée spéculative. exécution . (Pour faire court, l'optimisation est compliquée, vous ne le saurez pas vraiment tant que vous ne l'aurez pas profilée, et vous ne devriez probablement pas vous soucier de l'optimisation tant que vous n'avez pas un élément fonctionnel à optimiser , mais vous allez "probablement" bien.)
Quelque chose que j'ai trouvé vraiment intéressant (bien que pas particulièrement percutant ou bouleversant la vision du monde), c'est que croyez-le ou non, créer cette variable temporaire puis comparer prend exactement autant d'octets à encoder que la comparaison directe de la sortie du compilateur dans ma version.
Voici un extrait de la objdumpsortie de votre version. (Pour générer ceci sur votre machine locale, la commande que j'ai utilisée après l'assemblage avec nasm était objdump -Mx86-64,intel -D -S -s input.o.)
0000000000000005 <loop1>:
loop1:
cmp rcx, rsi ; if ( i < size ) {
5: 48 39 f1 cmp rcx,rsi
jae skip_loop
8: 73 14 jae 1e <skip_loop>
mov r8d, [rdi + 4 * rcx] ; make a temp variable so we can see this in step debugging
a: 44 8b 04 8f mov r8d,DWORD PTR [rdi+rcx*4]
cmp edx, r8d ; if ( arr[i] == item ) {
e: 44 39 c2 cmp edx,r8d
jne skip_if
11: 75 06 jne 19 <skip_if>
mov rax, 1 ; return true;
13: b8 01 00 00 00 mov eax,0x1
ret
18: c3 ret
Voici maintenant un extrait de la sortie de la version du compilateur qui contient l'opération de comparaison.
0000000000000011 <include.L3>:
.L3:
cmp [dword rdi+rax*4], edx
11: 39 94 87 00 00 00 00 cmp DWORD PTR [rdi+rax*4+0x0],edx
jne .L8
18: 75 ef jne 9 <include.L8>
mov eax, 1
1a: b8 01 00 00 00 mov eax,0x1
ret
1f: c3 ret
Notez comment dans votre version, l'affectation à une variable temporaire prend quatre octets. Vous avez spécifié le r8dregistre comme registre de destination, donc ce n'est pas exactement un truc révolutionnaire, mais l'instruction de comparaison suivante ne nécessitait que trois octets pour encoder:
44 8b 04 8f mov r8d,DWORD PTR [rdi+rcx*4]
44 39 c2 cmp edx,r8d
La version du compilateur a ignoré l'affectation de variable intermédiaire, mais l'instruction résultante nécessitait sept octets pour être codée.
39 94 87 00 00 00 00 cmp DWORD PTR [rdi+rax*4+0x0],edx
Pour expliquer pourquoi ces zéros supplémentaires à la fin importent, je vais emprunter une fois de plus à ce super article que vous devriez certainement lire .
Une plus petite taille de code machine est [...] toujours un avantage: une densité de code plus élevée conduit à moins d'erreurs de cache d'instructions et à une meilleure extraction d'instructions et potentiellement à décoder la bande passante.
Pour vraiment ramener ce point à la maison, lisons la documentation des instructions de saut conditionnel (p. 1109 dans le manuel combiné [vols 1-4]):
Tous les sauts conditionnels sont convertis en récupérations de code d'une ou deux lignes de cache, indépendamment de l'adresse de saut ou de la capacité du cache.
Je laisse maintenant ce lien vers les nombres de latence que chaque programmeur devrait connaître pour votre édification, bien qu'il convient de noter que ce document date de 2012. Voici une version mise à jour cool où vous pouvez consulter les nombres de latence par année (y compris 2020), mais je en fait, je viens de trouver cela moi-même, alors j'admets que je n'ai pas vérifié la source pour l'exactitude. Je l'inclus néanmoins par souci d'exhaustivité.
En ce qui concerne les étiquettes elles-mêmes, puisque loop1, skip_ifet skip_loopsont toutes logiquement liées au includesous - programme, je recommanderais d'utiliser des étiquettes locales pour organiser plus intuitivement votre code d'assemblage. Les étiquettes locales sont particulièrement utiles car le nom du sous-programme sert comme une sorte d'espace de noms, vous permettant de réutiliser les noms d'étiquettes locales qui y sont définis. Vous pouvez voir que la includeversion ci-dessus assemblée par gcc utilise des étiquettes locales.
La seule recommandation que je ferais concernant les boucles est de se méfier de l'utilisation du saut conditionnel adapté à votre situation. De la documentation:
Les termes «moins» et «plus grand» sont utilisés pour les comparaisons d'entiers signés et les termes «au-dessus» et «en dessous» sont utilisés pour les entiers non signés.
Ce n'est pas non plus du pédantisme. Prenons par exemple l' jaeinstruction "sauter si au-dessus ou égal" dans votre code. Il suit une cmpinstruction, qui soustrait le deuxième opérande du premier et modifie le EFLAGSregistre en conséquence. Plus précisément, l' subinstruction intermédiaire effectue à la fois des soustractions signées et non signées, définissant respectivement les indicateurs de dépassement de capacité et de report. Cependant, en utilisant l' jaeinstruction, vous ne vérifiez implicitement que l'indicateur de retenue, donc j'espère que votre compteur de boucle et vos conditions d'arrêt sont du même type.
Le standard C définit comment cela doit être fait , ce qui aide à atténuer les bogues en convertissant aussi correctement et en toute sécurité que possible, et en fournissant des avertissements utiles et même des messages d'erreur (en fonction des paramètres de rigueur de compilation). Bien sûr, si vous allez écrire directement le langage assembleur, cela ne vous aide évidemment pas.
Pour référence, les EFLAGScodes de condition se trouvent dans l'annexe B du volume 1 des manuels du développeur de logiciels des architectures Intel® 64 et IA-32 , et le tableau de référence des sauts conditionnels commence à la page 1106 du volume 2.