0xDEADBEEF

RSS odkazy english edition
««« »»»

Dodatek k bitonic sortu a optimalizaci

15. 8. 2021

Posledně jsem se věnoval velice specifickému případu řazení bitonic sortem. Podíval jsme se na to ještě jednou a ukazuje se, že to jde udělat o něco rychleji. Posledně prezentovaná verze řadila 20 intů v čase 41 ns, aktualizovaná to zvládá za 31 ns.

Zrychlení mají na starosti dvě změny. Jednak konec bitonic sortu, kdy je třeba seřadit 4 vektory po 4 intech, se dá nahradit konstrukcí použitou na začátku - transponovat, seřadit a transponovat zpátky - běží to o něco málo rychleji.

Druhá změna je znepokojivá. Když jsem nahradil funkce, které vracejí dvojici vektorů, za verzi s ref argumenty (nic nevrací, výsledek se promítne do argumentů), program najednou zázračně zrychlil. Není to tak, že by ref argumenty byly nějak magicky mnohem lepší, nejspíš jen jakýmsi nahodilým způsobem interagují s mašinérií kompilátoru a ten ve výsledku vygeneruje efektivnější binárku. Akceleraci nemají na svědomí metodické optimalizace, ale náhoda. Jiný program, i když dělá to samé, vyvolá trochu jiné heuristiky kompilátoru, to má za následek trochu jiný výběr instrukcí, které pak trochu jinak sednou na fyzický hardware. Když jde o nanosekundy, heuristiky a nepatrná rozhodnutí kompilátoru mohou mít gigantický dopad, v tomto případě 30%, a nedají se prakticky kontrolovat. Když jde o jednu specifickou řadící funkci, tak možná, ale i ta se vyskytla ve větším programu. Jak rychle běží v tom kontextu, jako jedna část z mnoha? To nikdy nemůže vědět, dokud se nepodívá.

Ale o tom všem se ví. Někdy stačí maličká změna v programu, doslova jen prohodit pořadí ramen ifu a GCC vyplivne jinak zarovnanou binárku, ta jinak zapadne do cache a všechno je bez většího důvodu drasticky pomalejší. Nebo rychlejší. To je možná horší případ, triviální změna nemá dopad přímo, ale v nahodilé souhře s komponentami kompilátorů a linkerů. Záleží u toho na přesné verzi kompilátoru a všech volbách, které mu nastrkáme, a pochopitelně na hardware. Můžete dosáhnout gigantického zrychlení u sebe na laptopu, ale na serveru s jiným CPU a s mírně odlišnou verzí kompilátoru ty samé změny povedou ke značnému zpomalení. A nikdo se to nedozví, protože to nikdo systematicky neměří.

Jedna verze bitonic sortu s -O2 trvala 33.2 ns a s vyšší úrovní optimalizací -O3 38.9 ns. Proč? Podle manuálu GCC s -O2 optimalizuje agresivně, ale vyhýbá se transformacím, které zrychlení vykoupí zvětšením binárky. Co přesně způsobilo zpomalení, na jaký konkrétní strop narážíme? Někdo to ví, ale já ne. Komplikované důvody heuristik optimalizací a latence a propustnosti instrukcí, počty funkčních jednotek procesoru a rozložení funkcionality mezi nimi. Současná verze je rychlejší, ale jak moc si můžu být jistý, že to bude platit i v ostatních případech a jiných situacích?

Vezměte si třeba některé instrukce (pshufhw, kdybyste chtěli příklad) na starých Sandy Bridge/Ivy Bridge CPU můžou běžet dvě každý takt, ale novější procesory s plnou podporou dvakrát širší AVX2, zvládají jen jednu na takt. Stejná binárka, pokud na těchto operacích stojí, bude na novém HW pomalejší. Zase, při pohledu zvenčí to nedává smysl.

Pointa je v tom, že benchmarkování je těžké a abychom mohli tvrdit něco definitivního, musíme si být vědomi všech omezení. Když někdo řekne tohle je o 20% rychlejší, co tím myslí? Je to rychlejší všude? Nebo jen u něj na laptopu v ten den a v chladné místnosti, kde se mu nepřehřívá procesor a nesnižuje frekvenci o 20%?

Na druhou stranu když je něco 7x rychlejší, pak to asi bude mít svou váhu. Nebo půjde o chybu. To nebo ono.


K tématu:

píše k47 (@kaja47, k47)