Daily Curious Perversion of Programming #16

El is felejtettem már, de most valami során ismét feljött a kérdés. A nyelv mindegy, de C előnyben. A válaszom az volt, hogy assemblyben pl. SSE4-en és felette a POPCNT utasitás pont erre való. :) De valami hasonlót már más architektúrák (ARM) mindenféle kiterjesztéseiben is láttam. Viszont ha kizárólag C-ben gondolkozunk, akkor a "triviális" megoldás ugye a következő:

int bitcntf(unsigned char num) {
   int cnt;
   int res = 0;
   for (cnt = 0; cnt < 8; cnt++) {
      if (num & (1 << cnt)) res++;
   }
   return res;
}

A következő kérdés az volt, hogy hogyan optimalizálnám ezt meg. Nagy naívan én kapásból kizártam a kézi loop unrollingot, mondván, azt úgyis megcsinálja a GCC, keressünk valami jobb megoldást. Később kiderült, hogy a GCC ugyan tényleg megcsinálja, ha akarod, de akkora mocskot generál belőle (legalábbis a GCC 4.0.3 AMD64, ami éppen kéznél volt a teszthez), hogy inkább hagyjuk... Tehát a "kézi" loop unrolling változat, amire az interjúztatóim gondoltak:

int bitcntu(unsigned char num) {
    int res = 0;
    if (num & (1 << 0)) res++;
    if (num & (1 << 1)) res++;
    if (num & (1 << 2)) res++;
    if (num & (1 << 3)) res++;
    if (num & (1 << 4)) res++;
    if (num & (1 << 5)) res++;
    if (num & (1 << 6)) res++;
    if (num & (1 << 7)) res++;
    return res;
}

Ez sem rossz, és jelentősen gyorsabb mint a forciklusos verzió. Én viszont egy teljesen más megoldással álltam elő:

unsigned char bitnum[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };

int bitcnt(unsigned char num) {
    return (bitnum[num & 0x0F] + bitnum[num >> 4]);
}

Az "nagy ötlet" természetesen a táblázatosítás volt, de egy lassú, gyenge (pl. embedded) procin egy 256 elemű (adott esetben alignment okok miatt int vagy word elemméretű, tehát 256 byte-nál nagyobb) táblázat cache-ben tartása nem biztos, hogy a leggyorsabb és a leghatékonyabb, főleg, ha még mást is kell mellette csinálni, ezért egy tizenhat elemű táblázatba vettem fel, hogy 0-15-ig (4 bit) hány bit van bekapcsolva az egyes értékekhez. Ezután a byte-ot csak ketté kell maszkolni, tehát egy maszkolásból, egy eltolásból, két táblázat indexelésből és egy összeadásból megvan a végeredmény. Nincs 8 feltétel, nincs 8 hozzáadás, nincs 8 maszkolás. Már csak az a kérdés, hogy a valóságban is hatékonyabb-e, mint a loop unrolling, és a táblázatból lévő memóriaolvasások valóban gyorsabbak-e, mint a tilitoli, amit a fordító úgyis jórészt a regiszterekben követ el. Jó esetben. Én meg voltam róla győződve, hogy gyorsabb, de méréseket nem végeztem. Eddig.

A tesztelő kód rém egyszerű, mégpedig a következő:

#include *stdio.h*

int main() {
   int cnt;
   long x = 0;
   for (cnt < 0; cnt < 1000000000; cnt++) {
      x += bitcnt(cnt);
   }
   printf("%d\n",x);
   
   return 0;
}

Egymilliárd iteráció, had szóljon! A teszthardver egy AMD Athlon 64 2800+, 64 bites Linux-szal, a tesztforditó GCC 4.0.3, amit a rajta futó disztribhez adtak. A GCC-hez az -O2 kapcsolót használjuk, mert -O3-mal sikerül kioptimalizálni neki az egész gyakorlatilag az egész ciklust... Eredmények:

For ciklusos változat:

charlie@testmachine:~$ gcc bitcntf.c -O2
charlie@testmachine:~$ time ./a.out
-294967296

real    0m17.467s
user    0m17.033s
sys     0m0.064s

A kézi loop unrolling változat:

charlie@testmachine:~$ gcc bitcntu.c -O2
charlie@testmachine:~$ time ./a.out
-294967296

real    0m8.343s
user    0m8.109s
sys     0m0.040s

És az én táblázatos változatom:

charlie@testmachine:~$ gcc bitcnt.c -O2
charlie@testmachine:~$ time ./a.out
-294967296

real    0m4.300s
user    0m4.188s
sys     0m0.016s

Hoppá. :) Mondhatjuk, hogy beigazolódott a sejtésem, tényleg a táblázatos változat a leggyorsabb. Ebben a tesztben, persze. Mert mindent tovább lehet fejleszteni. Például kiváncsi lennék, ha egy random adatfolyam lenne betápolva a fenti függvényeknek, nem egy forciklus ciklusváltozója, akkor mi lenne az eredmény. Vagy, hogy esetleg hogy lehet továbbfejleszteni az ötletet. Esetleg, hogy az alignment számít-e, mivan ha a táblázat tagjai intek, wordök. Mi a helyzet más architektúrákkal (i386, ARM, PowerPC, m68k), van-e különbség az arányokban Intel és AMD között, és így tovább.

Egyébként a teljes igazsághoz hozzá tartozik, hogy a fenti eredményből már majdnem egy másodperc csak a függvényhívás, ugyanis az üres ciklus kb. 1 másodperc alatt fut le... Tehát a leggyorsabb változat valószínűleg a következő makró lenne:

unsigned char bitnum[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
#define BITCNT(num) (bitnum[num & 0x0F] + bitnum[(num & 0xF0) >> 4])

.. de sehogy sem bírtam elérni, hogy a használt GCC ne szórja ki a ciklus belsejéből, már sima -O-nál is... Szóval egyelőre ennyi. Remélem másnak is hasznosak és tanulságosak a fent leírtak, nekem mindenképpen azok voltak. Főleg mert ez egy elég jellemző kérdés bitvadász-programozók interjúztatásánál, eddig három különböző cégnél találkoztam vele. Végül pedig a nagy kérdés:

Ki tud gyorsabbat ennél? :)

(ps: Egyébként sejtésem szerint nem én fingtam a passzát szelet, vagyis "találtam fel" ezt a táblázatos verziót, bár máshol még nem találkoztam vele, de annyira nem is kerestem... A különösen szép benne szerintem az, hogy valószínűleg nyelvtől és fordítótól függetlenül gyors, hiszen nem nagyon van benne optimalizálnivaló, annyira rövid. Egyébként 10-ből kilenc programozó akit eddig megkérdeztem, maximum a loop unrollig jutott, egyvalaki mondott egy másik megoldást, az ő ötlete: "res += (num & (1 << N)) >> N;", hogy az IF-eket kiírtsa a kódból, ahol N az aktuálisan tesztelt bit, nyilván ebből kell 8db egymás után, de ez érdekes módon a tesztkörnyezetünkben kb. 10%-al lassabb mint az IF-es verzió.)