Loop con chiamata di funzione più veloce di un ciclo vuoto

Ho collegato alcuni assembly con alcuni c per verificare il costo di una chiamata di funzione, con il seguente assembly e c source (usando fasm e gcc rispettivamente)

assembly:

format ELF public no_call as "_no_call" public normal_call as "_normal_call" section '.text' executable iter equ 100000000 no_call: mov ecx, iter @@: push ecx pop ecx dec ecx cmp ecx, 0 jne @b ret normal_function: ret normal_call: mov ecx, iter @@: push ecx call normal_function pop ecx dec ecx cmp ecx, 0 jne @b ret 

c fonte:

 #include  #include  extern int no_call(); extern int normal_call(); int main() { clock_t ct1, ct2; ct1 = clock(); no_call(); ct2 = clock(); printf("\n\n%d\n", ct2 - ct1); ct1 = clock(); normal_call(); ct2 = clock(); printf("%d\n", ct2 - ct1); return 0; } 

I risultati che ho ottenuto sono stati sorprendenti. Prima di tutto, la velocità dipendeva dall’ordine in cui ero collegato. Se ho collegato come gcc intern.o extern.o , è tipico un output

 162 181 

Ma collegando l’ordine opposto gcc extern.o intern.o , ho ottenuto un’uscita più simile a:

 162 130 

Che siano diversi è stato molto sorprendente, ma non è la domanda che sto chiedendo. ( domanda pertinente qui )

La domanda che mi pongo è: come è ansible che nella seconda esecuzione il ciclo con la chiamata di funzione fosse più veloce del ciclo senza uno, come è stato il costo di chiamare una funzione apparentemente negativa.

Modifica: solo per menzionare alcune delle cose provate nei commenti:

  • Nel bytecode compilato le chiamate di funzione non sono state ottimizzate.
  • La regolazione dell’allineamento delle funzioni e dei loop su tutto, da 4 a 64 byte, non ha accelerato no_call, anche se alcuni allineamenti hanno rallentato normal_call
  • Dare alla CPU / OS la possibilità di riscaldarsi chiamando più volte le funzioni piuttosto che una sola volta non ha avuto alcun effetto apprezzabile delle lunghezze dei tempi misurati, né cambia l’ordine delle chiamate o esegue separatamente
  • Correre per tempi più lunghi non influisce sul rapporto, per esempio correndo 1000 volte più a lungo ho ottenuto 162.168 e 131.578 secondi per i miei tempi di esecuzione

Inoltre, dopo aver modificato il codice assembly per l’allineamento su byte, ho provato a dare all’insieme di funzioni un offset aggiuntivo e sono arrivato a conclusioni più strane. Ecco il codice aggiornato:

 format ELF public no_call as "_no_call" public normal_call as "_normal_call" section '.text' executable iter equ 100000000 offset equ 23 ; this is the number I am changing times offset nop times 16 nop no_call: mov ecx, iter no_call.loop_start: push ecx pop ecx dec ecx cmp ecx, 0 jne no_call.loop_start ret times 55 nop normal_function: ret times 58 nop normal_call: mov ecx, iter normal_call.loop_start: push ecx call normal_function pop ecx dec ecx cmp ecx, 0 jne normal_call.loop_start ret 

Ho dovuto forzare manualmente (e non portabilmente) l’allineamento a 64 byte dal momento che FASM non supporta più di 4 byte di allineamento per la sezione eseguibile, almeno sulla mia macchina. Compensando il programma con offset byte, ecco cosa ho trovato.

 if (20 <= offset mod 128 <= 31) then we get an output of (approximately): 162 131 else 162 (+/- 10) 162 (+/- 10) 

Non sono sicuro di cosa farne, ma è quello che ho scoperto finora

Modifica 2:

Un’altra cosa che ho notato è che se si rimuovono push ecx e pop ecx da entrambe le funzioni, l’output diventa

 30 125 

che indica che quella è la parte più costosa di esso. L’allineamento dello stack è uguale in entrambe le volte, quindi non è questo il motivo della discrepanza. La mia ipotesi migliore è che in qualche modo l’hardware sia ottimizzato per aspettarsi una chiamata dopo una spinta o qualcosa di simile, ma non so nulla di simile

Aggiornamento: la memoria di Skylake / ricarica è a partire da 3c , ma solo se i tempi sono corretti . I carichi consecutivi coinvolti in una catena di dipendenze di inoltro del punto vendita che sono naturalmente distanziati di 3 o più cicli subiranno una latenza più rapida (ad esempio con 4 imul eax,eax nel ciclo, mov [rdi], eax / mov eax, [rdi] prende il ciclo solo fino a 12-15 cicli per iterazione.) ma quando i carichi sono consentiti per eseguire più densamente di quello, si verifica un qualche tipo di conflitto e si ottengono circa 4,5 cicli per iterazione. Il throughput medio non intero è anche un grande indizio che c’è qualcosa di insolito.

Ho visto lo stesso effetto per i vettori 32B (best case 6.0c, back-to-back 6.2 to 6.9c), ma i vettori 128b erano sempre intorno a 5.0c. Vedi i dettagli sul forum di Agner Fog .

Update2: l’ aggiunta di un’assegnazione ridondante accelera il codice una volta compilato senza ottimizzazione e un post del blog del 2013 indica che questo effetto è presente su tutte le CPU della famiglia Sandybridge .

La latenza back-to-back (caso peggiore) di inoltro dei negozi su Skylake è 1 ciclo migliore rispetto a quella precedente, ma la variabilità quando il carico non può essere eseguita immediatamente è simile.


Con l’allineamento corretto (errato), la call extra nel ciclo può effettivamente aiutare Skylake a osservare una latenza di inoltro dei negozi inferiore da push a pop. Sono stato in grado di riprodurre questo con contatori perf (Linux perf stat -r4 ), usando YASM. (Ho sentito che è meno conveniente usare i contatori perf su Windows e comunque non ho una macchina di sviluppo di Windows.) Fortunatamente il sistema operativo non è molto pertinente alla risposta, chiunque dovrebbe essere in grado di riprodurre i risultati del mio contatore perf-counter su Windows con VTune o qualcosa del genere.)

Ho visto i tempi più veloci con offset = 0..10, 37, 63-74, 101 e 127 seguendo un align 128 nel punto specificato nella domanda. Le linee della cache L1I sono 64B e la cache uop si occupa dei limiti 32B. Sembra che l’allineamento relativo a un limite di 64B sia tutto ciò che conta.

Il ciclo di non chiamata è sempre un costante di 5 cicli, ma il ciclo di call può scendere fino a 4c per iterazione dai suoi consueti quasi-esattamente-5 cicli. Ho visto prestazioni più lente del solito a offset = 38 (5.68 + – 8.3% cicli per iterazione). Ci sono piccoli difetti in altri punti, come 5.17c + – 3.3%, secondo perf stat -r4 (che esegue 4 run e facendo una media).

Sembra essere un’interazione tra il front-end che non fa la coda così tanti avanti, causando una minore latenza del back-end per lo store-forwarding da push a pop.

IDK se riutilizzare ripetutamente lo stesso indirizzo per l’inoltro del negozio lo rende più lento (con più uops di indirizzo di negozio già eseguiti prima degli uops di dati negozio corrispondenti) o cosa.


Codice di prova: bash shell loop per creare e profilare l’asm con ogni diverso offset :

 (set -x; for off in {0..127};do asm-link -m32 -d call-tight-loop.asm -DFUNC=normal_call -DOFFSET=$off && ocperf.py stat -etask-clock,context-switches,cpu-migrations,page-faults:u,cycles,instructions,uops_issued.any,uops_executed.thread,idq.mite_uops,dsb2mite_switches.penalty_cycles -r4 ./call-tight-loop; done ) |& tee -a call-tight-loop.call.offset-log 

(set -x) in una subshell è un modo pratico per registrare i comandi insieme al loro output quando si reindirizza a un file di log.

asm-link è uno script che esegue yasm -felf32 -Worphan-labels -gdwarf2 call-tight-loop.asm "[email protected]" && ld -melf_i386 -o call-tight-loop call-tight-loop.o , quindi esegue objdumps -drwC -Mintel sul risultato.

Programma di test NASM / YASM Linux (si riunisce in un binario statico completo che esegue il ciclo e quindi esce, in modo da poter profilare l’intero programma.) Porta diretta della sorgente FASM dell’OP, senza ottimizzazioni per asm.

 CPU p6 ; YASM directive. For NASM, %use smartalign. section .text iter equ 100000000 %ifndef OFFSET %define OFFSET 0 %endif align 128 ;;offset equ 23 ; this is the number I am changing times OFFSET nop times 16 nop no_call: mov ecx, iter .loop: push ecx pop ecx dec ecx cmp ecx, 0 jne .loop ret times 55 nop normal_function: ret times 58 nop normal_call: mov ecx, iter .loop: push ecx call normal_function pop ecx dec ecx cmp ecx, 0 jne .loop ret %ifndef FUNC %define FUNC no_call %endif align 64 global _start _start: call FUNC mov eax,1 ; __NR_exit from /usr/include/asm/unistd_32.h xor ebx,ebx int 0x80 ; sys_exit(0), 32-bit ABI 

Esempio di output da una call veloce:

 + asm-link -m32 -d call-tight-loop.asm -DFUNC=normal_call -DOFFSET=3 ... 080480d8 : 80480d8: c3 ret ... 08048113 : 8048113: b9 00 e1 f5 05 mov ecx,0x5f5e100 08048118 : 8048118: 51 push ecx 8048119: e8 ba ff ff ff call 80480d8  804811e: 59 pop ecx 804811f: 49 dec ecx 8048120: 83 f9 00 cmp ecx,0x0 8048123: 75 f3 jne 8048118  8048125: c3 ret ... Performance counter stats for './call-tight-loop' (4 runs): 100.646932 task-clock (msec) # 0.998 CPUs utilized ( +- 0.97% ) 0 context-switches # 0.002 K/sec ( +-100.00% ) 0 cpu-migrations # 0.000 K/sec 1 page-faults:u # 0.010 K/sec 414,143,323 cycles # 4.115 GHz ( +- 0.56% ) 700,193,469 instructions # 1.69 insn per cycle ( +- 0.00% ) 700,293,232 uops_issued_any # 6957.919 M/sec ( +- 0.00% ) 1,000,299,201 uops_executed_thread # 9938.695 M/sec ( +- 0.00% ) 83,212,779 idq_mite_uops # 826.779 M/sec ( +- 17.02% ) 5,792 dsb2mite_switches_penalty_cycles # 0.058 M/sec ( +- 33.07% ) 0.100805233 seconds time elapsed ( +- 0.96% ) 

Vecchia risposta prima di notare la latenza di inoltro del magazzino variabile

jcc / jcc tuo contatore di loop, quindi tutto tranne le istruzioni call e ret (e cmp / jcc ) fanno parte della catena di dipendenze del ciclo percorso critico che coinvolge il contatore di loop.

Ci si aspetterebbe che pop debba attendere aggiornamenti per il puntatore dello stack per call / ret , ma il motore dello stack gestisce quegli aggiornamenti con latenza zero . (Intel dal Pentium-M, AMD dal K10, secondo il microarch pdf di Agner Fog , quindi presumo che la tua CPU ne abbia una, anche se non hai detto nulla su quale microarchitettura della CPU hai eseguito i tuoi test.)

La call / ret supplementare deve ancora essere eseguita, ma l’esecuzione fuori sequenza può mantenere le istruzioni del percorso critico in esecuzione al massimo throughput. Poiché ciò include la latenza di un negozio-> load forwarding da push / pop + 1 cycle per dec , questo non è un throughput elevato su alcuna CPU, ed è una sorpresa che il front-end possa mai essere un collo di bottiglia con qualsiasi allineamento.

push -> pop latenza è di 5 cicli su Skylake, secondo Agner Fog, quindi su quel uarch il tuo ciclo può eseguire al meglio una iterazione ogni 6 cicli. Questo è un sacco di tempo per l’esecuzione fuori ordine per eseguire le istruzioni di call e ret . Agner elenca un throughput massimo per la call di uno per 3 cicli e ret a uno per 1 ciclo. O su AMD Bulldozer, 2 e 2. Le sue tabelle non elencano nulla sul throughput di una coppia call / ret , quindi IDK se queste possono sovrapporsi o meno. Su AMD Bulldozer, la latenza di archiviazione / ricarica con mov è di 8 cicli. Presumo che sia pressappoco lo stesso con il push / pop.

Sembra che diversi allineamenti per la parte superiore del ciclo (ovvero no_call.loop_start: stiano causando colli di bottiglia front-end. La versione di call ha 3 rami per iterazione: la chiamata, il ret e il ramo di loop. Notare che il target di ramo del ret è l’istruzione subito dopo la call . Ognuno di questi potenzialmente sconvolge il front-end. Dal momento che nella pratica si verifica un rallentamento effettivo, dobbiamo vedere più di un ritardo di ciclo per ramo. Oppure, per la versione no_call, una singola bolla di recupero / decodifica peggiore di circa 6 cicli, che porta a un ciclo effettivo sprecato nell’emissione di uops nella parte fuori dal core. Quello è strano.

È troppo complicato indovinare su quali siano i reali dettagli microarchitetturali per ogni ansible uarch, quindi fateci sapere quale CPU avete testato.

Citerò comunque che il push / pop all’interno di un ciclo su Skylake lo interrompe dall’emissione dal Loop Stream Detector e deve essere nuovamente recuperato dalla cache di uop ogni volta. Il manuale di ottimizzazione di Intel dice che per Sandybridge, un push / pop non corrispondente all’interno di un loop impedisce di utilizzare l’LSD. Ciò implica che può utilizzare l’LSD per loop con push / pop bilanciato. Nei miei test, questo non è il caso su Skylake (usando il lsd.uops prestazioni lsd.uops ), ma non ho visto alcuna menzione se sia stato un cambiamento, o se anche SnB fosse effettivamente così.

Inoltre, i rami incondizionati terminano sempre una riga di uop-cache. È ansible che con normal_function: nello stesso chunk di codice macchina allineato in modo naturale come call e jne , forse il blocco di codice non si adatta alla cache di uop. (Solo 3 righe di uop-cache possono memorizzare nella cache uops decodificati per un singolo pezzo di codice x86 da 32B). Ma questo non spiegherebbe la possibilità di problemi per il ciclo no_call, quindi probabilmente non stai girando su una microarchitettura della famiglia Intel SnB.

(Aggiornamento, sì, il ciclo a volte viene eseguito principalmente dalla decodifica legacy ( idq.mite_uops ), ma in genere non esclusivamente. dsb2mite_switches.penalty_cycles è in genere ~ 8k e probabilmente si verifica solo su interrupt del timer. essere correlato con idq.mite_uops inferiore, ma è ancora 34M + – 63% per il caso offset = 37 in cui le iterazioni 100M hanno richiesto cicli 401M.)

Questo è davvero uno di quei casi “non farlo”: funzioni inline minuscole invece di chiamarle dall’interno di loop molto stretti.


Potresti vedere risultati diversi se push / pop un registro diverso dal tuo contatore di loop. Ciò separerebbe il push / pop dal contatore di loop, quindi ci sarebbero 2 catene di dipendenza separate. Dovrebbe accelerare sia le versioni call che no_call, ma forse non ugualmente. Potrebbe semplicemente rendere più ovvio un collo di bottiglia front-end.

Dovresti vedere un’enorme accelerazione se push edx ma pop eax , quindi le istruzioni push / pop non formano una catena di dipendenze trasportata da loop. Quindi il call / ret sarebbe sicuramente un collo di bottiglia.


Nota a dec ecx : dec ecx già imposta ZF nel modo desiderato, quindi potresti aver appena usato dec ecx / jnz . Inoltre, cmp ecx,0 è meno efficiente di test ecx,ecx (dimensioni del codice più grandi e non è ansible eseguire il fusibile con le macro su altrettante CPU). Ad ogni modo, totalmente irrilevante per la domanda sulla performance relativa dei tuoi due loop. (La mancanza di una direttiva ALIGN tra funzioni significa che la modifica della prima avrebbe cambiato l’allineamento del ramo di loop nel 2 °, ma hai già esplorato diversi allineamenti).

La chiamata a normal_function e il ritorno da esso saranno correttamente previsti ogni volta tranne il primo, quindi non mi aspetto di vedere alcuna differenza nei tempi a causa della presenza della chiamata. Quindi tutte le differenze nel tempo che vedete (sia più veloci che più lente) sono dovute ad altri effetti (come quelli menzionati nei commenti) piuttosto che alla differenza di codice che state effettivamente cercando di misurare.