Matrix class - spravnost kodu

[perry]

[VladR]

Ono to dost zavisi od architektury. Napr. na starom Pentiu I, s inou architekturou Execution Units a Cache contention, by to vyzeralo inak a tie lokalne premenne by kludne mohli byt rychlejsie (ale teraz sa mi nechce spatne dohladavat pravidla ich fungovania v manuale).


Samozrejme, najrychlejsi kod si vzdy napises sam, v cistom assembleri, kde mas priamu kontrolu nad tym, co je v registri a co nie.


Kebyze si sa velmi nudil, tak by som to celkom doporucil - stravit s tym jeden den a pozriet co to da oproti beznemu MS compileru.
Plus, spravit SSE verziu. A tam to mas uplne ze najrychlejsie - vsetko v registroch a v jednej instrukcii nahradis mnohopocetne nasobenie/scitanie

[nou]

ked sa budes STRAAAAAASNE nudit tak mozes pouzit toto http://www.agner.org/optimize/

inak preliminary optimization is root of all evil. takze na optimalizacie sa teraz vyser. ked zistis ze to je pomale tak to ries potom. sice povedal by som ze taka zmena O(X^n) na O(n^2) by bola velmi vhodna hned ako to clovek pise.
_________________
Najjednoduchšie chyby sa najtažšie hľadajú.

[VladR]

Agner je fajn, ale predsa len troska prilis hi-level.

Ako vecernu beletriu by som doporucil manual priamo od Intelu:
http://download.intel.com/design/itanium/specupdt/248699.pdf

[rezna]

ja bych rekl ze to extremne hrotite - pokud presel od C# k C++ tak na nejake SSE je znacne brzo ...

[VladR]

To hej, ale myslim ze staci, ked bude mat aspon povedomie o tom, ze take veci existuju a ze aj ten C++ kod je stale de facto prilis hi-level a ze to vonkoncom nie je sranda ani v C++ napisat rychly kod.

Neskor aspon bude vediet co a kde ma hladat.

A to vecerne citanie od intelu nikdy nie je na skodu. Clovek znacne precitne, ked si precita ako vlastne funguje architektura sucasnych procesorov.

Naposledy som nieco take robil s 8088 CPU a odvtedy sa zaber CPU znacne rozsiril a aj mna mnohe veci v tom Intelovskom manuale prekvapili, ze ako to vlastne teraz funguje.
Clovek sa potom na kod pozera uplne inak...


Mne bezny C++ kod teraz pripada ako Karel, alebo LOGO...

[Vilem Otte]

Proč vektoizovat kód?

V drtivé většině případů NENÍ potřeba kód vůbec vektorizovat, vektorizace přinese spousty problémů a skalární operace se zpomalí (XMM registry nejsou vhodné pro práci s jediným číslem, na to je tad FPU), a horizontální operace (skalární součiny například) se zpomalí hodně (zkuste si napsat jednoduchý FPU dot product a SSE2 dot product a SSE4 dot product přes dpps instrukci - zjistíte, že pokud dokážete napsat dobrý FPU kód, tak SSE2 bude pomalejší a SSE4 jen velmi nepatrně rychlejší, ale následné uložení do float čísla z 128-wide registru to zpomalí a na většině CPU může FPU časově i zvítězit).

V 90 procentech zbylých případů je za vás dostatečně schopný provést vektorizaci do SSE kompilér (často ji nenapíšete o moc lépe - obvykle spíše hůře) ... samozřejmě mám na mysli reálný kompilér, ne MSVC - nové GCC je narozdíl od předchůdců na vektorizaci vynikající, ICC je nejlepší (a jeho černá magie ).
Navíc používání inline ASM v MSVC je overkill (napsání __asm je velmi drahá záležitost co se výkonu týče).

Ve zbylé části se jedná především o funkce, kde vektorizujeme cyklus (2x2 sse-packet traversal při ray tracingu - ovšem tady je další problém, nebudu rozvádět; násobení matice x pole bodů; apod.). Tady to smysl MÁ, ale musíte mít dobré structy (SoA raději než AoS), dobře napsané a postavené pointery (a už tady máme problém 32-bit vs. 64-bit aplikace), a tedy včas a dobře prefetchovat data v cachích (protože pokud to nemáte, dojde ke cache miss - což vektorizovaný cyklus výkonově zabije).

Takže abych to shrnul, dokud nevíte něco hlubšího o kompilérech a o procesorech - nemá se smysl o SSE bavit, natož v něm něco psát. Většinou jej stejně potřebovat nebudete, a když jo, tak to většinou skončí u compiler flagu -mssex ... za x doplňte odpovídající číslo.

Pozn. Pokud nevite co je SoA, AoS, FPU, SIMD, cachovací linka, cache miss, a další pojmy - nemá smysl s SSE začínat, máte na to ještě čas.

Proč SSE?!

Je standard, ale nové AVX vypadá slibněji (8-wide SIMD ... nicméně Core quad-core i7 s SSE výkonově převálcuje Sandy Bridge i5 s AVX ... a za podobnou cenu se dají sehnat jak Sandy Bridge i5, tak quad-core i7. Uvidím jak dopadne Bulldozer), i když mě nepřijde zrovna nejlepší, mnohem lepší mi přijde 16-wide SIMD (plánován u zrušeného Larabee - nevím jak to je u Knights Ferry?), protože do něj nacpete celou matici.

Nicméně, pokud potřebujete něco velmi paralelizovat a urychlovat - docela byste si měli vystačit třeba se 4 jádry a kompilérově vektorizovaným kódem. Pokud potřebujete počítat ještě rychleji, tak buď uvažujte o slušné GPU a OpenCL (nebo GPGPU), nebo 12-core Operton (pokud máte dostatek financí), případně 2x12-core na deskách pro něj.

EDIT:

[frca]

[Marek]

Co je špatného na #pragma once? Umí to VC++ i GCC (defaultně) a teoreticky to může trochu urychlit kompilaci.

Podle mě tady řešíte moc pokročilé věci a hlavně už je to off-topic. Autor vlákna tvrdí, že je začátečník. Takže mu radím, aby tady tu pokročilejší diskuzi radši ignoroval, prozatím.

Vilem Otte> Podle mě všechny compilery nahrazují lokální proměnné registrem, pokud to jde. Říká se tomu alokace registrů a dělá se to všude, protože to má brutální vliv na výkon. Vypnutá alokace registrů v compileru může způsobit, že se vygeneruje i 5x pomalejší kód. Funguje to tak, že se všem lokálním proměnným přiřadí registry (čísla) a provede se přejmenování všech registrů tak, aby jich bylo co nejmíň, ale aby kód dělal furt to samé. Pokud těch registrů bude mít víc, než se vejde do procesoru, hodí některé z nich do paměti. Kód, co používá 50 proměnných, si klidně může vystačit i s 6 registry a žádnou pamětí. Závisí to na tom, co ten kód dělá.

S alokací registrů je ale několik problémů:
1) Je to NP-complete, v praxi compiler nikdy neudělá perfektní kód.
2) Pokud procesor neumí indexovat registry, musí compiler všechny pole indexované nekonstantou hodit do paměti (to je odpověď na otázku, proč pole mohou být pomalejší, když se např. nerozvine cyklus, který nad ním iteruje).
3) Přejmenování registrů může způsobit, že některé optimalizace nebude možno provést (např. může úplně znemožnit automatickou vektorizaci). Naopak některé optimalizace mohou kód transformovat tak, že alokace registrů dopadne o dost hůř (vyrobí víc registrů). Tzn. špatně zvolené pořadí optimalizací v compileru může kód i zpomalit. Je to docela magie někdy.
_________________
AMD Open Source Graphics Driver Developer

[Tringi]

[perry]

Co jsem o templates četl, tak jsem je pochopil jako "typově kontrolované #define", navíc od C# se tvoří při překladu, takže v runtimu by nemělo použití template nic brzdit (na rozdíl od genericity v .NET).

[nou]

no hlavne lokalne premenne su na stacku. a ako vieme tak stack je jedna oblast pamete ktora sa neustale znovu pouziva. takze je velmi pravdepodobne ze bude v L1/2 cache. co sa o heap neda povedat.

inak gcc ma optimalizaciu ze ak je na zaciatku klasicky guard #ifndef BLA #define BLA tak preskakuje cely subor. http://gcc.gnu.org/onlinedocs/cppinternals/Guard-Macros.html
_________________
Najjednoduchšie chyby sa najtažšie hľadajú.

[perry]

Přepsáno na pole a OK... akorát co jsem zkoušel, tak operace s polem přes for jsou pomalejší (vnitřní cyklus mění druhý index) , než přímo vypsat natvrdo kód [0][0], [0][1] atd

----

[Vilem Otte]

[nou]