Koliko vas je bitkov mojih malih?
[c]
static const unsigned char BitLookupTable[] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
bits = BitLookupTable[value];
[/c]
Je lahko še hitreje?
4 thoughts on “Koliko vas je bitkov mojih malih?”
eh, žrtvovat pomnilnik za pospešitev, tako da vnaprej izračunaš rezultate ali delne rezultate, je vobče eden najboljših pristopov optimizacije za hitrost, če le ne porabiš preveč pomnilnika.
vseeno, lotiva se tvojega vprašanja podrobno in analitično, kot se za teoretika spodobi… 😉
tvoja tabela ima 256 zlogov. v register ne bo šla, kne? vsako štetje bo torej zahtevalo en dostop do pomnilnika.
glede na to, da pospešuješ operacijo, ki bi pri najbolj naivnem možnem pristopu vzela vsega nekaj jako preprostih strojnih ukazov in torej vsega nekaj ciklov procesorjeve ure, bo tvoj pristop dejansko uporaben le, če bo dostopanje do pomnilnika vzelo manj časa kot pa teh nekaj ciklov.
očitno torej pri štetju ne smeš dostopati do glavnega pomnilnika, ker boš čakal in čakal in čakal, da ti ram dostavi podatke, ura pa bo tiktakala. tale tabela mora bit v cacheu, ki je kar najbolj blizu procesorju.
res je majhna in paše v eno vrstico cachea na vsakem sodobnem procesorju. privzemiva še, da se začne na primernem naslovu, tako da ni razdeljena v dve vrstici cachea. vprašanje pa je, ali jo bo kakšen drug dostop do pomnilnika med zaporednimi štetji vrgel iz cachea.
odgovor na to je mogoč le ob poznavanju vzorca dostopov tvoje konkretne kode do pomnilnika.
takole čez prst pa lahko rečeva, da se ti to splača, če narediš več zaporednih štetij v zanki. če tole uporabljaš le vsake toliko in med dvema štetjema počneš kup drugih reči, potem bo tovoj pristop pmsm počasnejši od najbolj butastega možnega pristopa, recimo:
static inline int countbits(unsigned char c) {
for(n = 0, i = 0; i < 8; i++) {
n += (c & (((unsigned char)1) <> i;
}
}
prevedenega s prevajalnikom, ki mu povemo, naj optimizira kodo z razvijanjem zanke.
Imam bitmap velik priblizno 500kB pa vse do nekaj megabytov. V njem moram presteti vse bite, do poljubnega bita.
Nekako takole: bitCount(bitmap, last_bit); Vrnem pa potem stevilo prizganih bitov do zadnjega bita.
Od zacetka delam z vecjimi enotami, 32 bitnimi ‘wordi’. Testni bitmap je tak, da je zadnjih 10% bitov vedno prizganih, potem je pa se 10% bitov nakljucno prizganih po ostalih 90% bitmapa. Na koncu imam ~ 20% bitov prizganih.
Na koncu pa prakticno vedno ostane nek ostanek, ker se stetje ne zakljuci na 32 bitov. Torej mi ostane vsaj en byte za prestet ‘na roke’. Povprecno pa dva oziroma eden byte in pol. 🙂
Tale lookup tabela je stetje teh ostankov pohitrila za kaksnih 30 mikro sekund.
Ena pohitritev, ki bi se lahko prisla v postev je preverjanje vsakega integerja, ce je ‘poln’ torej, ce so vsi biti vklopljeni. Vendar se to verjetno splaca sele pri zadnjih 10% bitmapa. Pa se tam vprasanje.
Za zgoraj omenjeni bitmap v katerem je ~100.000 prizganih bitov ponucam tam nekje med 0,0007 in 0,0008 sekunde.
Najbolj butasta mozna resitev pa potebuje med 0,002 in 0,003 sekunde.
Ah, s kaksnimi bizarnimi optimizacijami se ukvarjam. Ampak tukaj gre za cast! ;> Oracle se hvali z 3.2 milijona inserti v bazo v eni sekundi, treba jih je premagati. Verjetno bodo imeli prednost kakega n-way clusterja. :))
V GCC imas tudi funkcijo __builtin_popcount(unsigned int x), ki ti presteje bite. x86 seveda nima za stetje bitov zato je prakticno enako, kot ce bi funkcijo spisal sam — no ja, ti jo vsaj ni treba.
Dobra metoda je objavljena v knjigi Hacker’s digest, gre pa nekako takole:
i = i – ((i >>> 1) & 0x5555555555555555L);
i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L);
i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
i = i + (i >>> 8);
i = i + (i >>> 16);
i = i + (i >>> 32);
return (int)i & 0x7f;
Priporocam knjigo, ce te zanimajo taki in podobni “bit hacki” 😉
Mitja, ja nekaj podobnega imam narejeno za preverjanje 32 bitnih vrednosti. Deluje precej hitro.
Comments are closed.