Regula # 1: “Distrează-te!”

István Kiss
Software Engineer @ FlowTraders

De fapt, aceasta ar trebui să fie regula # 0!

Regula #1: Nu o face!

Potrivit lui Knuth, Computer Programming as an Art (1974) "optimizarea prematură este cauza tuturor relelor (sau a majorității relelor) în programare." Oare s-a schimbat realitatea din spatele acestor vorbe în ultimii 40 de ani? Să ne uităm la C++ care a rămas un sinonim pentru performanță și în ziua de azi. Să începem cu o funcție simplă: împărțirea la patru.

În imaginea de mai jos, în partea stângă, puteți observa operaţia de împărţire din cod, iar mai jos, rezultatul codului, după ce compilatorul a optimizat codul:

unsigned int div_by_4(unsigned int num)
{
  return num / 4;
}

div_by_4(unsigned int):
mov     eax, edi
shr     eax, 2
ret

Eu utilizez Compiler Explorer pentru a verifica rezultatul compilării sub formă de limbaj de asamblare. Când caut ponturi de bune practici pentru optimizarea vitezei în C++, pe Internet, primesc următorul sfat: "utilizați rotaţie la nivel de biţi pentru înmulţirile și împărţirile cu doi."

unsigned int div_by_4(unsigned int num)
{
  return num >> 2;
}

mov     eax, edi
shr     eax, 2
ret

În imaginea de mai jos, în partea stângă, puteți observa codul ce folosește rotaţie pe biţi, iar în partea dreaptă, rezultatul codului, după ce compilatorul a optimizat codul.

Comparând rezultatele ambelor versiuni, veţi observa că e vorba de același lucru: rotire spre dreapta a conţinutului registrului EAX cu două poziţii. Deci, ce am reușit să facem folosind rotirea pe biţi în loc de împărţirea standard? Codul e mai greu de citit. Chiar dacă ar lua o jumătate de secundă, trebuie să ne întrebăm: ce înseamnă, de fapt, rotire spre dreapta cu două poziţii?

Un programator C++ versat ar putea spune că poate citi a doua variantă de cod la fel de repede ca pe prima. Ce spuneți despre următorul exemplu? Să îndepărtăm cuvântul-cheie unsigned. Va schimba rezultatul sau nu?

int div_by_4( int num )
{
    return num / 4;
}

div_by_4(int):
lea     eax, [rdi+3]
test    edi, edi
cmovns  eax, edi
sar     eax, 2
ret

Am vești proaste pentru tabăra care a votat că nu este vorba de nicio schimbare. O singură instrucțiune shift right și avem două instrucțiuni shift în jurul celei mai importante secțiuni, urmat de familiarul shift right cu 2. Deci, ce s-a întâmplat? Funcția poate acum divide și numere negative, iar aceasta schimbă algoritmul. Deci, optimizând codul, noi am putea introduce un bug greu de detectat.

Să verificăm un alt exemplu. Haideți să calculăm cu 10!

int main(  )
{
    int result = 1;
    for (int i = 1; i <= 10; ++i)
    {
        result *= i;
    }
    return result;
}

main:
mov     eax, 3628800
ret

Există o singură instrucțiune move: compilatorul a calculat rezultatul pentru noi și a înlocuit ciclul FOR cu un număr constant. Aceasta chiar este optimizare!

Ce ziceți de inlining? În vechile zile ale limbajului C, se puteau utiliza funcții macro, dar nu aș sfătui să se folosească, deoarece nu știţi cum se comportă și cum se va comporta codul rezultant. C++ conține cuvântul cheie inline, deci instruim compilatorul pentru funcția inline. Am creat o funcție șablon simplă care să returneze valoarea maximă din cei doi parametri input. Dacă verificați rezultatul în limbaj de asamblare, atât pentru versiunile inlined, cât și pentru non-inlined, veți vedea că nu există nicio diferență. Limbajul C a observat că funcția ar trebui să fie inline.

Codul normal:

#include 

template 
T const& MAX(T const& a, T const& b)
{
    return (a < b ) ? b : a ;
}

int main(  )
{
    int a = 0;
    std::cin >> a;
    return MAX(a, 42);
}

main:                                   # @main
push    rax
mov     dword ptr [rsp + 4], 0
lea     rsi, [rsp + 4]
mov     edi, std::cin
call    std::basic_istream >::operator>>(int&)

mov     ecx, dword ptr [rsp + 4]
cmp     ecx, 41
mov     eax, 42
cmovg   eax, ecx
pop     rcx
ret

Codul ce conține metoda inline:

#include 

template 
inline T const& MAX(T const& a, T const& b)
{
    return (a < b ) ? b : a ;
}

int main(  )
{
    int a = 0;
    std::cin >> a;
    return MAX(a, 42);
}

main:                                   # @main
push    rax
mov     dword ptr [rsp + 4], 0
lea     rsi, [rsp + 4]
mov     edi, std::cin

call    std::basic_istream >::operator>>(int&)

mov     ecx, dword ptr [rsp + 4]
cmp     ecx, 41
mov     eax, 42
cmovg   eax, ecx
pop     rcx
ret

Aș spune că ați face mai mult rău dacă forțați compilatorul să folosească inline pentru anumite funcții decât dacă îl lăsați să decidă dacă e mai bine să fie inlined sau nu. De fapt, azi atât GNU, cât și Google oferă multe resurse pentru a vă ajuta să optimizați timpul de compilare al compilatoarelor. Utilizați rezultatele acelor programatori bine plătiți, cu doctorat (unde e posibil), și nu vă pierdeți timpul prețios încercând să faceți ceva ce un calculator ar putea să facă mai bine. În majoritatea cazurilor, puteți uita de lucruri precum dead code elimination, loop unfolding, even inlining. Dacă doriți să faceți acest lucru manual, utilizați un IDE, de exemplu, InteliJ/CLion de la JetBrain care oferă analize bune de cod și trăsături ce pot ajuta în refactorizare.

Regula #2: Dacă trebuie să o faci: MĂSOARĂ!

Când compilatorul primește cod de performanță joasă, codul nu va fi optimizat. Chiar dacă compilatorul este destul de inteligent, acesta nu este o baghetă magică. Totuși, noi, programatorii, avem, de obicei, preconcepții că o anumită bucată de cod performează rău. Începem să optimizăm această bucată. Poate aveți nevoie de o jumătate de săptămână, iar rezultatele sunt dezamăgitoare. Să facem un pas în spate. Cât de siguri suntem că acea bucată de cod ne-a consumat cel mai mult timpul și energie?

Am verificat? La un moment dat, am dezvoltat o aplicație care a parsat un fișier text, am prelucrat datele, iar rezultatele le-am introdus într-o bază de date via Hibernate. Aplicația a fost înceată și a generat o eroare de tip excepție de memorie. Procesarea nu a părut că are probleme vizibile, deci candidatul ideal pentru optimizare a fost procesul de parsare de fișier. După câteva zile de lucru, am putut parsa fișierul cu aproximativ 50% mai repede, potrivit cu cazurile mele de test. Ce surpriză! Când am integrat soluția în aplicația originală, nu am văzut nicio schimbare sau îmbunătățire. Am făcut un pas în spate și am făcut ce trebuia să fac de la bun început: am profilat întreaga aplicație. Rezultatele au fost surprinzătoare: mai puțin de 5% din timp l-am petrecut pe parsarea fișierului, mai puțin de 10% pe procesare, iar restul pe calluri SQL. S-au realizat apeluri distincte de inserţie pentru fiecare linie procesată. Problema se poate rezolva cu inserări multiple de tip batch.

Ne-am învățat lecția: profilați aplicația la nivel înalt.

Găsiți punctele fierbinți. Pentru C++, aș recomanda setul de tooluri perf . Setul este gratuit, puternic și se poate rula în mod consolă. VTune de la Intel s-a îmbunătățit foarte mult în ultimii ani, are o interfață grafică bună, dar trebuie să plătiți pentru ea. Pentru aplicațiile Java, prefer NetBeans. Dacă vă plac armele serioase, folosiţi JProfiler. Odată identificate zonele cu probleme, putem trece la micro-benchmarking cu teste ce rulează și pe codul existent, și pe cel îmbunătățit, astfel încât să putem măsura îmbunătățirea.

Deci, a doua regulă este: să nu ai încredere în nimeni, măsoară. Măsoară lucrul potrivit. Dacă măsurăm lucrul greșit, ajungem la o soluție greșită.

Regula #3: Cunoașteți toolurile!

Când vorbim de optimizarea performanței, majoritatea persoanelor se gândesc la lucruri abstracte precum un sistem de operare special sau o linie neagră magică în cod, pe care doar cei cu adevărat inițiați o știu sau o înțeleg. Da, puteți gândi lucrurile la acest nivel, dar, de obicei, după ce fiecare fruct care este la îndemână a fost cules, te lupți și pentru ultimele nanosecunde.

Organizăm un concurs în care rugăm programatorii să rezolve o problemă ușoară. Am primit o soluție O(n) și una O(1). Spre surprinderea mea, mai puțin de 0.5% dintre participanți au implementat o soluţie complexă. Deci, nu te grăbi ; dacă e nevoie, pune mâna pe pix și hârtie, și asigură-te că nu există un alt algoritm mai bun pentru problema ta. Va fi un motiv în minus pentru optimizare ulterioară.

Memoria este ieftină. Într-adevăr, gândindu-ne la hardware-ul din ziua de azi, este foarte ieftin să adăugăm mai multe module de memorie fizică. Totuși, gestionarea unei memorii mari poate reduce performanța. În arhitectura modernă C++, apelarea funcției new pentru alocarea de spațiu de memorie costă între 160 și 300 de cicluri CPU. Spre comparație, realizarea unei înmulțiri necesită 1-2 cicluri, o împărțire în jur de - 30-35 cicluri. Nu este foarte mult, dar dacă codul vostru merge bine, să zicem, 10 înmulțiri și o alocare/dealocare: 2 cicluri de înmulțiri de 10 ori vor rezulta în 20 de cicluri de muncă utilă. Să numărăm doar new cu 160 de cicluri. Ar presupune că doar 11% din timp s-a consumat pe munca efectivă, 89% putând fi optimizat. Programatorii Java și .Net ar putea spune, în acest moment, că ei gestionează memorie și colectori de reziduuri ultra-performanți.

Dacă ne lăsăm ghidați de motto-ul "cel mai bun cod este să nu avem cod deloc", aș spune că cel mai rapid cod este cel neexecutat. Gândiți-vă la aceasta când colectorul de reziduuri vă pune în pauza codul care rulează în JVM, pentru a mai elibera memorie. Dacă este posibil, evitați alocarea dinamică de memorie. Recomand să alocați memorie de la bun început și să o reutilizați ulterior.

Obiecte ce nu se schimbă. În Java, putem uita ușor că Stringurile nu se schimbă. Cât de des ați scris ceva similar cu cele de mai jos?

public String FooFunction (String input1, 
String input2, String input3)
{
    return "Input1 = " + input1 + "Input2 = " 
           + input2 + "Input3 = " + input3 ;
}

De câte ori v-ați gândit că se poate traduce în ceva de genul

public String FooFunction (String input1, 
String input2, String input3)
{
    String anon1 = "Input1 = ";
    String anon2 = anon1 + input1;
    String anon3 = "Input2 = ";
    String anon4 = anon2 + anon3;
    String anon5 = anon4 + input2;
    String anon6 = "Input3 = ";
    String anon7 = anon5+ anon6;
    String anon8 = anon7 + input3;

    return anon8;
}

Va genera câteva stringuri reziduale, corect? Acest lucru e acceptabil dacă FooFunction este apelat de câteva ori. Dar, dacă folosiți o funcție similară pentru a crea o interogare SQL, să zicem cu 100 de parametri și o apelați de câteva milioane de ori? Elementele reziduale vor crește exponențial. La un anumit punct, ar fi bine să folosiți un constructor de stringuri static și să curățați totul de fiecare data când concatenați un alt set de stringuri.

Din fericire pentru cei care folosesc Java, paragraful 15.17.1.2 din Specificațiile Limbajului Java zice în felul următor "To increase the performance of repeated string concatenation, a Java compiler may use the StringBuffer class ". Suntem salvati din nou de regula numărul unu.

Utilizarea vectorilor. Ce este un vector? Conform www.cppreference.com: Este un container de secvențe care include tablouri de dimensiuni variabile. Grozav! Deci, nu trebuie să ne preocupe dimensiunea unui tablou. Dacă avem nevoie de spațiu, îl vom obține ca prin magie. Plătim prețul în cicluri CPU. De ce? Vectorii au o trăsătură care îi face rapizi când se aplică iterații asupra elementelor lor componente, deoarece elementele lor sunt stocate nefragmentat. Să analizăm exemplul următor. Puneți 10 elemente într-un vector.

Doriți să mai adăugați unul. Totuși, nu mai există spațiu pentru acesta. Ce se întâmplă? Containerul alocă un nou spațiu de memorie continuu mai mare decât cel original, de obicei, mai mult decât aveți nevoie. După aceea, copiază vechiul spațiu de memorie pe cel nou și îl dealocă pe cel vechi. Ce se întâmplă când faci aceasta de câteva milioane de ori? Memoria devine fragmentată. Va lua mai mult timp să faceți un spațiu de memorie nefragmentat suficient de mare, copierea din vechea în noua locație va dura mai mult. Dacă sunteți norocoși, colectorul de reziduuri (dacă aveți unul) și-a făcut deja treaba, și nu veți primi mesaje de tipul "out of memory exception".

Am analizat doar niște exemple generice, dar sper că v-am convins să vă gândiți la ceea ce se întâmplă "în spatele scenei" și să utilizați toolurile așa cum au fost gândite.