Přesně, z nadpisu jsem se vyděsil, že ten kód pak špatně dělil, což by byl daleko větší průšvih. A říkal jsem si, jak se jim to povedlo. Naštěstí se po přečtení ukázalo, že to neoptimalizovalo špatně, ale vůbec.
A víš o nějaké 64-bit architektuře (nebo i mikroarchitektuře), která má stejnou latenci pro 32-bit a 64-bit dělení?
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/3
A 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.html
Vý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.
Pokud ale hodne delite, tak spis pouzijete SIMD s/bez libdivide napr.
Pochybuji ze existuje obecny kod, ktery bude pomalej prave kvuli deleni - ty latence vykryji jine instrukce.
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.
Že bude 64bit varianta pomalejší než 32bit snad není tak překvapivé. A že je optimalní ji použít, když stačí, taky každý pochopí. To, že mám na podnikání dodávku taky neznamená, že nepoužiju osobák pro přivezení nákupu pro rodinu.
10. 5. 2024, 11:18 editováno autorem komentáře
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.
Pokud tam pridava prekladac vetev podle velikosti operandu (delitele), tak to je idealni ukol pro ucode update prece - tj. provede se podle (B>>32) ? div64 : div32
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
REP operace se rozbije na cyklus a je na to snad několik "flagů" v CPUID, které popisují, jak drahé to celé je... Dělení je ale úplně o něčem jiném a nedokážu si to představit.
Mám pocit, že sice máš "nápady", které ale nejsou realizovatelné.
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
Ne, SHL/SHR bere jen 3, 4, 5, nebo 6 bitů v závislosti na velikosti operace. Proto např. `A << B` kde B je 64 bude výsledek A (na x86).
ARM to má trochu jinak a myslím, že když B >= sizeof(A)*8 tak výsledek bude 0, což mi přijde logičtější.
11. 5. 2024, 14:56 editováno autorem komentáře
Tak hlavne toto je naprosto okrajova zalezitost a prisel na to nejspis nekdo kdo ladi preklad pro konkretni procesor. 99% uzivatelu se to vubec netyka.