Test: paměti mají čtyřistakrát delší latenci než procesory

Z výsledků je dále patrné, že procesory Intel Xeon mají lepší správu paměti cache než AMD Opteron. Ta se projeví v případě, že přes CPU „teče“ hodně dat, která budou potřeba jen jednou (například při kódování videa). Nakonec si neodpustím několik úplně zbytečných programátorských rad, které však používám už řadu let a věřte, že se mi plně osvědčují.

Úvod

Kdysi dávno se výkon procesoru hodnotil podle rychlosti jeho hodin. Když se přišlo na to, že je to hloupost, začaly se pomocí drystone&whetstone testu měřit MIPSy a MFLOPSy. Pak ale vyšlo najevo, že v praktických programech MIPSově pomalejší počítač mnohdy předhoní MIPSově rychlejší. Od té doby se používají „aplikační testy“, tedy například kolik dosáhne FPS při animování hry Quake (toto, po přepočtu na frekvenci Intelu P4, používala firma AMD pro číselné značení Athlonu), jak dlouho trvá zazipování a rozbalení nějakého souboru a další podobné testy. Tato metoda měření má nesporné výhody pro běžné uživatele. Na konkrétních příkladech jim ukazuje, jak dlouho co trvá. Také do jistě míry potlačuje nesprávnou odpověď „4GB“ na otázku „Jak rychlej máš procesor?“.

Když ale programuji, tak mě zajímá, jak dlouho různé operace trvají, abych mohl program udělat co nejrychlejší. Částečně se to dá zjistit z datasheetu procesoru, ale na opravdovou výkonnost počítače má vliv ještě chipset a paměti, a proto jsem napsal program, který tuto rychlost zkusí přibližně změřit. Nicméně měření jednotlivých instrukcí je třeba brát pouze jako orientační. Při optimalizaci je nakonec nejlepší měřit přímo program, který píšeme. Na druhou stranu, jeho celková architektura má vliv na rychlost mnohdy větší než všechny pozdější optimalizace dohromady. A pro její volbu se už vyplatí znát špičkové výkony ve sčítání, násobení a přesouvání dat z paměti, které si dále ukážeme.

Jak měřit dobu provádění instrukce

Dnešní procesory jsou jednak pipelinované a za druhé superskalární. To první znamená, že instrukce prochází „výrobní linkou“ s několika „odděleními“. První oddělení načítá instrukci, další ji dekóduje, další provádí a poslední zapisuje výsledky do paměti (například; v PC procesorech je to mnohem složitější).

V ideálním případě, kdy další instrukce nemusí čekat na výsledek předchozí, jsou takto rozpracovány čtyři instrukce a každý takt je jedna dokončena. Superskalárnost znamená, že je takových výrobních linek několik. Například dnes běžně máme v procesoru tři sčítačky. Tak je možné, aby procesor za jeden takt dokončil tři instrukce. Schopnosti procesoru pro různé instrukce pak udávají následující dvě čísla:

Latency je čas, za jaký bude k dispozici výsledek, od doby, co instrukce načetla operandy, měřený v počtu taktů. V jednoduchých případech odpovídá délce pipeline zkrácené o načítací a dekódovací část.

Repeat Rate, někdy též zvaný Throughput. Říká, kolik taktů průměrně uplyne, než mohu spustit tutéž instrukci znovu (s jinými daty). Když například pracují všechny tři sčítačky zároveň, dostávám repeat_rate 1/3.

Když kompilátor optimalizuje nějaký program, měl by ideálně vědět víc než jen tato dvě čísla. Ve skutečném procesoru jsou některé jednotky sdílené (dekodér instrukcí) a může se stát, že i když třeba máme ještě volnou sčítačku, dekodér, který u většiny CPU dokáže dodávat maximálně tři instrukce za takt, je již zahlcen. Rozhodnout, jak rychle se pak co bude provádět, je bez přesného popisu CPU velmi těžké (jelikož kromě superskalárnosti je zde ještě out-of-order execution, což znamená, že nezávislé instrukce můžou být přeházeny ještě dřív, než se dostanou do pipeline).

Pro naše účely však postačí, když určíme špičkovou výkonnost procesoru pro některé často používané operace. Proto ho necháme provádět dlouhé bloky stejných instrukcí a budeme měřit čas pomocí instrukce RDTSC (která přečte z čítače uvnitř procesoru počet taktů hodin od zapnutí počítače). Latence se měří pomocí řady závislých instrukcí, například:

    add $1,%eax
    add $1,%eax
    add $1,%eax
    add $1,%eax
        ....

Takových instrukcí je sto, pak je skok na začátek, opakujeme pětsetkrát (důvod pro opakování je případné vyprůměrování doby, kdy se instrukce načítaly do instrukční cache). Repeat-rate se měří pomoci řady nezávislých instrukcí, například:

    add $1,%eax
    add $1,%ebx
    add $1,%ecx
    add $1,%edx
    add $1,%esi

    add $1,%eax
    add $1,%ebx
    add $1,%ecx
    add $1,%edx
    add $1,%esi
        ....

Pro jednoduchost se čas jumpu, který tvoří cyklus na konci bloku, a čas inicializace citace započítává do celkového testu. Jelikož je ale blok velký (stovky instrukcí), je chyba poměrně zanedbatelná (v řádech procent). V případě násobení je u ia32 architektury problém v předem daných registrech (%eax*něco → %edx:%eax). Je potřeba udělat explicitní MOV, abych se zbavil závislosti. Teoreticky by se měl provést zároveň s násobením.

Měření rychlosti pamětí

Kromě měření operací které něco počítají, budeme také měřit, jak dlouho trvá, než dostaneme data z paměti. Nejprve jak dlouho trvá MOV dat z L1-cache. Alokujeme si nevelké pole. Toto pole vynulujeme a pak ho dvaatřicetkrát přečteme. Tím procesor pochopí, že ho má držet v L1-cache. Pak následuje test:

        movl RPTS, %%edx
        dec  %%edx
        movl PITCH, %%ecx
        movl ADDRESS, %%edi
        movl %%ecx, %%esi
        addl %%esi, %%esi
loop:                       (*)
        movl (%%edi), %%eax
        movl (%%edi,%%ecx), %%ebx
        addl %%esi, %%edi

        movl (%%edi), %%eax
        movl (%%edi,%%ecx), %%ebx
        addl %%esi, %%edi
        .
    .
        .
        subl $1, %%edx
        jns loop

Je zde snaha číst data tak, aby byla teoretická šance provést všechny tři instrukce v bloku zároveň. Nakonec se změří, kolik taktů bylo v průměru potřeba na přenos jednoho 32bitového čísla. PITCH bylo v tomto případě rovno čtyřem, takže jsme četli souvislý úsek.

Pokud budeme chtít změřit, jak asi rychle funguje načítání z RAM, můžeme použít stejný kód, ale než ho spustíme, je třeba pole (které nyní bude mnohem větší) vystrnadit z cache. Toho se docílí alokováním 150 MB pomocného pole, které nejdřív vynulujeme, pak přečteme a pak se zaměříme na jeho kousky o velikosti 0,5 MB, které čteme a zapisujeme a postupně se posouváme podél velkého 150 MB pole. To celé se několikrát opakuje s různé velikými kousky (abychom různé veliké L1-cache nalákali na tato data a přiměli je zapomenout původní pole).

Nakonec spustíme čtení (*), tentokrát s větším PITCH. Pro hodnotu 74 bytů (což označuji za typickou cache-miss) uvidíme celkem přívětivé výsledky, jelikož počítač do L2-cache načte celou cache-line, takže na RAM budeme skutečně čekat jen občas. Zároveň ale 74 bytů je delší než typická L1-cache-line (která je 64 bytů), takže tím procesor nutíme číst z L2-cache.

Pro hodnotu PITCH=1048572 bytu však již uvidíme poměrně dlouhé časy. Velikost okolo 1 MB zaručí, že každý přístup bude do jiné řádky DRAM paměti, takže řadič paměti bude muset pokaždé provést plný cyklus přístupu (close/prechar­ge/řádek/slou­pec). Ještě tu máme jeden test s PITCH=1048572 a s poznámkou „1-pass cache flush“, což znamená, že 150 MB pole se pouze vynuluje a jednou přečte a pak se hned začne testovat pomocí (*). Jak uvidíme, procesorům AMD to stačí, aby zapomněly na původní data, nové procesory Intel si většinu z nich udrží přinejmenším v L2 cache.

Měříme v Linuxu

Čítač z RDTSC je globální pro celý operační systém, ne pro jednotlivé procesy. Měří tudíž reálný čas a kdybychom měli spuštěn s testem ještě jiný program, tak by měření ovlivnil. I kdyby však byl čítač lokální, výsledky by byly jiné, vzhledem k jinému chování cache po task switchi.

Proto je potřeba spouštět test jen na nezatíženém systému. I tak však neustále běží přerušení od časovače a ostatních periférii. Proto se každý test opakuje dvacetkrát a vybere se minimální naměřená hodnota (zbrzdilo nás minimálně, ideálně žádné, přerušení). Toto opatření je trochu v rozporu s měřením vybavovací doby paměti, protože tam se zajímáme spíše o maximální čas. Přijde-li například několikrát refresh (chodí každých 7 až 15 µs, podle typu paměti) a jednou ne, dostaneme na výstupu ten lepší výsledek, když nepřišel a nemuselo se na jeho dokončení čekat.

Přesnějšího měření by bylo možné dosáhnout při zakázaném přerušení, ale nevím, co by se pak stalo při případném page-faultu (jestli by si Linux přerušení zase povolil, kdyby třeba potřeboval mmapovat program z disku nebo swapovat, čemuž by se částečně dalo předejít zamknutím stránek v RAM). Pak by mělo smysl výsledky z jednotlivých opakování průměrovat. Jelikož jsem ale nechtěl riskovat zamrznutí systému a na většině měřených počítačů stejně nejsem root, dále jsem tento problém neřešil.

O programu

Program (zdrojový kód i binárka) jsou v příloze tohoto článku. Vzhledem k tomu, že používám spoustu assembleru, je to napsáno v gcc-2.95.3, které ještě podle staré normy C++ povolovalo stringy přes několik řádků. Měřil jsem jen 32bitovou integerovou výkonnost a ve floatech jen standardní FPU (bez SSE). To vše z lenosti. Program lze spustit i na 64bitových strojích, pokud je přeložen 32bitově (staré gcc stejně neumělo překládat jinak).

Tabulky

Výsledky nejsou úplně vědecké, správné bych měl měřit ještě směrodatnou odchylku (a dobře by bylo měřit maximum i minimum), ale to by pak vznikla spousta nepřehledných čísel (kdo to má rád, snadno si program upraví). V případě počítače SOL5 jsem měření několikrát opakoval a dvě instance jsem napsal pod sebe, aby si čtenář udělal představu o rozptylu.

V sloupečku DEPENDENT je odhad na latency, ve sloupečku INDEPENDENT je odhad na repeat-rate. Počet jader počítače je počet CPU, který uvádí /proc/cpuinfo. Testovalo se vždy jen jedno jádro a ostatní zahálela (resp. běžel top, sshd a nějaké systémové procesy).

Počítač FIREBALL1 (4jádro):

model name: Intel® Xeon® CPU 5160 @ 3.00GHz
cpu MHz: 2992.494
cache size: 4096 KB
cache_alignment: 64

Ukázka variability výsledků. Na lichých řádcích je jedno měření, na sudých je druhé. Měření byla provedena na nezatíženém stroji okamžitě po sobě a byla vybrána dvě z nich, která se hodně liší v přístupové době k paměti. Na ostatních instrukcích je vidět, že chyba měření je spíše systematická (zanedbávání instrukcí cyklu apod.) než náhodná (přerušení).

Počítač SOL5 (4jádro):

model name: Dual Core AMD Opteron™ Processor 275
cpu MHz: 2190.981
cache size: 1024 KB
cache_alignment: 64

Počítač GAIA (2jádro):

model name: Intel® Pentium® 4 CPU 3.00GHz
cpu MHz: 2992.602
cache size: 1024 KB

Počítač VICTORIA (1jádro):

model name: Intel® Pentium® 4 CPU 2.66GHz
cpu MHz: 2660.310
cache size: 512 KB

Počítač OLDATHLON (1jádro):

model name : AMD Athlon™ XP 1800+
cpu MHz : 1530.999
cache size : 256 KB

Interpretace výsledků a postřehy

Na první pohled je vidět převaha AMD v množství vykonané práce na takt procesoru (zvláště u násobení a dělení). Zajímavou výjimkou je počítač VICTORIA (Intel P4), který dovede provést dvě závislá sčítání během jednoho taktu. Je to tím, že jeho sčítačka umí pracovat jak v náběžné, tak i v sestupné hraně hodin. V případě, že jsou data nezávislá, už lepší není, protože dovede spustit stejně jen tři instrukce zároveň, což dává stejný výkon, jako má většina ostatních procesorů.

Řádek 0*0 imul testuje rychlost násobení „nula krát nula“. Na některých starších procesorech (i386) nebo třeba na ARM-7TDMI závisí doba násobení na číslech, která násobíme, přičemž 0*0 je nejrychlejší. Je vidět, že u nových procesorů tomu tak není.

Je pozoruhodné, že RDTSC trvá u některých Intelů až sto taktů. Přitom nevidím důvod, proč by musela být delší než jeden takt, když je to vlastně jen přečtení registru TSC čítače do %edx:%eax.

Jak je z tabulek vidět, latence pamětí je pořád poměrně dlouhá a od dob 8bitových počítačů se na rozdíl od přenosové rychlosti příliš nezlepšila (ATARI 800 XE mělo latenci paměti 559 ns z pohledu programátora, z pohledu HW spíš něco jako 260 ns).

Je vidět, že i FPU jednotka je u AMD lepší, jelikož je celkově rychlejší pro závislé instrukce a pro nezávislé má dokonce repeat-rate pro násobení rovno jedné. I nejlepší Xeon, který jsem testoval, měl repeat-rate dvě (nicméně Intely můžou být lepší v SSE, což jsem neměřil).

Řádek NaN+x fadd udává dobu instrukce fadd, která dostala jako operand NaN (Not a Number – výsledek operace 0/0). Jak je vidět, u AMD je pak latence (ale nikoliv repeat-rate) o jeden takt delší. Naproti tomu u Intelu provedení jedné takové instrukce může trvat až 1100 taktů (počítač GAIA). Důvod je mi neznámý, jen vím, že FPU je možné nastavit tak, že buď počítá s NaNy a Infy, nebo vyhodí výjimku. Vypadá to, jako by ji Linux chytil a do správného FPU registru strčil NaN jako výsledek a zase se vrátil, čímž by emuloval IEEE aritmetiku. Proč to není implementováno přímo, to netuším. Je to poměrně zrádné chování, představte si real-time program, který má zpracovávat nějaká data, ve kterých se občas objeví blok Infu nebo NaNu – rázem to běží tisíckrát pomaleji! Takovou chybu může být poměrně těžké objevit dřív, než způsobí nějakou škodu.

Pokud někdo víte, čím to přesně je, napište to do diskuze. Úplně nejlepší by bylo, kdyby někdo znal univerzální „zaříkadlo“, které napíšu na začátek svého programu a které mi nastaví FPU tak, aby se výjimky negenerovaly a fungovalo to jako u AMD.

Dále je vidět, že novější Intely (FIREBALL1) mají chytřejší cache, která se nedá vyprázdnit pomoci „1pass cache flush“, kdežto AMD se takto nechá zmást. Sice má SOL5 již určitý náznak zlepšení, ale k FIREBALL1 má ještě daleko.

Zajímavý je repeat-rate 0,56 pro čtení z L1-cache u počítače SOL5 (a 0,65 pro OLDATHLON). Znamená to, že se většinou podařilo v (*) provádět všechny tři instrukce zároveň. Intely toto neumějí.

Ještě zajímavější ale je, že starší verze testovacího programu, která pro přesun dvou čísel v (*) místo tří instrukci používala čtyři tímto způsobem (před vstupem do bloku bylo %esi=%edi+%ecx):

        movl (%edi), %eax
        addl %ecx, %edi
        movl (%esi), %ebx
        addl %ecx, %esi

dávala následující výsledky:

Počítač SOL5

Počítač FIREBALL1

Počítač GAIA

Počítač OLDATHLON

Je vidět že zde už se AMDčku tolik nedařilo spouštět čtení najednou, na druhou stranu ale máme téměř dvojnásobné zrychlení čtení z paměti, a to u všech procesorů. Důvod pro toto podivné chování neznám, mám hypotézu, že procesor nebo řadič paměti možná dělá spekulativní načítání dat. Když mám čtecí instrukce rozmístěné tak, že se provádí jedna za druhou s rostoucími adresami, tak z toho pozná, jakou asi další část budu z paměti chtít, a snaží se ji připravit do cache. Když je ale provádím najednou, je možné, že požadavky přicházejí víceméně náhodně (jak to procesoru zrovna vyjde při skládání a přehazování instrukce). To pak nejspíš zmate prediktor v určení vhodné adresy pro spekulativní načtení. Pokud máte někdo lepší vysvětlení, napište ho do diskuse. Původní chování se zapne definováním makra OLDVERSION a je přeloženo do binárky oldcpubench.

V každém případě je nová verze lepší pro otestování latence RAM. Dokonce se variabilita času snížila (jak je vidět z výsledků SOL5). Také zmizelo abnormální chování počítače GAIA, kdy načítání po „1pass cache flush“ trvalo déle než po důkladném vyprázdnění cache. To vše naznačuje, že jsme blíž k měření latence než ve staré verzi. Pouze se vtírá otázka, jestli skutečná latence není náhodou ještě třeba dvakrát větší a pouze se to teď šťastnou náhodou neprojevilo.

Poučení pro programátory (ano, to je úplně zbytečné…)

V „hot spotech“ programu je dobře řídit se těmito pravidly:

(1) Pokud násobíte integery, rozdělte kód tak, aby zároveň s násobením (které má latenci 3, 5, 6, 12 nebo 18 taktů podle typu procesoru) měl kompilátor šanci rozvrhnout nějaké nezávislé instrukce a výsledek násobení byl potřeba ideálně až za 18 taktů. Násobení a*(2^n) se to netýká, protože ho kompilátor přepíše na a<<n.

(2) Vyhýbejte se celočíselnému dělení, pokud to jde. Je pomalejší než floatové.

(3) Při práci s floaty místo (a+b)/2 radši pište 0.5*(a+b), nebo zkontrolujte v assembleru, že kompilátor první zápis sám převede na druhý.

(4) Nedopusťte, aby se vám na vstup dostaly NaNy nebo Infy (většinou to stejně znamená chybu), těch pár případů, kdy se to velmi hodí, je asi lepší oželet než riskovat sto- až tisícinásobné zpomalení programu.

(5) Při hashovaní typu „open addressing“ bývá linear-probing často rychlejší než double-hashing. Je to proto, že porovnání klíčů je řádově rychlejší než cache-miss. Takže zatímco double-hashing má při téměř každém přístupu tendenci tahat novou cache-line z paměti (nebo alespoň z cache další úrovně), linear-probing to udělá jen jednou a pak už může celkem rychle porovnávat. Řetízek je sice o něco delší, ale načtení dat do registru je řádově rychlejší.

(6) Pokud máte algoritmus, který prochází nějakou velkou datovou strukturu (například nějaký velký graf) víceméně náhodně, snažte se ho nahradit něčím jiným (třeba ho počítejte on-the-fly), nebo alespoň v paměti strukturu uspořádejte tak, jak k ní bude pravděpodobně přistupováno. Zrychlení může být klidně desetinásobné (což se například při paralelizaci některých algoritmů na nekonečně mnoho procesorů považuje za úspěch).

(7) Problémům s cache lze částečně ulehčit rozumným používáním instrukce PREFETCH, která načte data do cache ještě dřív, než budou opravdu potřeba.

(8) Pokud dosáhnete 50% rychlosti oproti teoretickému špičkovému výkonu z tohoto testu, nemá cenu dál optimalizovat – lepší už to nebude (co na jednom procesoru získáte, na jiném pokazíte). Mimo hot spot nemá cenu špinit si ruce jakýmkoliv optimalizováním, které za vás neudělá kompilátor.

Závěr

Rozdíl 50 % ve výkonu CPU (a troufám si říct, že i v aplikačním testu – pokud jedinou vaší aplikaci nebude ZIP a Quake) vůbec nic neznamená. Čili, nenechte se obalamutit „nezávislými testy CPU“. Velice záleží na tom, jak přesně je program přeložen, kde fyzicky v RAM sídlí a na mnoha dalších subtilních vlivech.

Pokud jste někdo šťastným majitelem procesoru AMD Phenom nebo Intel Quadcore, neváhejte, změřte a vložte výsledky do diskuze pod článkem. Doufám, že nemusím připomínat, že za chování měřicího programu neručím. Je možné ho dál šířit ve smyslu licence GNU GPL.