Optimiser une boucle qui imprime un compteur

Question

J'ai un très petit programme de boucle qui imprime les nombres de 5000000 à 1. Je veux le faire fonctionner le plus rapidement possible. J'apprends l'assemblage linux x86-64 avec NASM.

global main 
extern printf 
main: 
    push rbx      
    mov rax,5000000d 
print: 
    push rax      
    push rcx      
    mov  rdi, format    
    mov  rsi, rax     
    call printf     
    pop  rcx      
    pop  rax      
    dec  rax      
    jnz  print     
    pop  rbx      
    ret 

format: 
db "%ld", 10, 0 

Answer 1

L'appel à printf domine complètement l'exécution même de cette boucle très inefficace. (Avez-vous remarqué que vous poussez/pop rcx même si vous ne l'utilisez jamais nulle part? Peut-être qu'il ne reste plus qu'à utiliser the slow LOOP instruction).

Pour en savoir plus sur l'écriture efficace de x86 asm, voir Agner Fog's Optimizing Assembly guide. (Et son guide de microarchitecture, aussi, si vous voulez vraiment entrer dans les détails de processeurs spécifiques et comment ils sont différents: ce qui est optimal sur un CPU uarch ne pourrait pas être sur un autre.) IMUL r64 a un meilleur débit et latence sur Intel Les processeurs que sur AMD, mais CMOV et ADC sont 2 uops sur Intel pré-Broadwell, avec 2 cycles de latence contre 1 sur AMD, puisque les m-op ALU à 3 entrées (FLAGS + les deux registres) ne sont pas un problème pour AMD .) Voir aussi d'autres liens dans le wiki des tags x86.

---

optimisation Purement la boucle sans changer la 5M appelle à printf est utile que comme un exemple de la façon d'écrire une boucle correctement, ne pas accélérer réellement ce code. Mais commençons par ce qui suit:

; trivial fixes to loop efficiently while calling the same slow function 
global main 
extern printf 
main: 
    push rbx 
    mov  ebx, 5000000   ; don't waste a REX prefix for constants that fit in 32 bits 
.print: 
    ;; removed the push/pops from inside the loop. 
    ; Use call-preserved regs instead of saving/restoring stuff inside a loop yourself. 
    mov  edi, format   ; static data/code always has a 32-bit address 
    mov  esi, ebx 
    xor  eax, eax    ; The x86-64 SysV ABI requires al = number of FP args passed in FP registers for variadic functions 
    call printf     
    dec  ebx 
    jnz  .print 

    pop  rbx    ; restore rbx, the one call-preserved reg we actually used. 
    xor  eax,eax   ; successful exit status. 
    ret 

section .rodata  ; it's usually best to put constant data in a separate section of the text segment, not right next to code. 
format: 
db "%ld", 10, 0 

---

Pour accélérer ce, nous devrions tirer parti de la redondance dans la conversion des nombres entiers consécutifs à des chaînes. Puisque "5000000\n" n'a que 8 octets de long (y compris le saut de ligne), la représentation de chaîne tient dans un registre de 64 bits.

Nous pouvons stocker cette chaîne dans un tampon et incrémenter un pointeur de la longueur de la chaîne. (Comme il sera plus court pour les plus petits nombres, gardez simplement la longueur de chaîne courante dans un registre, que vous pouvez mettre à jour dans la branche spéciale où il change.)

Nous pouvons décrémenter la représentation de chaîne sur place pour éviter Toujours (re) faire le processus de diviser par 10 pour transformer un entier en une chaîne décimale. Comme carry/emprunter ne se propage pas naturellement dans un registre, et l'instruction AAS n'est pas disponible en mode 64 bits (et ne fonctionne que sur AX, pas même EAX, et est lente), nous devons faire nous-mêmes. Nous diminuons de 1 à chaque fois, donc nous savons ce qui va se passer. Nous pouvons gérer le chiffre le moins significatif en le déroulant 10 fois, il n'y a donc pas de branchement pour le gérer.

Notez également que puisque nous voulons les chiffres dans l'ordre d'impression, le report va quand même dans la mauvaise direction, puisque x86 est little-endian. S'il y avait un bon moyen de tirer parti de notre chaîne dans l'ordre des octets, nous pourrions peut-être utiliser BSWAP ou MOVBE. (Mais notez que MOVBE r64 est 3 uops de domaine fusionné sur Skylake, dont 2 sont ALU uops .. BSWAP r64 est également 2 uops.)

Peut-être devrions-nous faire des compteurs pair/impair en parallèle, en deux moitiés de un registre de vecteurs XMM.Mais cela ne fonctionne plus une fois que la chaîne est plus courte que 8B. Stocker une chaîne de nombres à la fois, nous pouvons facilement se chevaucher. Pourtant, nous pourrions faire la propagation de propagation dans un vecteur reg et stocker les deux moitiés séparément avec MOVQ et MOVHPS. Ou puisque 4/5ème des nombres de 0 à 5M sont à 7 chiffres, il peut être intéressant d'avoir un code pour le cas spécial où l'on peut stocker un vecteur 16B entier de deux nombres.

Une meilleure façon de gérer les chaînes plus courtes: SSSE3 PSHUFB pour mélanger les deux cordes à gauche emballés dans un registre vectoriel, puis un seul MOVUPS pour stocker deux à la fois. Le masque de shuffle n'a besoin d'être mis à jour que lorsque la longueur de la chaîne (nombre de chiffres) change, de sorte que le code de cas spécial de carry-handling rarement exécuté peut le faire également.

La vectorisation de la partie chaude de la boucle devrait être très simple et bon marché, et devrait à peu près doubler les performances.

;;; Optimized version: keep the string data in a register and modify it 
;;; instead of doing the whole int->string conversion every time. 

section .bss 
printbuf: resb 1024*128 + 4096  ; Buffer size ~= half L2 cache size on Intel SnB-family. Or use a giant buffer that we write() once. Or maybe vmsplice to give it away to the kernel, since we only run once. 

global main 
extern printf 
main: 
    push rbx 

    ; use some REX-only regs for values that we're always going to use a REX prefix with anyway for 64-bit operand size. 
    mov  rdx, `5000000\n` ; (NASM string constants as integers work like little-endian, so AL = '5' = 0x35 and the high byte holds '\n' = 10). Note that YASM doesn't support back-ticks for C-style backslash processing. 
    mov  r9, 1<<56   ; decrement by 1 in the 2nd-last byte: LSB of the decimal string 
    ;xor  r9d, r9d 
    ;bts  r9, 56   ; IDK if this code-size optimization outside the loop would help or not. 

    mov  eax, 8   ; string length. 
    mov  edi, printbuf 

.storeloop: 

    ;; rdx = "????x9\n". We compute the start value for the next iteration, i.e. counter -= 10 in rdx. 

    mov  r8, rdx 
    ;; r8 = rdx. We modify it to have each last digit from 9 down to 0 in sequence, and store those strings in the buffer. 
    ;; The string could be any length, always with the first ASCII digit in the low byte; our other constants are adjusted correctly for it 
    ;; narrower than 8B means that our stores overlap, but that's fine. 

    ;; Starting from here to compute the next unrolled iteration's starting value takes the `sub r8, r9` instructions off the critical path, vs. if we started from r8 at the bottom of the loop. This gives out-of-order execution more to play with. 
    ;; It means each loop iteration's sequence of subs and stores are a separate dependency chain (except for the store addresses, but OOO can get ahead on those because we only pointer-increment every 2 stores). 

    mov  [rdi], r8 
    sub  r8, r9    ; r8 = "xxx8\n" 

    mov  [rdi + rax], r8 ; defer p += len by using a 2-reg addressing mode 
    sub  r8, r9    ; r8 = "xxx7\n" 

    lea  edi, [rdi + rax*2] ; if we had len*3 in another reg, we could defer this longer 
      ;; our static buffer is guaranteed to be in the low 31 bits of address space so we can safely save a REX prefix on the LEA here. Normally you shouldn't truncate pointers to 32-bits, but you asked for the fastest possible. This won't hurt, and might help on some CPUs, especially with possible decode bottlenecks. 

    ;; repeat that block 3 more times. 
    ;; using a short inner loop for the 9..0 last digit might be a win on some CPUs (like maybe Core2), depending on their front-end loop-buffer capabilities if the frontend is a bottleneck at all here. 

    ;; anyway, then for the last one: 
    mov  [rdi], r8    ; r8 = "xxx1\n" 
    sub  r8, r9 
    mov  [rdi + rax], r8  ; r8 = "xxx0\n" 

    lea  edi, [rdi + rax*2] 


    ;; compute next iteration's RDX. It's probably a win to interleave some of this into the loop body, but out-of-order execution should do a reasonably good job here. 
    mov  rcx, r9 
    shr  rcx, 8  ; maybe hoist this constant out, too 
    ; rcx = 1 in the second-lowest digit 
    sub  rdx, rcx 

    ; detect carry when '0' (0x30) - 1 = 0x2F by checking the low bit of the high nibble in that byte. 
    shl  rcx, 5 
    test rdx, rcx 
    jz  .carry_second_digit 
    ; .carry_second_digit is some complicated code to propagate carry as far as it needs to go, up to the most-significant digit. 
    ; when it's done, it re-enters the loop at the top, with eax and r9 set appropriately. 
    ; it only runs once per 100 digits, so it doesn't have to be super-fast 

    ; maybe only do buffer-length checks in the carry-handling branch, 
    ; in which case the jz .carry can be jnz .storeloop 
    cmp  edi, esi    ; } while(p < endp) 
    jbe  .storeloop 

    ; write() system call on the buffer. 
    ; Maybe need a loop around this instead of doing all 5M integer-strings in one giant buffer. 

    pop  rbx 
    xor  eax,eax   ; successful exit status. 
    ret 

Ceci n'est pas complètement étoffé, mais devrait donner une idée de ce qui pourrait bien fonctionner.

Si vous effectuez une vectorisation avec SSE2, utilisez probablement un registre d'entiers scalaires pour suivre le moment où vous devez sortir et gérer le report. à savoir un décompteur de 10.

---

Même cette version scalaire est probablement proche de maintenir un magasin par cycle d'horloge, ce qui sature le port du magasin. Ce ne sont que des magasins 8B (et quand la chaîne est plus courte, la partie utile est plus courte que cela), donc nous laissons définitivement la performance sur la table si nous ne goulot pas sur les échecs de cache. Mais avec un processeur 3GHz et une double bande DDR3-1600 (bande passante maximale théorique de ~ 25,6 Go/s), 8 Go par horloge est à peu près suffisant pour saturer la mémoire principale avec un seul cœur.

Nous pourrions paralléliser ceci, et casser la gamme 5M .. 1 en morceaux. Avec des maths intelligents, nous pouvons déterminer quel octet écrire le premier caractère de "2500000\n", ou nous pourrions avoir chaque fil appelez write() lui-même dans le bon ordre. (Ou utilisez le même calcul intelligent pour les appeler pwrite(2) indépendamment avec différents décalages de fichiers, de sorte que le noyau s'occupe de toute la synchronisation pour plusieurs écrivains au même fichier.)

Answer 2

Vous imprimez essentiellement une chaîne fixe. Je pré-générer cette chaîne dans une longue constante.

Le programme devient alors un appel unique à write (ou une boucle courte pour traiter des écritures incomplètes).