V prvni rade diky za clanek, v posledni dobe na rootu moc technickych clanku neni.
Zajimalo by mne na ktere typy uloh je mozne uplatnit tenhle low-level typ profilingu? I kdyz obdivuju hacky typu "Cormackova" inverse square rootu s 0x5f3759df, prijde mi ze to jde uplatnit jenom ve velmi specifickych podminkach:
1. Musite psat aplikaci "from scratch" (aby bylo mozne zvolit vsechny datove struktury)
2. Hotspoty musi byt zalozeny hlavne na aritmetice (treba grafika je celkem dobry priklad; bitva s memory alokatorem kvuli cache-miss je masakr, viz nize)
3. Nesmite prilis pouzivat 3rd-party knihovny (nejvic nekolik), protoze nevite "co kde lita" a hrabat se v nich/prepsat to treba z casovych duvodu nejde
4. Nesmi to byt multiplatformni (prekladacem vygenerovany kod na vsech platformach neuhlidate)
Konkretni zkusenost: multiplatformi (linux/windows) prekladac v C++, typicke struktury jsou grafoveho charakteru a mapy - syntakticky strom, tabulky symbolu, apod. Pouziva celou armadu knihovnen typu xerces, boost... Cilem je udelat existujici kod rychlejsi.
Tohle jsou nejake typicke bottlenecky a postrehy pro tenhle pripad:
1. "Nevyjimecne" pouziti vyjimek (=nekolik desitek/stovek) umi spolehlive zabit dobry algorimus, specialne se starsi glibc a hazenim pres hranici knihoven
2. Pouziti std::algorithm a boost::lambda byva rychlejsi (i dvojnasobne) nez "emulovani" pres for/while (zavisi jak moc prinutite C++ prekladac inlineovat kratke funkce)
3. std::map a std::set jsou paradoxne rychlejsi nez hash_map a hash_set navzdory O(log(n)) vs O(1) pro male mapy/sety (< 1000 polozek). Na tomhle ma nejspis zasluhu C0x standard, ktery pozaduje lokalni iteratory na buckety=> implementace nemuze byt open-adressing (=>extra mallocs => extra cache misses). boost::unordered_set a boost::unordered_map jsou (mirne) lepsi nez hash_set a hash_map, ale pro male sety/mapy je lepsi pouzit std:: verze (zalozeny na RBtree)
4. msvc ma pomaly malloc/free/new/delete, mirne rychlejsi exception unwinding nez gcc+glibc (se starsi glibc 2.3.x jsou ty vyjimky hodne spatny). reserve() muze vyrazne pomoci kdyz vite kolik veci nasypete do STL kontejneru
5. U gcc dokaze obrovske mnozstvi cyklicky vytvarenych a mazanych mensich hash_setu/hash_map udelat celkem brutalni memory fragmentation (napr. skutecne mate naalokovano 20MB, jenze kvuli fragmentaci je namapovano pro proces klidne 200 MB RSS)
6. Kdyz zacnete pouzivat 3rd party knihovny, budete se celkem divit, ze dve podobny funkce jsou implementovany uplne jinak (jedna je rychla a ta druha to zabije); obcas se oplati malou cast preimplementovat
7. I kdyz se pri slozitosti konstanta ignoruje, pri profilingu na ni k*va zalezi ;-)
Slo by low-level pristup z clanku aplikovat nejak v tomhle pripade? (tam hlavne nevite jak to nejaka knihovna rozhazi po pameti) Treba by slo napsat si vlastni memory allocator nebo pouzit nejaky page coloring kernel patch (jenze v prvnim pripade to neni uplne sranda a druhym pripade tezko presvedcite uzivatele pouzit kernel patch, ktery muze zmrvit vykon ostatnich veci).
BTW: pouzivame NaN ve specialnich pripadech matematickych funkci jako hodnotu "undef" (funkce v bode nedefinovana, testovano je to porovnanim). Bohuzel jsem nemel cas zatim zmerit, jestli by se to zrychlilo pouzitim treba numeric_limits<double>::max misto NaN. (Podival jsem se na implementaci finite() a ta to dela bitovou maskou => FPU exception nemuze nastat)
"Slo by low-level pristup z clanku aplikovat nejak v tomhle pripade? (tam hlavne nevite jak to nejaka knihovna rozhazi po pameti)"
To si nejsem jisty. Ja osobne pouzivam pouze libc a libm. Ostatni si pisu.
Nicmene podobny low-level pristup je pouzity v knihovne fftw (FFT na 1000 zpusobu), ovsem ponekud brutalne. Na druhou stranu je to (snad porad) nejrychlejsi implementace FFT a dokonce multiplatformni (toho dosahuji tak ze parametry (a dokonce poskladani kusu kodu ktere FFT implmementuji) se doladuji behem kompilace na target machine nebo dokonce za behu (v inicializaci)).
V high-level se to da pouzit jen omezene pri navrhu. Treba kdyz mate nejaky AI program ktery nejprve treba neco pocita pomoci SVM (nebo neuronovych siti) a nasledne s temi vysledky provadi A^* algoritmus tak na starsich pocitacich, ktere mely pomalou aritmetiku a relativne rychle pristupy do pameti bylo lepsi udelat jednodussi SVM a narocnejsi A^*. Dnes je to naopak. Tedy za predpokladu ze celkova uspesnost toho programu se da balancovat mezi SVM a A^*.
