Ocenujem clanok na takuto low-level tematiku, ale popravde, robi viac skody nez osohu.
Ano, je skvele, ze dnesne procesory maju plno sikovnych instrukcii. Ale co tak si spomenut, ze prvy krok sa vola optimalizacia algoritmu?
Dal som tomu 15 minut svojho casu:
for (int i = 0; i < SAMPLES*4; i += 4) {
uint64_t* raw = (uint64_t*)&inbuf[i + 0];
uint64_t mask = (*raw >> 1) & 0x1000100010001000;
*raw |= mask;
const int i2 = i >> 1;
outbuf1[i2] = (float)inbuf[i + 0];
outbuf1[i2 + 1] = (float)inbuf[i + 1];
outbuf2[i2] = (float)inbuf[i + 2];
outbuf2[i2 + 1] = (float)inbuf[i + 3];
}
Ako vidno, absolutne som sa nesnazil to optimalizovat na registre ci davat kompilatoru nejake hinty a vysledok je takmer 2x rychlejsi kod.
Nemozem uverit, ze autor radsej vyzaduje najnovsiu generaciu procesorov, ktore mu usporiadaju 4 16-bitove slova do jedneho miesto toho, aby si to napisal sam.
Nehovoriac o tom, ze ak by si autor ten bit #12 (to cislovanie 1az 13 v clanku je dost... nestandardne) dal na trochu vhodnejsie miesto (cize predpripravil data vo vhodnejsom formate), tak to otvara dvere dalsim optimalizaciam.
Bez jedinej SSE instrukcie by sa ta slucka dala urychlit 3x - 4x.
Tohle s architekturou nesouvisí. C++ překladač nemusí invalidovat data v registrech (načítat je znovu), pokud se do paměti ukládá přes pointer jiného typu. Je to optimalizace. Uvedený program tohle porušuje, ukládá do paměti int64 hodnotu a potom ze stejného místa čte int16 hodnotu. Překladač ale z paměti int16 hodnotu nemusí načíst, protože strict aliasing rule říká, že se nesmí aliasovat pointery různého typu.
Musí, protože dřív to (na dané architektuře a kompilátoru) fungovalo a staré kódy s tím počítají. Warning/error na stric aliasing si nastavuješ, abys odhalil dopředu problémy, kdybys chtěl portovat na jinou architekturu (např. na MIPS v grafické stanici SGI nefungoval a chvíli jsem se trápil, proč ten kód dělá nesmysl).
Strict aliasing rule je součástí C++ standardu myslím od verze 11. Od té doby standard zakazuje aliasing pointerů různého typu a programy, které tohle používají (a dřív fungovaly), najednou fungovat nemusí, protože je to undefined behavior. Gcc někdy řekne warning při překladu, ale ne vždy, heuristiky v kompilátoru nejsou schopny odhalit všechna porušení strict aliasingu. S architekturou to nemá nic společného.
Asi nerozumím? Jak souvisí strict aliasing s architekturou? Podle C++ standardu je porušení strict aliasing rule undefined behavior. To znamená, že program může dělat cokoliv. Může i náhodou správně fungovat a může i náhodou správně fungovat na nějaké konkrétní architektuře. To ale neznamená, že je takový program korektní. Není. Když se takový program přeloží jiným překladačem nebo na jiné architektuře, tak fungovat nemusí a není to problém ani překladače ani architektury. Je to problém toho programu, protože je v něm undefined behavior.
Takhle teoreticky svět ale nefunguje. Ten behavior byl v minulosti experimentálně ověřen, takže ho musí překladač dodržovat, jinak by ztratil kompatibilitu s dřívějšími kódy, které na něj spoléhají. Ale na jiné architektuře ten aliasing nemusí fungovat, což ale nevadí, protože tam nefungoval nikdy, tedy opět není problém s kompatibilitou se starými kódy (pro danou architekturu). Autoři překladače (na obou architekturách použit ten samý) to obhájí - jak upozorňujete - že je to v C/C++ undefined behavior, takže obojí chování je správné.
Kompatibilita s dřívějšími kódy se ztratila změnou C++ standardu. Ve chvíli, kdy se do C++ standardu zavedl strict aliasing, tak se do všech dříve korektních programů, které používaly aliasing pointerů různého typu, zavedlo undefined behavior.
Tohle se vědělo a udělalo se to záměrně, protože strict aliasing umožňuje překladači lépe optimalizovat kód a překladače to využívají, aby byl výsledný kód rychlejší.
Takže tvůj předpoklad, že překladač musí dodržovat kompatibilitu s dřívejšími kódy, není správný. Překladač musí dodržovat kompatibilitu pouze s C++ standardem.
Ten behavior byl v minulosti experimentálně ověřen, takže ho musí překladač dodržovat, jinak by ztratil kompatibilitu s dřívějšími kódy, které na něj spoléhají.
Právě že nemusí. Novější verze gcc často využívají toho, že je něco specifikováno jako UB, k hodně divokým optimalizacím a občas v takovém případě doslova "udělají cokoli". Ani na zdánlivě logické "obojí je správně" se spoléhat nedá. V případě strict aliasingu naštěstí lze "staré" chování překladači nařídit, protože třeba v jádře by se jinak některé low level věci dělaly dost těžko a hlavně dost neefektivně. Ale v jiných případech už to nejednou zaskřípalo a argumenty jako "to dá přece rozum" nebo "takhle se to chovalo vždycky" na vývojáře gcc většinou moc neplatí.
Je to tak. Preto ta poznamka, ze som tomu nevenoval viac usilia, bolo to len na demonstraciu, ze dokonca aj pri manipulacii s pamatou je ten algoritmus rychlejsi len s minimalnymi upravami.
Pointa toho prikladu je, ze keby sa autor trochu zamyslel miesto prehladavania intelackych tabuliek s instrukciami, tak moze mat zadanie napisane "vektorovo" aj v plain C-cku na obycajnej 64-bitovej architekture zpred 10 rokov.
23. 11. 2022, 13:18 editováno autorem komentáře
Ten tvůj program má dvě chyby, dělá něco jiného a je v něm undefined behavior.
Děláš tam OR do metadat bitu, ale ten bit předtím nevynuluješ, takže to nefunguje správně.
Pointa je, že nemá smysl srovnávat výkon korektní implementace a tvé implementace, která dělá něco jiného a ještě s undefined behavior.
> Děláš tam OR do metadat bitu, ale ten bit předtím nevynuluješ, takže to nefunguje správně.
Safra, to jsem pěkně rozbil testy. Nechtěl jsem do gitu commitovat velký soubor z /dev/urandom na kterém jsem to testoval, ani se mi nechtělo shánět deterministický RNG co bych tam dal (vím že v Pythonu můžu nastavit seed, ale nevěřím tomu, že to vygeneruje stejné věci napříč verzemi), tak mě napadl ten hack "uděláme nějaký 'seq' a to použijeme jako data". Jenže co čert nechtěl, zrovna v ASCII hodnotách výstupu není ten klíčový bit nastaven, takže testujeme jenom že se to správně přioruje, ale ne že se vymaže pokud nastaven je.
Nápady na deterministický RNG pro generování testovacích binárních dat? Změnil jsem to na samodomo věc co opakovaně počítá MD5 a vypisuje výsledek.
Díky, přidal jsem to do testovacího programu.
i7-9700TE, GCC 10 (z Debianu stable): numpy 163us, naivní 294us, ručně unroll 92us*, tvoje 73us, moje SSE 31us, moje AVX 24us.
* tohle je zajímavé, protože ve standalone testovacím programu (co je na githubu) ruční unroll pomohl hodně, ale v celém tom zpracování vůbec. IMHO se nějak blbě zpropagovaly restrict nebo další kvalifikátory a ve standalone se to podařilo optimalizovat. Ale výsledný kód se mi asi teď úplně zkoumat nechce.
Strict aliasing se dá řešit pomocí unions těch datových typů, ne?
A ještě k tomuhle:
> Nemozem uverit, ze autor radsej vyzaduje najnovsiu generaciu procesorov
Ve skutečnosti použitá SSE umí snad všechny procesory vydané po roce ~2008 a na ničem jiném fakt nepoběžíme, pokud teda nepřejdeme na nějaký M1 nebo tak něco :)
> Nehovoriac o tom, ze ak by si autor ten bit #12 (to cislovanie 1az 13 v clanku je dost... nestandardne) dal na trochu vhodnejsie miesto (cize predpripravil data vo vhodnejsom formate), tak to otvara dvere dalsim optimalizaciam.
To by vyžadovalo trochu větší hackování FPGA kódu v bladeRF, což je pro mě komplikované, protože FPGA nerozumím. A nevím moc jak by to pomohlo -- řekněme že bych to dal do nejvyššího bitu, furt musím udělat v podstatě totéž, vymaskovat a nahradit.
Ono se to FFT zvládá, výhodu ve zpracování přímo ve FPGA bych viděl spíš v tom, že by se obešel bottleneck propojení s počítačem -- aktuálně je to 20 MS/s * 4 bajty na vzorek * MIMO2x2 = 160 MB/s pro každý směr (RX a TX) což už se blíží tomu co dá USB 3.0 a přitom ta data obsahují podstatně méně informace, většina z toho jsou „nuly“, resp. oversampling. Navíc by to mohlo přímo posílat balíčky otagované azimutem, takže bych nemusel řešit to lepení metadat do nejvyšších bitů o kterém je článek.
Velikou nevýhodou pak ale je, že tohle bylo nabastlené za chvilku, zatímco to FPGA by klidně mohlo být několik měsíců práce - a já samozřejmě nemůžu řešit jenom tohle, protože tak nějak stavím celý radar (teď už samozřejmě ve víc lidech, ale stejně). Právě to, že jsme na rozdíl od konkurenčních firem použili jako jediní v podstatě nemodifikované hotové SDR nám nejspíš umožnilo vyrobit radar s omezenými prostředky v rekordním čase. Dále, hrábnout do mého C/Python kódu může kdokoli z týmu nebo i zákazníků (když si to třeba koupí research tým na univerzitě a chce si něco vyzkoušet), zatímco FPGA rozumí málokdo a dělat tam nějaké úpravy je peklo. Poslední myšlenka pak je, že my nevíme, jestli třeba nenajdeme nějaký lepší způsob filtrace/zpracování signálu - a opět, v kódu na počítači se to snadno vyzkouší a změní.
Ještě doplním jeden problém: když se zjistí že bladeRF / to FPGA co se v něm používá nejde koupit (to se teď stává doslova se vším a není výjimkou číst zprávy o tom že to zastavilo třeba celou ohromnou automobilku; od ostatních výrobců radarů slyšíme přesně totéž) a musím použít jiné rádio (což bude znamenat jinou řadu a třeba i jiného výrobce FPGA (Intel / Xilinx)), tak mě čeká velmi komplikovaná portace. Software oproti tomu běží všude.
Totéž pokud se zjistí že bladeRF nevyhovuje a je potřeba něco jiného.
Taktiez ma napada, optimalizacia na urovni kodu zvedsa nestaci pri tako vysokych bit rate. Ten procesor musi komunikovat s okolim, jadra budu zdielat IO s dalsimi procesmi, procesy tak isto budu zdielat pamat, cache. Takze je realna sanca ze niektore istrukcie budu trvat v reali dlhsie. Rovnako dalsie casti procesoru su zdielane medzi jadrami.
Vo vysledku zistite ze pocet taktov ktore mate k dispozicii nie je umerny taktu jadra a periodou prichadzajucich dat. Bude o mnoho nizsia. Napriklad toto neplatilo ani u osembitov. Priklad ZXS, ked ULA potrebovala pristup do videopamate tak procesoru poslala proste signal na HALT pin, ostatne tiez nemali dvojportovu pamat.