CodeWars - Assembly Language - Elenco di controllo per il valore
Sto eseguendo problemi con il linguaggio assembly su CodeWars, un sito Web con problemi di pratica.
Problema
https://www.codewars.com/kata/545991b4cbae2a5fda000158/train/nasm
Crea un metodo che accetti un elenco e un elemento e restituisca true se l'elemento appartiene all'elenco, altrimenti false.
Soluzione in C
Per darti un'idea di cosa farà il codice assembly.
#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;
}
Soluzione in NASM Assembly (Linux x64)
CodeWars ha fornito le 7 righe in alto.
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
Domande
Sono nuovo di zecca per l'assemblaggio. Qualsiasi feedback su modelli e best practice sarebbe apprezzato. Per esempio
- Esiste uno schema standard da utilizzare durante la scrittura di loop?
- Esiste uno schema standard da utilizzare durante la scrittura di if / elseif / else?
- Esistono scelte di parole e formattazione migliori per le etichette?
Risposte
Prima di tutto, gli oggetti di scena per i commenti abbondanti, in particolare il modo in cui hai incluso una rappresentazione in C.La rappresentazione in C stessa ha un confronto firmato vs non firmato, che può causare strani bug quando e dove non te lo aspetti, ma sto andando per attenersi al codice assembly stesso in questa recensione. Vorrei solo raccomandare di dichiarare il contatore del ciclo icome size_t, poiché questo è il tipo di condizione di arresto.
Ho assemblato la tua funzione C utilizzando gcc versione 10.2.0 con -O3 -march=native, quindi includerò l'output qui in modo da poterlo esaminare passo dopo passo, confrontando le due implementazioni. Questa è davvero una buona idea, tra l'altro, perché lavorare all'indietro su ciò che ha fatto il compilatore C ti aiuta a vedere il vero linguaggio assembly, non solo gli esempi pratici che hai scritto. Compiler Explorer è un ottimo strumento per questo.
Comunque, ecco il mio file di input.
#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;
}
Per montarlo, utilizzo il seguente comando. Nota l' -masm=intelargomento; la sintassi predefinita dell'assembly è AT&Tper gli strumenti GNU.
gcc -S -O3 -march=native -masm=intel -o output.asm input.c
È possibile filtrare i metadati ausiliari e le relative etichette contenenti utilizzando il comando seguente.
cat output.asm | sed -E '/^\s+\./d;/^\.L[A-Z]/d'
Ed ecco la mia uscita.
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
Notare che la prima riga è già diversa. Nella tua versione, hai iniziato impostando il rcxregistro su 0, usando l' movistruzione, mentre l'output del compilatore test rsi, rsi. Perché?
Bene, come hai notato, la convenzione di chiamata per la programmazione di assembly di Intel x86-64 Linux impone che il rsiregistro contenga il secondo argomento della tua funzione, in questo caso la dimensione dell'array. Dalla documentazione Intel x86-64 (pag. 1866), l' testistruzione esegue un test AND logico sui suoi argomenti. Se il risultato è zero, imposta il flag zero ZFuguale a 1. La seguente istruzione ha quindi senso, poiché l'istruzione "jump near if equal" ( je) viene eseguita quando il flag di zero è impostato ( ZF=1).
In altre parole, la subroutine inizia controllando se l'array di input contiene effettivamente degli elementi prima di eseguire effettivamente qualsiasi operazione con esso. Nota che non stavi controllando questo caso limite nel tuo codice originale (né hai verificato che il puntatore all'array non lo fosse NULL), ed è un ottimo esempio di compilatori fantastici. Matt Godbolt (il ragazzo che ha creato Compiler Explorer) ha un discorso fantastico su questo tipo di cose che ti consiglio vivamente di controllare se ti piace questo genere di cose.
Ad ogni modo, se guardi l' .L4etichetta, noterai che è semanticamente equivalente alla tua skip_loop. Tuttavia, si imposta letteralmente il raxregistro (cioè il valore di ritorno della funzione) uguale a zero movinserendo un 0in esso, mentre il compilatore usa l' xoristruzione esclusiva o su eaxse stesso, che ovviamente sarà sempre zero. Non sei semanticamente sbagliato per averlo fatto nel modo in cui hai fatto, ma puoi leggere questo post SO che descrive in dettaglio significativo perché dovresti optare per il xor eax, eaxmetodo. La versione breve è che è più efficiente e la versione più lunga è che è molto più efficiente, ma ci sono altri vantaggi, come il consumo di energia. Quel post entra molto più in dettaglio, però, ed è un'ottima lettura.
Il tuo stesso loop mi sembra a posto. Il compilatore ha utilizzato il raxregistro per il contatore del ciclo, che sia tu che il compilatore avete quindi utilizzato per ottenere il valore dell'array all'indice appropriato. L'unica vera differenza tra le due versioni è che il compilatore ha utilizzato un'istruzione di salto incondizionato jmpper saltare la prima parte del suo ciclo principale, che conteneva l'incremento del contatore del ciclo, mentre il tuo codice aveva l'ultima.
Sinceramente non penso che questa differenza abbia alcun impatto reale, perché entrambe le implementazioni contengono due salti condizionali, che hanno un impatto significativo sulle prestazioni perché attivano recuperi di istruzioni incondizionati e coinvolgono funzionalità del processore più avanzate come la predizione dei rami , che a sua volta introduce problemi tramite un'ottimizzazione chiamata speculativa esecuzione . (Per farla breve, l'ottimizzazione è complicata, non lo saprai davvero fino a quando non la profilerai e probabilmente non dovresti nemmeno preoccuparti dell'ottimizzazione finché non avrai qualcosa funzionante da ottimizzare , ma "probabilmente" stai bene.)
Qualcosa che ho trovato davvero interessante (anche se non particolarmente incisivo o visione del mondo sconvolgente), era che ci crediate o no, la creazione di quella variabile temporanea e quindi il confronto prende esattamente come numero di byte per codificare come il confronto diretto l'output del compilatore nella mia versione.
Ecco uno snippet objdumpdell'output per la tua versione. (Per generarlo sulla tua macchina locale, il comando che ho usato dopo l'assemblaggio con nasm era 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
Ora ecco uno snippet dall'output per la versione del compilatore che contiene l'operazione di confronto.
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
Nota come nella tua versione, l'assegnazione a una variabile temporanea richiede quattro byte. Hai specificato il r8dregistro come registro di destinazione, quindi non è esattamente roba rivoluzionaria, ma la seguente istruzione di confronto richiedeva solo tre byte per codificare:
44 8b 04 8f mov r8d,DWORD PTR [rdi+rcx*4]
44 39 c2 cmp edx,r8d
La versione del compilatore ignorava l'assegnazione della variabile intermedia, ma l'istruzione risultante richiedeva sette byte per la codifica.
39 94 87 00 00 00 00 cmp DWORD PTR [rdi+rax*4+0x0],edx
Per spiegare perché quegli zeri extra alla fine sono importanti, prenderò in prestito ancora una volta da questo fantastico post che dovresti assolutamente leggere .
La dimensione del codice macchina più piccola [...] è sempre un vantaggio: una densità di codice più alta porta a un minor numero di errori nella cache delle istruzioni e a un migliore recupero delle istruzioni e alla potenziale larghezza di banda di decodifica.
Per chiarire davvero questo punto, leggiamo la documentazione con le istruzioni per il salto condizionale (pag. 1109 nel manuale combinato [vol. 1-4]):
Tutti i salti condizionali vengono convertiti in recuperi di codice di una o due righe di cache, indipendentemente dall'indirizzo di salto o dalla capacità di cache.
Ora lascio questo collegamento ai numeri di latenza che ogni programmatore dovrebbe conoscere per la tua edificazione, anche se va notato che questo documento è del 2012. Ecco una bella versione aggiornata in cui puoi guardare i numeri di latenza per anno (incluso il 2020), ma io in realtà l'ho trovato da solo, quindi ammetto di non aver controllato la fonte per verificarne l'accuratezza. Lo includo comunque per completezza.
Per quanto riguarda le etichette stesse, dal momento che loop1, skip_ife skip_loopsono tutte logicamente correlate alla includesubroutine, consiglierei di utilizzare etichette locali per organizzare in modo più intuitivo il codice assembly. Le etichette locali sono particolarmente utili perché il nome della subroutine funge da sorta di spazio dei nomi, consentendo di riutilizzare i nomi delle etichette locali ivi definiti. Puoi vedere che la includeversione sopra assemblata da gcc usa etichette locali.
L'unica raccomandazione che vorrei fare riguardo ai loop è di diffidare di usare il giusto salto condizionale per la tua situazione. Dalla documentazione:
I termini "minore" e "maggiore" vengono utilizzati per i confronti di interi con segno e i termini "sopra" e "sotto" vengono utilizzati per gli interi senza segno.
Neanche questa è pedanteria. Prendiamo ad esempio l' jaeistruzione "salta se sopra o uguale" nel codice. Segue cmpun'istruzione, che sottrae il secondo operando dal primo e modifica il EFLAGSregistro di conseguenza. In particolare, l' subistruzione intermedia esegue la sottrazione sia con segno che senza segno, impostando rispettivamente i flag di overflow e carry. Tuttavia, utilizzando l' jaeistruzione, stai implicitamente solo controllando il flag di riporto, quindi si spera che il contatore del ciclo e le condizioni di arresto siano dello stesso tipo.
Lo standard C definisce come questo dovrebbe essere fatto , il che aiuta a mitigare i bug sia convertendo nel modo più appropriato e sicuro possibile, sia fornendo utili avvisi e persino messaggi di errore (a seconda delle impostazioni di rigore della compilazione). Ovviamente, se stai scrivendo direttamente in linguaggio assembly, questo ovviamente non ti aiuta.
Per riferimento, i EFLAGScodici di condizione sono disponibili nell'Appendice B del volume 1 dei manuali per sviluppatori di software per architetture Intel® 64 e IA-32 e la tabella di riferimento dei salti condizionali inizia a pagina 1106 del volume 2.