0xDEADBEEF

RSS odkazy english edition
««« »»»

Protip: Eliminujte zbytečné maskování

9. 6. 2022 #protip

Kompilátory nejsou vševědoucí. Někdy generují ne zcela optimální program, protože nedokážou využít všechny dostupné informace.

Vezměte si tohle jako příklad:

int4 a;
int4 b;
int* ptr;

int4 res = pcmpgtd(a, b);
int mask = movmsk(res);

ptr += popcnt(mask) / 4;

Žádné překvapení se až po popcnt nekoná. Ale pak je to zkompilované do následující trojice instrukcí.

popcnt %edx,%edx
and    $0x3c,%edx
add    %rdx,%rax

GCC ví, že popcnt vyprodukuje číslo v rozmezí 0 – 64. Dále ví, že dělení je ekvivalentem x >> 2 a převod indexu na int* pointer zas x << 2. Ve výsledku tak jen odmaskuje 2 dolní bity jednou and instrukcí.

Na druhou stranu je vidět, že nedokáže zužitkovat znalost, odkud proměnná pochází. (Aspoň tedy GCC 10 nebo 11 na nichž jsem to ověřoval.)

Kombinace pcmpgtdmovmsk nastaví n bitů, kde n je násobek 4. int má 4 bajty, pcmpgtd nastaví všech 32 bitů intu v každém pruhu na 0 nebo 1 v závislosti na výsledku porovnání a movmsk do cílového intu nastaví 4 bity s polaritou odpovídající každému bajtu. Ve výsledku proměnná mask může obsahovat jen 0, 4, 8, 12 nebo 16 bitů a inkrementace pointeru proběhne o násobek 4, nikdy to nebude 3 nebo 7, výsledek je správně zarovnaný a and není potřeba.

Když kód změním stylem, který dá kompilátoru najevo, že přebírám otěže,

ptr = cast(uint*) ((cast(ubyte*) ptr) + popcnt(mask));

ve výsledné binárce se zbytečné maskování neprovádí a i když se chová identicky, je o jednu instrukci kratší.

popcnt %edx,%edx
add    %rdx,%rax

Jedna jednotaktová instrukce nemusí znamenat mnoho, obvykle jde o rozdíl stěží měřitelný, ale pokud se nachází v řetězu závislostí, může jít o příjemný bonus.

píše k47 (@kaja47, k47)