Dotaz: C++ Knihovna pro priblizne matematicke vypocty - sqrt, sin, csin apod.

[gld17]

Zdravim,

chtel bych se zeptat, zda-li nevite o nejake knihovne, ktera by pocitala sqrt treba s presnosti jen na tri desetinna mista (slo by to napsat ale chci optimalizovanou), potreboval bych udelat takovou jednoduchou analyzu obrazu ktera se bude delat na Raspberry Pi (bude slouzit pro pristani koptery do doku) a premyslim jak to udelat co nejmin narocne aby to vubec stacilo.

Je to moje diplomka a pouzit jen priblizne hodnoty sqrt mi prijde jako dost dobry napad ktery by usetril dost casu, protoze stejne bych vetsi presnost nevyuzil (math.h vraci normalne double).

Jinak bych si asi zkusil napsat sam nejaky assemblerovsky kod na to, cimz bych urcite zapusobil na porotu :D

---

---

Odpovědi

[Josef Kufner]

Podíval jsi se profilerem, že to drhne opravdu tam, kde si myslíš, že to drhne?

[gld17]

Diky za tip, zkusim to udelat, ale zatim tuhle cast jeste nedelam, nejsem tak daleko. Ptam se preventivne a informativne.

[jake]

v tom pripade bych to videl na predcasnou optimalizaci

[gld17]

nevim jak ty, ale ja, narozdil od tebe, vim diky svemu zalozenemu tematu o tomto vypoctu odmocniny: https://en.wikipedia.org/wiki/Fast_inverse_square_root#Overview_of_the_code

Takze ses jen dalsi neprihlaseny brblal.

[rADOn]

Tim "narozdil" bych si nebyl byt tebou tak jistej, to to co jsi objevil je legendarni a dobre znamej hack. Kdyz budes patrat dal tak se da najit i rozhovor s Carmackem kde (krome popreni otcovstvi) celkem jasne rekl ze dnes uz je blbost takovy vylomeniny delat.

BTW Jestli te zacaly bavit prekomplikovany optimalizace tak pogoogli termin "duff's device", to se ti bude libit. Zadnej z (nezasvecenych) ceckaru v praci nebyl schopnej rict jestli je to legalni C kod

[stativ]

Nejenom, že je to dobře známé, ale výkonově už je to k ničemu. Tedy většinou. Je to asi tak dva roky zpátky, kdy jsem potřeboval normalizovat hodně vektorů, tak jsem zkoušel různé přístupy a fast inverse square root byla v C několikanásobně pomalejší než knihovní funkce. A o řád pomalejší než SSE intrinsics. Co bylo zajímavé, tak v C# byl, pokud se dobře pamatuji, fast inverse srovnatelný s knihovní funkcí. SSE pak bylo kvůli přepínání do unmanaged módu očekávaně nejpomalejší.

[jake]

brblal? mas nejakej komplex? ... resit rychlost vypoctu odmocniny v tehle fazi vyvoje, ve ktere jsi, je proste nesmysl - az ti to pobezi a vykonove to nebude dostatecny, tak pak teprve hledej, kde tomu pomuzes, do ty dobe je tohle ztrata casu ... ale tak je to tvuj cas, ze jo ... JFYI tenhle "Cormackuv" trik zna fakt asi kazdej, tedy i ja - ale jo, ses borec, ze to znas taky

[axel]

Zdravim, Jinak bych si asi zkusil napsat sam nejaky assemblerovsky kod na to, cimz bych urcite zapusobil na porotu :D

Nepochybuju o tom, ze tvuj kod v assembleru bude radove vykonnejsi, nez knihovni funkce. Zabyvat se podobnou - podle mne nesmyslnou - uvahou o optimalizci vypoctu odmocniny v kontextu programu na rizeni koptery je ucebnicovy priklad uviznuti v detailu, ktery na porotu jiste zapusobi, mozna ale ne tim zpusobem, ktery ocekavas. Naprogramuj to s knihovni funkci, profiluj, a pak pripadne optimalizuj.

[gld17]

Beru to s rezervou. O vasi schopnosi pochopit moznosti takove knihovny a to nejen v kontextu s moji kopterou, nepochybuji.

Ocividne jste analyzu obrazu nikdy nedelal a nevite, jak dlouho to trva a na cem to vazne.

[stativ]

Ocividne jste analyzu obrazu nikdy nedelal a nevite, jak dlouho to trva a na cem to vazne.

Mě přijde, že vy na tom nejste o moc lépe. Nevím, co konkrétně tam řešíte, ale pokud jde o rychlost výpočtu, tak se spousta věcí dá řešit pomocí lookup tabulek, pro float vstup se pak dá použít lineární interpolace hodnot z tabulky. Ale na samotné sqrt, sin aj. se to skoro určitě nevyplatí, protože HW implementace často nějakou formu LUT používá. Pokud ale výpočet jde sloučit do nějakého black boxu „hodím dovnitř číslo/čísla, vyhodí to výsledek“ a vstup je nějak rozumně omezen, tak je LUT většinou dobrá volba. Tabulka může být i vícerozměrná, ale její velikost je pak mnohem větší a chce si to opravdu dávat pozor na to, jestli její použití kvůli případným cache misses nebude pomalejší než to počítat normálně.

Další věc je, že jít do assembleru se většinou vyplatí jen v případě, kdy se problém dá dobře řešit pomocí SIMD instrukcí, což je k ničemu, protože RPi nemá NEON. Mnohem víc se získá upravením algoritmu (něco různě ošidit a podobně). Třeba u analýzy obrazu se často dá dobře využít časové koherence a počítat jen změny.

[Josef Kufner]

Nepochybuju o tom, ze tvuj kod v assembleru bude radove vykonnejsi, nez knihovni funkce.

Jsem si celkem jist, že tomu bude naopak. Leda by využil specifických podmínek daných konkrétním problémem. Ale to je problém spíš matematický, než programovací. Tady je lepší se zamyslet nad nahrazením pomalých operací něčím jiným – předpočítané tabulky, aproximace polynomem, kešování mezivýsledků, …

Taková předpočítaná tabulka hodnot často používaných vzorečků by mohla hodně pomoct. Pokud má málo významných číslic, je použité množství paměti celkem malé. Například tabulka 11bit int na 16bit int zabere 4KB, což se při troše štěstí vejde do L1 cache.

Další a mnohem zajímavější možností je použít grafický čip k výpočtům. Nevím jak moc Malina podporuje OpenCL, ale možná by jsi mohl aspoň něco implementovat pomocí shaderů.

[Jendа]

Nevím jak moc Malina podporuje OpenCL

Myslím, že vůbec. A i kdyby, tak než se dočká výsledku z OpenCL, tak mu to spadne :) (musí počítat víc věcí paralelně a je tam laaaaaag)

Já myslím, že pokud má problém řídit quadcopteru s takto výkonným procesorem, chyba bude jinde než v pomalém počítání odmocnin a trigonometrie. Jsou i elektroniky s 8bit AVR na 24 MHz a funguje to.

[Jendа]

Aha, už vidím, jde o analýzu obrazu. Zkusil bych to naprogramovat co nejvíc celočíselně.

[stativ]

RPi má hardwarovou FPU. Pokud nebudeš dělat ve svém algoritmu nějaké šílenosti typu bitslicing (to si u floating-point operací nedokážu představit), myslím, že HW FPU nemáš šanci předehnat.

Nevím, jak dlouho trvá na FPU v ARMu běžná operace, ale když to porovnáš s takovýmito šílenostmi, ten shift, odečtení a několik násobení asi vyjde hůř.

[potato]

Rozdíl mezi elementární operací a speciální funkcí na FPU je pořád asi tak řád, takže šílenosti jsou rychlejší, byť zrovna sqrt patří spíš mezi rychlé speciální funkce. Ostatně, vyzkoušej...

[Logik]

Řád? Takže máš na spočítání odmocniny, aby se vůbec vyplatilo ji aproximovat, cca 5 instrukcí....

[Jendа]

Tak floatová odmocnina je u mě 10x pomalejší než ten bitshiftový odhad odkazovaný níže. A inverse square root je 2x pomalejší než ten z Quake (nemám pro to instrukci, dělám vsqrt a vdiv).

[Ivan]

Kdysi davno jsem prochazel knizku (anebo knihovnu) ktera se jmenova nejak jako "Numerical recipies in C++". Tak se daly najit naprosty silenosti, ktery normalni clovek nevymysli. Neco z toho se urcite pouziva jeste dneska.

[lertimir]

Tak to je naprosto jasné. Algoritmizace, numerická matematika a aproximace, má za sebou desítky let vědeckého vývoje. V současnosti je už pokrok na mnoha místech malý, protože u mnoha algoritmů je dokázáno, že lepší konvergence/optimalizace už být nemůže. Mnoho knihoven zůstalo komerčních jako např. FORTRANská knihovna IMSL, kterou jsem používal někdy koncem 80 let. Právě FORTRAN je příklad jazyka, který skoro nic nekontroluje a provádí jen nezbytné operace. Triviální příklad pro algoritmizaci je aproximace funkce. Matematicky zřejmé je to Taylorovým rozvojem. Hodně nezřejmé, ale místo Taylora z nějakého jednoduchého počátku je aproximace po částech s různými počátky a okolími konvergentní mnohem rychleji. Vymyslet se to samozřejmě dá, ale člověk musí mít silný matematický background.

[DaBler]

Pokud potřebuješ odmocninu √x a ne 1/√x, tak doporučuji tento trik:

http://bits.stephan-brumme.com/squareRoot.html

Nezkoušel jsem to na Raspberry Pi, ale na mém Intel Core2 je rychlejší než knihovní funkce sqrtf.

[TrSek]

Hrozne nepresne. Pisou ze +/- 5% ale co jsem testoval ja tak klidne i 12%.

[Jendа]

Přílohy:

• sqrt.png (9838 bytů)
• sqrt2.png (10258 bytů)

Pro malá čísla se to nehodí, pak to ale začne být docela hezké.

[Jendа]

Přílohy:

• sqrt.png (27485 bytů)
• sqrt2.png (26724 bytů)

Napadlo mě, že by nebyl špatný nápad normalizovat to přes velikost výsledku, ne přes to původní číslo . To už vypadá hůř (a realističtěji).

[DaBler]

Pokud jde o přesnost více než o rychlost, můžete k výpočtu odmocniny použít inverzní odmocninu zmíněnou výše:

1.f/Q_rsqrt(x)