Vlákno názorů k článku
LLVM špatně optimalizovalo celočíselné dělení na procesorech AMD
od RDa - Chteli 64-bit architekturu... ale musi pouzivat DIV32, aby...
-
Od Ice Lake je tohle 64bit deleni optimalizovano, viz:
One of the key points here is the 64-bit division throughput, which goes from a 97-cycle latency to an 18-cycle latency, blowing past AMD’s 45-cycle latency.
https://www.anandtech.com/show/14664/testing-intel-ice-lake-10nm/3A kolik ze to generaci 64-bit jader pred ICL bylo za poslednich 21 let, kdy to proste nebylo dulezite resit, hm?
-
Toto je podle mě mnohem lepší přehled:
https://uops.info/html-instr/IDIV_R32.html
https://uops.info/html-instr/IDIV_R64.htmlVýsledek je jasný - 32-bit dělení je vždycky rychlejší.
A jestli něco je důležité řešit nebo ne nechám na jiných. Idiv se v kódu vyskytuje celkem často a třeba Apple dělení v jejich procesorech hodně optimalizoval. Samozřejmě pokud píšu optimalizovaný kód, tak se tomu chci vyhnout, ale jsou případy, kdy to nejde.
-
Libdivide je pouze pro případy, kdy znám dělitele pro mnoho operací. Celkově se ale 64-bit int divide hodně špatně optimalizuje, protože SIMD integer dělení neumí a 64-bit double zase nemá požadovanou přesnost. 32-bit dělení je v pohodě, 64-bit je pain.
Já jsem teda 64-bit int dělení už implementoval 2x pomocí SIMD, a i když se použije AVX-512, tak dělit 8 čísel současně je jen 3x rychlejší než použít IDIV. Je to komplikované a vyžaduje to hodně instrukcí a roundtrip int64 -> double -> int64 + korekce. Nevymyslel jsem to ale, postupoval jsem podle jednoho blogu, co to popisoval.
-
To je sice všechno logické, ale podle mě ti uniká jedna zásadní věc. Když v C++ napíšeš A / B a jedná se o 64-bit dělení, tak tam překladač přidá větev pro 32-bit a 64-bit dělení. Takže se jedná o to, že 32-bit dělení je sice rychlejší, ale bude rychlejší i s tím kódem okolo a skokem na správnou větev? O tom ten "bug" je...
Na X86 to tak zatím je zdá se ve všech případech, ale co třeba Apple Silicon - tam jsou rozdíl 4 cykly, takže tam už může být lepší prostě emitnout jednu instrukci místo té větve - rychlost kódu bude fixní a jedna instrukce je vždycky lepší než 5.
-
To, ze volit ruzne instrukce na zaklade toho, zda ma operand jen 32 platnych bitu nebo vice by melo byt opravdu zalezitosti hardware - tim, ze to bude generovat ruzne mikrooperace, a pak se jen nekde uvede, ze latence zavisi jak velke cislo v danem registru bylo. Pak by nemuselo existovat to nadbytecne vetveni, jakozto snaha o optimalizaci.
Viz treba PCIe - format TLP se lisi od toho, zda se pristupuje na 32bit nebo 64 bit adresu (3DW vs 4DW paket), a pokud vygenerujete 64bit paket s nulama ve vyssim slovu, tak je chovani nedefinovane (zkouseli jsme to v praxi, a od resetu po zatuhnuti systemu, po totalni desynchronizaci a zblazneni pcie IP - jsme videli vsechno mozny :D
10. 5. 2024, 18:34 editováno autorem komentáře
-
Takto ale moderní HW nefunguje.
Dekodér každou instrukci rozděli na uops (mikrooperace), které pokud je to možné jdou do uop cache. Takže když máš třeba cyklus, tak pořád nebudeš ten cyklus dekódovat, ale budeš brát ty mikrooperace z uop cache, ze které se dávají do pipeline.
Když CPU dekóduje instrukci, tak absolutně nemá tušení, jestli dělení bude možné takto optimalizovat, takže prostě jako uop zvolí 64-bit dělení a to taky vykoná.
Dnešní CPU mají mnoho stages a dlouhou pipeline a jsou out of order, není možné takto manipulovat s uops. Toto jde hezky vidět u instrukcí typu gather/scatter, kde vlastně nezáleží na tom, jestli se načte 0 elementů nebo úplně všechny.
-
Ale moznosti to ma.. prece kdyz mas "rep" prefix tak to ma taky zpetnou vazbu podle obsahu podminky nebo pocitadla.
A celkove, pokud jde o moznost urychlit 32bit deleni, tak to mela delat prislusna ALU, aby nemrhala cykly na pocitani s nulama - kdyz to neni jednoducha operace.
Nejspis to nikoho netrapilo, a pak si tvurci prekladacu udelaj nejakou prasackou optimalizaci pro corner case. By me zajimalo co dalsiho se takhle prasi :D
-
Early operation temination se bežně realizuje, není problém takovou logiku zadrátovat do hardware děličky. Má to tak ARM, viz např. Cortex-A57 Software
Optimization Guide:Integer divides are performed using a iterative algorithm and block any subsequent divide operations until complete. Early termination is possible, depending upon the data values.
Instrukce dělení má latenci 4-20 cyklů podle hodnot operandů.
-
Takže ty chceš přidat funkcionalitu, která bude spekulativně (operandy v době dekódování většinou nebudeš znát) dekódovat instrukce, což bude složité a sežere spoustu tranzistorů. Docílíš tím zrychlení v některých případech a dost možná zpomalení v jiných (když se bude dělit pokaždé skutečně 64bit číslo). Výsledná instrukce bude mít v případě načítání operandů z paměti masivně rozdílnou latenci v závislosti na obsahu této paměti - klidně cizího procesu nebo jádra (ve spekulativní větví se to nekontroluje). To dá prostor pro novou a naprosto fascinující třídu síde channel útoků. Gratuluji k skvělému nápadu. Rychle tu diskuzi smažte, než to objeví někdo z Intelu.;-)
-
Neni tam zadne spekulativum, proste operace bude adaptabilni podle argumentu - klidne v pozdejsi fazi (exekuce).
Jde o stejny princip jako kdyz mas treba bit shift (a << b), tak v pripade ze b je vetsi nez 32 ci 64, rovnou vis ze vysledek bude nulovej, protoze vyshiftuje vsechny bity. Nebo mi chces tvrdit ze (a << 4e9) bude trvat 4 miliardy taktu? :D
