.[ ČeskéHry.cz ].
Optimalizace asm

 
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> C / C++
Zobrazit předchozí téma :: Zobrazit následující téma  
Autor Zpráva
frca



Založen: 28. 07. 2007
Příspěvky: 1487

PříspěvekZaslal: 23. listopad 2021, 17:18:36    Předmět: Optimalizace asm Odpovědět s citátem

Zkouším optimalizovat voxel algoritmus a nabyl jsem podezření, že nejpomalejší je přístup do velkého kusu paměti (2 MB).
Vytvoři jsem minimální example:
https://www.franticware.com/files/dosbench/main.cpp
V assembleru to je:
https://www.franticware.com/files/dosbench/main.s

Tato část trvá asi 175 cyklů 486DX2 66 MHz, což mi přijde nějak moc:
kód:
L6:
# main.cpp:41:             int32_t index = rand() & (dataCount - 1);
   call   _rand   #
# main.cpp:41:             int32_t index = rand() & (dataCount - 1);
   andl   $1048575, %eax   #, index
# main.cpp:42:             sum ^= data[index];
   movw   _data(%eax,%eax), %cx   # data,
   xorl   %ecx, %ebx   #, sum
# main.cpp:39:         for (int i = benchSize; i != 0; --i)
   decl   %edi   # i
   jne   L6   #,


Pokud by to skutečně byl ten
kód:
   movw   _data(%eax,%eax), %cx   # data,

, dalo by se to nějak zrychlit?
Díky.
_________________
www.FRANTICWARE.com
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
OndraSej



Založen: 28. 07. 2007
Příspěvky: 765
Bydliště: Brandýs nad Labem

PříspěvekZaslal: 23. listopad 2021, 21:23:20    Předmět: Odpovědět s citátem

S cache 8 kB, nebo kolik to má, bude ten náhodný přístup do paměti zabiják.

Ale 175 cyklů mi přijde taky trochu moc. Zkoušel jsi, kolik stojí ten rand(), případně ho nahradit konstantou, inkrementem a případně inkrementem s modulem (udělaným přes andl)?

Edit: podle této přiručky, strana 805 by rozdíl mezi cache hit a cache miss měl být cca 2 cykly, takže těch 175 je fakt hodně.
_________________
http://trionteam.net


Naposledy upravil OndraSej dne 23. listopad 2021, 22:12:23, celkově upraveno 1 krát
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
mar



Založen: 16. 06. 2012
Příspěvky: 569

PříspěvekZaslal: 23. listopad 2021, 22:11:46    Předmět: Re: Optimalizace asm Odpovědět s citátem

pokud jde o samplování heightmapy/textury s barvami a je to opravdu o memory accessu, kolik mají ty textury - 1kx1k?

pokud to je ten access, tak bys měl vidět silný propad výkonu při otočení kamery o 90 stupňů

tak buď zkusit menší texturu nebo pokud je k dispozici dost paměti,

tak mě ještě napadlo udělat si transponované verze textur (ale 2 extra MB na 486ce asi nebude úplně cool)

počítám že ten fetch je zarás 8-bit heightmapa a 8-bit barva

a pak použít tu nebo onu podle toho, jaký je access pattern,

tzn. pokud |stepy| > |stepx|, swapnout a použít transponované textury, worst case 45 stupňů to ale nevyřeší

ještě mě napadla další věc - nejstarší trik v historii - co takhle zkusit mipmapy? určitě se to bude vařit vzadu, kde se tak jako tak sampluje v podstatě v dost random částech té textury

mimapy pro heightmapu budou triviální, pro barvy to bude kvůli paletě trochu složitější, ale dá se udělat třeba perceptual fit, tzn. vážit error podle barev - myslím 0.3*red, 0.59*green a 0.11*blue

ještě by se pak dal k tomu zkusit třeba tiling těch textur, ale to nevím, jestli už není na 486ku moc hardcore a jestli by se to neuvařilo na dekódování indexů, něco jako třeba uložit to blokově a řekněme 4x4 texely by byly blízko v paměti, něco takového
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
frca



Založen: 28. 07. 2007
Příspěvky: 1487

PříspěvekZaslal: 24. listopad 2021, 00:31:34    Předmět: Odpovědět s citátem

Zajímavé nápady; v původním examplu nejvíc opravdu žral ten rand(). Budu zkoumat a experimentovat dál.
_________________
www.FRANTICWARE.com
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
mar



Založen: 16. 06. 2012
Příspěvky: 569

PříspěvekZaslal: 24. listopad 2021, 17:11:10    Předmět: Odpovědět s citátem

no pokud cache miss trvá na 486ce 2 cykly a mov jeden, jak psal ondrasej, pak určitě cache missy nejsou důvod, proč to běží jak se ti zdá pomalu a žádný z těch nápadů stejně v ničem nepomůže
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
OndraSej



Založen: 28. 07. 2007
Příspěvky: 765
Bydliště: Brandýs nad Labem

PříspěvekZaslal: 24. listopad 2021, 18:03:39    Předmět: Odpovědět s citátem

No jo, to bývaly ty zlaté časy, kdy paměť běžela na podobné frekvenci jako procesor a cykly byly tak dlouhé, že round-trip do paměti a zpět proběhl skoro okamžitě Smile

frca: máš někde ten skutečný kód, co optimalizuješ? Jinak v té dobové příručce, co jsem odkazoval, je tabulka latencí většiny instrukcí, takže by nemělo být až tak těžké dopočítat, co tam trvá dlouho.
_________________
http://trionteam.net
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
frca



Založen: 28. 07. 2007
Příspěvky: 1487

PříspěvekZaslal: 25. listopad 2021, 00:53:49    Předmět: Odpovědět s citátem

Kód mám teď rozkopaný, ale mezitím jsem přemýšlel, jestli je nějaká výhoda mít lokální proměnné na stacku vs. statické (v datovém segmentu). Zatím jsem neměl čas to zkoušet.
_________________
www.FRANTICWARE.com
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
frca



Založen: 28. 07. 2007
Příspěvky: 1487

PříspěvekZaslal: 26. listopad 2021, 19:26:15    Předmět: Odpovědět s citátem

Zkoušel jsem všelicos, ale výsledek stále víceméně stejný. Funkce vykresluje jeden řádek voxelů v konstantní vzdálenosti. Assembler je výsledkem kompilace s -O2:

https://franticware.com/files/rcross_opt/cpurenderasm.cpp
https://franticware.com/files/rcross_opt/cpurenderasm.s
_________________
www.FRANTICWARE.com
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
mar



Založen: 16. 06. 2012
Příspěvky: 569

PříspěvekZaslal: 27. listopad 2021, 09:52:16    Předmět: Odpovědět s citátem

frca napsal:
Zkoušel jsem všelicos, ale výsledek stále víceméně stejný. Funkce vykresluje jeden řádek voxelů v konstantní vzdálenosti. Assembler je výsledkem kompilace s -O2:

https://franticware.com/files/rcross_opt/cpurenderasm.cpp
https://franticware.com/files/rcross_opt/cpurenderasm.s

myslím, že bude asi potřeba do toho zahrábnout i na vyšší úrovni trochu.
proč nezkusit half-res x? okamžitě 2x rychlejší, i když to nebude tak pěkné

jinak ten clamp se mi moc nelíbí (ani vizuálně) - proč to neudělat tak, že se jenom obarví okraj na fixní barvu? pak ten check může být jednodušší a dělat se až když projde ybuffer test (x|y) & -1024 => color 0 nebo tak něco
tzn výškově by se terén opakoval, ale ušetříš tím uvnitř té loopy v hot pathu

případně by se ten test dal posunout ven a nakrájeto nebo prostě jenom udělat test, že pokud rozsah koncových bodů je uvnitř textury, tak se použije specializovaná fce/templáta, kde se ten clamp vůbec nemusí řešit, což by měla být většina případů

EDIT: ještě ten rounding bias (+0.5) by se dal vytáhnout mimo loopu, ale v assembly koukám, že to už udělal compiler za tebe Wink

ještě jedna věc mě napadla - pokud by se to vůbec vyplatilo - možná by se dalo specializovat i pro blízké řádky a v incrementu otestovat, jestli se nezmění hi part uvček,
ze které se sampluje - třeba ve smyčce - a takhle naakumulovat třeba x pixelů a ty pak flushnout v té loopě, co renderuje ten vertikální sloupec
tím by se to zkomplikovalo, takže nevím, jestli by se to vůbec vyplatilo - ale minimálně by se tím dalo vyhnout extra samplování té heightmapy+barvy za cenu minimální extra logiky

ještě by se dala ta myšlenka rozvést tak, že by se ta loopa dala splitnout - v první části by se provedl uv krok a výsledný index, odkud samplovat,
by se uložil do lokálního pole. zároveň by se dalo pak udělat jednoduché RLE za běhu
tzn. třeba pole shortů a prokládat indexy odkud samplovat a kolik pixelů je stejných - to by mohla být varianta pro blízké řady,
kde absolutní krok je menší, než jeden texel, něco takového...
vlastně by se tam mohlo i rovnou samplovat a ukládat do toho pole výšku a barvu, to už je ale naprostý detail

hmm, teď jsem si ještě uvědomil, že to nebude tak jednoduché, protože v rámci běhu stejného texelu je stejně potřeba ještě testovat y-buffer, ale i tak by se s tím možná dalo něco vymáčknout...
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu
frca



Založen: 28. 07. 2007
Příspěvky: 1487

PříspěvekZaslal: 27. listopad 2021, 13:02:24    Předmět: Odpovědět s citátem

Díky za super nápady, hlavně s tím clampem a verzí funkce bez něj. To bude poměrně snadné.

Half-res je taky možnost, hlavně blízko kamery, kde jsou voxely beztak velké přes x pixelů.


Co mi vrtá hlavou: Nejsou 32-bit operace rychlejší než 8-bit? Že bych si vytvořil 32-bit framebuffer, pracoval nad ním a pak zkopíroval každý čtvrtý bajt, na to bude určitě nějaká instrukce Wink

PS: Druhou půlku jsem nepochopil, přečtu si ji znova zítra Laughing

PS2: Optimalizaci clampu mám hotovou, testuju počáteční a koncové iCoordX, iCoordY a pokud všechno spadne do 0-1023, volám rychlou verzi bez clampu. Pokud hráč jede po trati a nedělá kraviny, tak se verze s clampem vůbec nezavolá.
Druhá věc je, že se neudálo žádné znatelné zrychlení. Pořád to zarytě jede 17-18 fps.

PS3: Pixel doubling přinesl zrychlení na asi 23 fps. Použil jsem ho jen blízko kamery, kde to je pixelované tak jako tak.
_________________
www.FRANTICWARE.com
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
frca



Založen: 28. 07. 2007
Příspěvky: 1487

PříspěvekZaslal: 2. prosinec 2021, 16:49:35    Předmět: Odpovědět s citátem

V další verzi plánuji 3 úrovně detailu:


Pixel doubling je jen u části obrazu při nastavených detailech na úroveň 0. Pak se to liší hlavně počtem z-sliců. Nejvíce se rozdíl projevuje v pohybu, kdy je vidět alias hlavně u výraznějších terénních nerovností.
_________________
www.FRANTICWARE.com
Návrat nahoru
Zobrazit informace o autorovi Odeslat soukromou zprávu Zobrazit autorovi WWW stránky
Zobrazit příspěvky z předchozích:   
odeslat nové téma   Odpovědět na téma    Obsah fóra České-Hry.cz -> C / C++ Časy uváděny v GMT + 1 hodina
Strana 1 z 1

 
Přejdi na:  
Nemůžete odesílat nové téma do tohoto fóra
Nemůžete odpovídat na témata v tomto fóru
Nemůžete upravovat své příspěvky v tomto fóru
Nemůžete mazat své příspěvky v tomto fóru
Nemůžete hlasovat v tomto fóru


Powered by phpBB © 2001, 2005 phpBB Group


Vzhled udelal powermac
Styl "vykraden" z phpBB stylu MonkiDream - upraveno by rezna