Vlákno názorů k článku Použití instrukcí SSE a AVX pro zrychlení bitových operací od mikro - Ocenujem clanok na takuto low-level tematiku, ale popravde,...

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.

Ten tvůj program porušuje strict aliasing rule, nemůžeš do paměti ukládat přes uint64_t pointer a pak to číst jako int16_t pointer, to je undefined behavior, není to korektní kód.

To, že je to undefined behaviour v daném jazyce, neznamená, že je to undefined na cílové/ých architekturách.

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).

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.

Dopsal jsem mu tam ten jeden AND s invertovanou maskou, takže už to počítá totéž a zpomalilo se to zanedbatelně.

Ten UB se dá celkem jednoduše obejít pomoci memcpy().

Třeba:

static inline uint64_t load64_unaligned(const void* src) {
  uint64_t x;
  memcpy(&x, src, sizeof(uint64_t));
  return x;
}

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.

protože FPGA nerozumím
To by nebolo zle sa doucit, pretoze na FPGA urobite aj tu fourierovu transformaciu daleko efektivnejsie ako v strojaku...

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.

Jj, to dava rozum, akurat mi prislo logicke na to pouzit to fpga. A ako som letmo pogooglil, tak zdaleka nie som sam, takze mesiace znovuvyliezania kolesa by nehrozily...