Optimizarea programului de asamblare
În partea anterioară, am discutat câteva probleme generale de optimizare, apoi am vorbit despre compromisurile pe care trebuie să le faceți atunci când optimizați viteza și dimensiunea programului. În această parte și în următoarea, vom arunca o privire mai atentă la câteva dintre exemplele clasice de optimizare „locală”. Dar este important să ne amintim că aceste tehnici speciale ar trebui utilizate numai în anumite circumstanțe - și anume, după ce te-ai asigurat că ai aplicat algoritmii și structurile de date corecte, că ai depanat complet programul și că instrumentele de profilare v-am arătat însăși părțile programului care limitează performanța.
Refuzul universalității
Operațiile de înmulțire și împărțire necesită mult efort de la aproape orice CPU, deoarece acestea trebuie implementate (în hardware sau software) prin deplasări și adunări sau, respectiv, deplasări și scăderi. Vechile procesoare de 4 și 8 biți nu conțineau instrucțiuni ale mașinii pentru înmulțire sau împărțire, așa că aceste operațiuni trebuiau implementate folosind subrutine lungi în care deplasările și adunările sau scăderile erau efectuate în mod explicit. Primele microprocesoare pe 16 biți, cum ar fi 8086 și 68000, au permis înmulțirea și împărțirea în hardware, dar procedurile corespunzătoare au fost incredibil de lente: în procesorul 8086, de exemplu, împărțirea unui număr de 32 de biți la un număr de 16 biți necesare aproximativ 150 de cicluri.
Să ne uităm mai întâi la cea mai simplă procedură de optimizare a înmulțirii. Pentru a multiplica un număr cu o putere de doi, pur și simplu mutați-l la stânga cu numărul necesar de poziții binare (biți). Așa arată, de exemplu, o secvență comună, dar lentă de comenzi atunci când înmulțiți o valoarevariabila myvar la 8:
Pe procesoarele 8086/88, acest program poate fi convertit într-o secvență de schimbare „mai rapidă”:
sau chiar așa: shl myvar, 1 shl myvar, 1 shl myvar, 1
Dacă este necesară o schimbare de una sau două poziții, atunci este de obicei cel mai ușor să efectuați aceste operații pe operanzi din memorie. Dacă este necesară o schimbare în mai multe poziții, atunci viteza crescută de lucru cu operanzi de registru compensează pe deplin instrucțiunea suplimentară pentru încărcarea unui număr într-un registru și extragerea lui de acolo după schimbare.
Dar fă-ți timp - chiar și această simplă optimizare nu este atât de banală pe cât pare! Coada de instrucțiuni din familia de procesoare 80x86, modelul de procesor specific pe care îl folosește computerul și prezența sau absența memoriei cache pot juca cele mai bizare glume. În unele cazuri și pe unele modele de CPU, uneori este posibil să utilizați această comandă în opțiunea „deplasare după numărul de poziții specificat în CX”:
Și în procesorul 80186 și mai târziu există o opțiune „deplasare după numărul de poziții specificat de operandul imediat”, care este și mai convenabilă:
Dacă trebuie să înmulțiți numere mai lungi de 16 cifre cu o putere de două, indicatorul de transport este folosit pentru a organiza operațiuni pe două sau mai multe registre. De exemplu, pentru a înmulți un număr de 32 de biți în DX:AX cu 4, ai scrie:
Combinând în mod creativ schimburile și înmulțirile, puteți înmulți rapid cu aproape orice valoare specifică. Următorul fragment înmulțește valoarea din registrul AX cu 10:
Utilizarea respingerii universalității pentru divizare este ceva mai limitată. Împărțirea cu o putere a doi este, desigur, foarte simplă. Pur și simplu mutați numărul la dreapta, având grijă doar să alegeți comanda de schimbare a părintelui pentru tipul de divizare dorit (cusemnat sau nesemnat). De exemplu, pentru a efectua o împărțire nesemnată cu 4 pe conținutul registrului AX, puteți scrie:
iar pentru procesoarele 80186 și ulterioare, puteți folosi comanda în schimb
O împărțire semnată cu 4 va furniza, de exemplu, secvența
sau pentru procesorul 80186 și mai târziu
Singura diferență dintre instrucțiunea de schimbare logică (fără semn) SHR și instrucțiunea de schimbare aritmetică (semnată) SAR este că SHR copiază bitul cel mai semnificativ (semn) în următorul și apoi înlocuiește bitul de semn cu un zero, în timp ce SAR copiază semnul bit până la următoarea cifră cea mai puțin semnificativă, lăsând valoarea inițială neschimbată.
Împărțirea prin puteri a doi cu schimburi se poate face cu steagul de transport și nu este mai dificilă decât înmulțirea. De exemplu, pentru a efectua o împărțire semnată cu 8 valori, registrele DX:AX pot folosi secvența
Dar, spre deosebire de operația de înmulțire, folosirea schimburilor pentru a împărți rapid la numere arbitrare, cum ar fi 3 sau 10, mai degrabă decât puterile a doi, este surprinzător de supărătoare. Dacă te hotărăști să scrii un program rapid de împărțire cu 10 care folosește o metodă similară metodei înmulțirii cu 10 de mai sus, vei descoperi în curând că programul rezultat este lung, lent și, în plus, ai făcut deja 90% din munca necesară pentru a scrie un program de împărțire generalizată care utilizează deplasări și scăderi. De obicei, este mai bine să regândiți întreaga situație și să reproiectați algoritmul sau structura de date pentru a evita împărțirea la numere „incomode”.
Acum că ați văzut acest truc non-trivial, probabil că aveți o mulțime de idei despre cum să organizați înmulțirea sau împărțirea relativ mareputeri de doi: 256, 512 etc., folosind secvențe de comandă XCHG sau MOV.
Optimizarea salturilor și a apelurilor subrutine
Programele de paste pline de ramuri și salturi în toate direcțiile sunt indezirabile din toate punctele de vedere și mai ales atunci când se lucrează cu procesoare din seria 80x86. Puteți considera această afirmație ca pe o discuție motivațională, al cărei scop este de a încuraja programatorii în limbaj de asamblare și cei implicați în optimizarea compilatorului să structureze corect programele. Există probleme aici, dar înainte de a discuta despre optimizarea ramurilor și apelurilor, să discutăm câteva dintre caracteristicile procesoarelor Intel.
Performanța acestor procesoare este determinată în mare măsură de arhitectura lor, care se bazează pe o schemă de conducte simplă care conține trei componente: o interfață magistrală (BIU - unitate de interfață magistrală), o coadă de preluare și o unitate executivă (EU - unitate de execuție). Când magistrala de memorie este inactivă (de exemplu, când se execută o instrucțiune multiciclu ai cărei operanzi sunt în registre), interfața magistrală preia octeții de instrucțiuni din memorie și îi plasează în coada de preluare, avansând secvențial de la poziția curentă a contorului de instrucțiuni CPU. Când modulul de execuție finalizează execuția următoarei comenzi, în primul rând caută următoarea comandă în coada de prefatch: dacă este într-adevăr acolo, atunci puteți începe imediat să o decriptați, fără a mai accesa memoria.
În același timp, dacă programul va funcționa în principal pe computere cu procesoare 8086 sau 80286, ar trebui să vă aliniați în limitele WORD, iar dacă este proiectat pentru procesoare 80386DX, 80486DX, utilizați alinierea DWORD. (Pentru procesorul 80486, care are un cache internmemoria este mai bună atunci când pozițiile se află pe granițele de 16 octeți, dar cheltuirea în medie a 8 octeți pe etichetă mi se pare un lux.)
Dacă programul dumneavoastră necesită o ramură condiționată, analizați punctul de decizie și aranjați programul astfel încât probabilitatea unei ramuri să fie mai mică decât cea a unei ramuri. În acest fel, veți reduce numărul de șocuri în coada de comenzi. De exemplu, dacă programul dumneavoastră verifică semnul unei variabile care poate fi negativă doar în cazuri rare, în circumstanțe speciale, atunci faceți programul să „sare” peste punctul de ramificare când variabila este pozitivă:
În mod similar, dacă valori diferite ale unei variabile declanșează acțiuni diferite și trebuie să faceți mai multe comparații urmate de salturi condiționate, atunci încercați să mutați comparațiile cu cea mai probabilă valoare mai aproape de începutul lanțului:
convertit la mai rapid
Eliminarea apelurilor recursive este foarte asemănătoare cu tail splicing. Când un program se autoapelează în secvență și acel apel este plasat imediat înaintea instrucțiunii RETURN din program, apelul poate fi convertit într-o ramură, atât crescând viteza, cât și reducând spațiul necesar în stivă. De exemplu, programul
poate fi convertit în
Un astfel de program recursiv poate fi adesea optimizat în continuare prin conversia recursiunii într-o buclă.