XOR csere

„Premature optimization is the root of all evil”, mondta egykor Donald Knuth. Igaza is volt; a programozók sokszor unalomból, tudatlanságból, szakmai hiúságból teljesen fölöslegesen optimalizálgatnak olyan kódrészleteket, amelyek ritkán futnak, esetleg eleve elég gyorsak voltak. Az optimalizálásnak általában ára van: bonyolódik tőle a kód, csökken az olvashatósága. Mi több, sokszor el is rontják ilyenkor a kódot.

Annak idején, amikor még mindenki Assembly nyelvű programokat írt, rengeteg apró optimalizálást kézzel végeztek el a programozók. Például egy regiszter nullázása helyett: movl $0, eax (C-ben: eax = 0), inkább saját magával XOR kapcsolatba hozták azt: xorl eax, eax (eax ^= eax). Mert ez kevesebb bájtot foglalt, nem kellett a 0 számot eltárolni hozzá a memóriában. Akkoriban jöttek rá arra is, hogy két regiszter értékét szintén meg lehet cserélni az xor gépi utasítással:

xorl eax, ebx
xorl ebx, eax
xorl eax, ebx

A módszer előnye, hogy nincsen hozzá szükség segédregiszterre. Eddig minden rendben is lenne. A baj csak az, hogy a '70-es években kitalált, az akkori szemléletet tükröző módszer annyira beszivárgott a köztudatba, hogy egyesek manapság is használják, magas szintű programozási nyelveken. A XXI. században, amikor a fordítóprogramok legtöbbje gyorsabb kódot tud generálni, mint amilyen Assembly kódot az emberek írnának.

Mi a gond igazából az XOR cserével? Leginkább az, hogy nem fejezi ki a szándékot. Ha leírjuk ezt, mondjuk C-ben:

a = a^b;
b = b^a;
a = a^b;

akkor nem csak a többi programozó nem fogja tudni, mit akarunk itt csinálni (hacsak nem ismerik a trükköt), hanem a fordítóprogram sem. Ellenben ha ezt írnánk:

temp = a;
a = b;
b = temp;

akkor azt minden programozó felismeré, és mint az kiderül, a fordítóprogramok is gyorsabb kódot generálnának.

Induljunk a legfontosabb kérdéssel! Helyes-e a kód egyáltalán? A fenti kódrészlet sok programban megtalálható ilyen formában:

void xorSwap(unsigned *a, unsigned *b) {
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

A probléma csak az vele, hogy helytelen. Ha a == b, azaz a két pointer ugyanarra a változóra mutat, akkor a változó értéke lenullázódik már az első sorban, mivel x^x nulla, bármilyen x-re:

int main(void) {
    unsigned a = 5;
    xorSwap(&a, &a);
    printf("%u", a);    // 0
}

De hát ki írna swap(&a, &a)-t? Pont ilyet nyilván senki, de más, kevésbé triviális helyen mégis könnyen előfordulhat ehhez hasonló. Gondoljunk például egy rendezésre, amelyben egy tömb két elemét cseréljük. Ha a csere előtt nem végeztünk i != j ellenőrzést, akkor a fenti függvény pointerei meg fognak egyezni egymással, a tömb néhány eleme pedig lenullázódik rendezés közben:

unsigned arr[100];

for (/* ... */) {
    /* ... */
    xorSwap(&arr[i], &arr[j]);  // Ha i==j, akkor &arr[i]==&arr[j]
}

Ezen már nem látszik ránézésre, hogy esetleg saját magával próbál egy változót megcserélni. Pedig ilyen esetben is elvárhatnánk a függvénytől a helyes működést. Ne is folytassuk a gondolatmenetet: a fenti xorSwap() függvény helytelen. Javítható egy if (a==b) return; sorral, de az meg lassítani fogja a működését. Minden egyes hívásnál, márpedig legtöbbször a != b, az a == b csak ritkán fordul elő. Megérte? Nem. Ha általában ezerből csak egy a == b esetünk van, akkor amiatt az egy miatt nem kellene a másik 999 cserét lassítanunk.

A segédváltozós cserének nem lett volna ilyen problémája.

Nézzük meg a generált kódot is! Hogy értsük az Assembly kódrészleteket, vizsgáljuk meg előbb egy nagyon egyszerű függvény lefordított változatát:

void set(unsigned *a, unsigned *b) {
    *a = 1;
    *b = 2;
}

movl    $1, (%rdi)
movl    $2, (%rsi)
ret

A függvény az a pointer által mutatott változóba 1-et tesz. Ezt a műveletet végzi el az első movl utasítás; az rdi regiszter, % karakterrel jelölve, tartalmazza a pointert, és az Assembly kódban a () kerek zárójel jelenti az indirekciót. Tehát (%rdi) az rdi regiszter által mutatott memóriaterület. Hasonló a következő sor: a movl adatot mozgat, a 2-es értéket másolja az rsi nevű regiszter által mutatott helyre. A ret végül visszatér a függvényből.

Következzen a mezei, segédváltozós csere függvény kódja! Ezzel kell majd az XOR cserének versenyeznie:

void swap(unsigned *a, unsigned *b) {
    unsigned temp = *a;
    *a = *b;
    *b = temp;
}

movl    (%rdi), %eax
movl    (%rsi), %edx
movl    %edx, (%rdi)
movl    %eax, (%rsi)
ret

Mi is történik itt? A segédváltozó eltűnt, helyette a fordító nem egy, hanem kettő regisztert használt! (Furcsa, ugye? Az XOR cserével spórolni akartunk, ehelyett a generált kód épp ellenkezőképp, bőkezűen bánik a regiszterekkel!) Az rdi által mutatott adat az eax regiszterbe, az rsi által mutatott adat az edx-be kerül. Utána pedig visszaíródnak a memóriába, csak fordítva: (rdi)→eax→(rsi), illetve (rsi)→edx→(rdi) a trükk.

Észre kell vennünk, hogy ez a két olvasási és két írási művelet az elvi minimum, ami lehetséges. Mindkét változót ki kell olvasnunk, és mindkét változó értéke módosul. Tehát ennél kellene az XOR csere okosabb legyen, az elviekben lehetséges legjobbnál. (Innen szép nyerni!) Vizsgáljuk meg az XOR cserés változat kódját:

movl    (%rdi), %eax
xorl    (%rsi), %eax
movl    %eax, (%rdi)
xorl    (%rsi), %eax
movl    %eax, (%rsi)
xorl    %eax, (%rdi)
ret

Ez ránézésre rosszul kezdődik... Hat utasítás van benne, az előbbiben csak négy volt. Sőt, ezek közül az összes a memóriához is fordul! Tehát hat utasítás, amiből három olvasás és három írás, kettő+kettő helyett. Sokkal rosszabb a helyzet, mint az előbb, ez a kód kb. másfélszer lassabb! Ráadásul még helytelen is, hiszen emlékszünk az előbbről, hogy a == b, azaz rsi == rdi esetben még le is nullázza a változót. Ha ezt kiegészítenénk az a != b vizsgálattal, még hosszabb kódot kapnánk.

Nézzük meg kicsit tüzetesebben a fenti Assembly kódot! Az egyes utasítások melletti kommentek C kód formájában magyarázzák, mi történik, az eredeti pointerek neveit és a regiszterek neveit használva:

movl    (%rdi), %eax        ; eax = *a
xorl    (%rsi), %eax        ; eax ^= *b  !
movl    %eax, (%rdi)        ; *a = eax
xorl    (%rsi), %eax        ; eax ^= *b  ?
movl    %eax, (%rsi)        ; *b = eax
xorl    %eax, (%rdi)        ; *a ^= eax

A processzornak rengeteg regisztere van, amivel dolgozni tud: eax, ebx, ecx, edx stb. A segédváltozós cserében ezeket használta is a fordító, itt viszont mindent az eax regiszterrel csinál. Sőt a második és a negyedik sor ugyanaz, mindkettő a *b változó értékét olvassa ki. De mi célból generál ilyen kódot a fordító, miért fordul a memóriához kétszer? Miért nem olvassa be inkább a *b értékét egyszer, mondjuk az edx-be, mint az előbb, és utána dolgozik azzal – ahelyett, hogy megint a processzornál sokkal lassabb memóriára kellene várni?

Tekintsünk egy egyszerűbb példát, amelyen jobban látszik, mit vesz figyelembe a fordító! Egészítsük ki az előbbi set() függvényt egy sorral! Vajon mennyi az alábbi függvény visszatérési értéke?

unsigned set(unsigned *a, unsigned *b) {
    *a = 1;
    *b = 2;
    return *a;
}

Ránézésre azt mondanánk, természetesen 1. De ez egyáltalán nem biztos! Ha a függvényt úgy hívjuk meg, hogy a == b, azaz a két pointer ugyanarra az unsigned változóra mutat: set(&x, &x), akkor bár az első értékadással az x-be 1-et teszünk, de a másodikkal felülírjuk, és 2 lesz a tárolt érték. Emiatt a return *a sorhoz a fordítónak egy olyan utasítást kell generálnia, amelyik kiolvassa a *a értékét, mert nem lehet tudni, hogy a *b = 2 nem volt-e rá hatással. A generált kódrészlet emiatt az alábbi:

movl    $1, (%rdi)
movl    $2, (%rsi)
movl    (%rdi), %eax
ret

Ez egy buta példa, de mégis megmutatja: a fordító fel van készítve erre a lehetőségre; olyan kódot generál, amelyik az a == b esetben is helyesen működik.

Ha a != b, akkor viszont a visszatérési érték biztosan 1 lesz, mert a *b = 2 hatására *a nem módosul. Tegyük fel, hogy mindig így hívjuk meg a függvényt! Ha ez teljesen biztos, akkor a fordító a return *a sort return 1-nek vehetné. De ehhez valahogyan mondani kellene neki, hogy garantáljuk, a két pointer nem ugyanoda mutat, hogy biztosan senki nem fogja set(&x, &x) formában meghívni a függvényt. Erre vezették be a C99-ben a restrict kulcsszót (főként tömbműveletek gyorsítására): a programozó által restrict-tel megjelölt pointerről feltételezheti a fordító, hogy nincs más olyan pointer az adott látókörben, amelyik ugyanarra a változóra mutatna:

unsigned set(unsigned * restrict a, unsigned * restrict b) {
    *a = 1;
    *b = 2;
    return *a;
}

Ilyenkor a generált kódrészletben tényleg egy memóriaművelettel kevesebb van, nem olvassa már vissza a *a értékét:

movl    $1, (%rdi)
movl    $2, (%rsi)
movl    $1, %eax
ret

Miért lényeges ez az XOR csere szempontjából? Arról tudjuk, hogy úgysem működik helyesen, ha egyforma pointereket kap. A sebesség vizsgálatakor ezért adjunk neki még egy esélyt (halottnak a csók), vizsgáljuk meg a generált kódot restrict kulcsszóval együtt is – hátha azzal együtt gyorsabb tud lenni. De ne felejtsük, ez már eleve rosszabb program: a segédváltozós csere gond nélkül működött a == b esetben is. Az XOR-os cserénél az a != b korlátozás eleve többlet teher a függvény használóinak.

Szóval írjunk restrict kulcsszót a két pointerhez, és fussuk végig így a generált kódot:

movl    (%rsi), %edx
movl    (%rdi), %eax
xorl    %edx, %eax
xorl    %eax, %edx
xorl    %edx, %eax
movl    %edx, (%rsi)
movl    %eax, (%rdi)
ret

Még ez is sokkal hosszabbnak tűnik, mint a segédváltozóval megfogalmazott kód, három utasítással több. Viszont látszik, hogy legalább már használ két regisztert a fordító: beolvassa a két számot az eax, edx regiszterekbe, aztán azokon végrehajtja az XOR cserét (eax↔edx), végül visszaírja őket a pointerek által mutatott helyre.

Hogy micsoda?! Két regisztert használunk, beolvasunk két számot, megcseréljük a regisztereket, és kiírjuk az értéküket ugyanazokra a helyekre? Miért nem írjuk vissza őket fordítva a memóriába? Nézzük csak meg a kódot még közelebbről! A négy mov utasítás majdnem ugyanaz, mint ami a segédváltozós cserénél is generálódott! Csak míg ott a fordító fölismerte, hogy a beolvasott adatokat keresztbe visszaírva a memóriába, meg is van oldva a feladat, itt ezt nem történt meg. Nem értette, mit akarunk csinálni az XOR operátorokkal. Négy ugyanolyan mov utasítást kaptunk, mint az előbb, de mellé még három xor-t is.

Az XOR csere lassabb.

Az XOR cseréhez hasonló trükk lehetséges más műveletekkel is, például összeadással és kivonással. Egy ilyet használó kód:

void doubleAddSwap(double *a, double *b) {
    *a = *a + *b;
    *b = *a - *b;
    *a = *a - *b;
}

Persze amellett, hogy ez a szokásos a == b esetben hibás (ez is lenullázza a változót), egy további gond is van vele. A lebegőpontos számokról tudjuk, hogy a velük végzett műveletek sosem adnak pontos eredményt. double-ök esetében általában 16-17 tizedesjegynyi a pontosság. Mi történik, ha két olyan számot szeretnénk megcserélni, amelyek nagyságrendje nagyon eltér, pl. 10⁴⁰ és 10^-40?

int main(void) {
    double a = 1e40, b = 1e-40;
    printf("%g %g\n", a, b);
    doubleAddSwap(&a, &b);
    printf("%g %g\n", a, b);
}

1e+40 1e-40
0 1e+40

Az eredmény hibás, az egyik változó lenullázódott. Kell folytatni?

Az XOR csere ártalmas:

• helytelen működésű lehet,
• lassabb,
• és nehezebb megérteni az így megírt kódot a többi programozó számára.

Egyéb szempontok pedig nincsenek, amelyek szerint egy magas szintű programozási nyelven megírt programkódot vizsgálni lehetne.

Emiatt értelmetlen a fentihez hasonló apró mikrooptimalizálásokkal elrontani a programunkat. Az alábbi két függvény hatására mindkét esetben ugyanaz a kódrészlet keletkezik:

bool paros_e(int a) {
    return a % 2 == 0;
}

movl    %edi, %eax
andl    $1, %eax
xorl    $1, %eax
ret

bool paros_e_omg(int a) {
    return !(a&1);
}

movl    %edi, %eax
andl    $1, %eax
xorl    $1, %eax
ret

Aki nem hiszi, próbálja ki! A mai fordítókba bele vannak építve ezek az apróságok: tudja, hogy a 2-vel osztás maradéka az alsó bit, és azt is tudja, hogy a 0-val összehasonlítás ezek után a bit invertálásával elvégezhető. Ha ezeket a csavarokat mi építjuk be a programba, csak a kódunk minőségét rontjuk vele, az eredmény semennyivel nem lesz jobb. Ugyanígy, ha el kell osztatnunk egy számot néggyel, akkor írjunk a kódba is a/4-et! Majd ha a fordító jobbnak látja, léptetésre cseréli...

unsigned negyede(unsigned a) {
    return a/4;
}

movl    %edi, %eax
shrl    $2, %eax
ret

És tényleg.

A fordításokat a Code::Blocks-ban is használt GCC fordítóval végeztem, annak mostanság legelterjedtebb 4.8.4-es verziójával; legmagasabb optimalizálási szint, -O3 mellett. A használt ABI: Linux x86_64.