Názory k článku Vyrovnávací paměti a optimalizace programů
-
Rejpal (neregistrovaný)RDTSC už poměrně dlouhou dobu nepočítá cykly. Na strojích s dynamickým taktováním by to ani nemělo smysl. A započtěte si ještě SMP systémy, které jsou čím dál tím běžnější, a případné přehazování threadů a podobně, a nebudete se stačit divit. :-) Jen tak mimochodem, dnešní x86/x86_64 procesory mají co do měření přasnhéo časování mnohem lepší možnosti, než kdy byla RDTSC.
-
Rejpal (neregistrovaný)(Totiž, měl jsem na mysli, že na nových procesorech od Intelu nepočítá podle aktuální frekvence. Staré procesory od Intelu a všechny od AMD sice s aktuální (a měnící se) frekvencí počítají, ale ty údaje nejsou tak jako tak moc užitečné. :o) A když už to člověk chce mermomocí používat, je asi dobrý nápad aspoň vypnout jakékoli dynamické změny frekvence.)
-
ACK. RDTSC má už viac ako 10 rokov. Použiteľné sú aj inštrukcie RDPMC (read performance counter) a RDMSR.
http://en.wikipedia.org/wiki/RDTSC
HPET je trocha mladšia záležitosť.
http://en.wikipedia.org/wiki/High_Precision_Event_Timer
Minuloročný procák poskladaný z dvoch úlomkov kremíka s celkovým počtom tranov približne 880 melcov má constant timestamp.
CPUinfo (19-Aug-2007) by Rhett M. Hollander and Paul V. Bolotoff
GenuineIntel family 6 model F stepping 7
Intel Core 2 Quad (Kentsfield) 65nm processor
BIOS name string: "Intel(R) Core(TM)2 Quad CPU @ 2.40GHz"
(4x) I-cache: 32Kb, 8-way, 64 bytes per line
(4x) D-cache: 32Kb, 8-way, 64 bytes per line
(4x) I-TLB (4Kb pages): 128 entries, 4-way
(4x) I-TLB (4Mb pages): 4 entries, 4-way
(4x) D-TLB (4Kb pages): 256 entries, 4-way
(4x) D-TLB (4Mb pages): 32 entries, 4-way
(2x) S-cache: 4096Kb, 16-way, 64 bytes per line
Scalar: FPU CMOV CX8 CX16 AMD64
Vector: MMX MMX+ SSE SSE2 SSE3
General: MSR FXSR CLFSH SENTER VMX
Addressing: PSE PSE36 PAE PGE PAT MTRR
Monitoring: TSC TMSC TM TM2
Other: VME DE MCE MCA APIC DS SS NX
http://alasir.com/software/cpuinfo/index.html
Ale Mubadala procesory to nevedia. -
Kvakor (neregistrovaný)>InTheHell CPU od Pentium Pro pozná inštrukciu Read Timestamp Counter.
Ne, RDTSC byla uz v prvnich Pentiich, viz http://en.wikipedia.org/wiki/RDTSC . Jeste pamatuju, jak jsem kdysi delal programek, ktery se vesel do bootsektoru a vypocital frekvenci procesoru v MHz. Hodilo se to pri pretaktovavani, kdy BIOS hlasil nespravnou frekvenci procesoru, napr. puvodne byla frekvence 133MHz (4x33), po pretaktovani byla skutecna frekvence byla 160MHz (4x40, deska umela 30, 33, 40 a 50Mhz), i kdyz BIOS trval na puvodnich 133MHz. -
بطر (neregistrovaný)Spíš jak nepracují, ne? http://www.root.cz/zpravicky/predvedeni-bezpecnostnich-chyb-procesoru-intel/
-
Pavel TišnovskýZlatý podporovatelno pracují s ní stejně blbě jako ostatní procesory - dopředu nic neví o tom, co bude program potřebovat (jaké adresy) a cache line (bloky) má taky větší než integer, tak to je ve výsledku úplně nastejno -
Pavel TišnovskýZlatý podporovatelDůležitější je to strncmp(), ale i toto porovnání se tam vyskytlo, prostě reálná komerční aplikace :-)
-
Přemysl (neregistrovaný)
Ne, mně jde o to, že ta smyčka zde v tomto případě vůbec nemusí být. Pokud již někdo chce takto optimalizovat, myslel bych, že to alespoň udělá takto:
!*items[i].id_prvekSice z toho nemusí být na první pohled zřejmé, jakou to má funkci, ale toto je jedna z optimalizací, které kompilátor pravděpodobně neumí vykonat.
-
Pavel TišnovskýZlatý podporovatelNemusí tam být, právě že to je ukázka toho, že i v reálných aplikacích lidi nasekají smyčky aniž by si to třeba uvědomili. V céčku to aspoň trkne, protože se volá funkce, ale v jiných jazycích se vesele porovnávají stringy i uvnitř smyček (stringem se nahradily například výčty :-) a podle toho to vypadá.
Viz již poněkud dávnější problémy s výpočtem hešů pro řetězce v Javě - tam člověk vcelku nevinně (při vytvoření například HashMap<String, něco>) udělal někdy při přístupu do takové hešovací mapy dost hroznou smyčku. Sun to samozřejmě vyřešil (snad v 1.3), ale i tak to některé aplikace odnesly pomalým během. -
anonymníZaujla ma konstrukcia
array[i+j*width]++;
Z akeheho pohladu je toto dvojrozmerne pole?
Dvojrozmerne pole je podla mna pole smernikov na typ, kde tie smerniky ukazuju nma jednorozmerne pole cize sekvencny riadok dvojromerneho pola..
Som presvedceny,ze pri takom pristupe by bol efekt nelokality dat vyssi a teda vyznam lokality dat vyssi
Je to otazka individuality programatora, ale kedeze som zvyknuty pisat uvedenu konstrukciu ako
array[j*width+i]++;
tak mi chvilu trvalo pochopit autorovu verziu. Ale ako som napisl to je vec individuality a proti gustu ziadny disputat -
Michal Vyskocil (neregistrovaný)>Je to otazka individuality programatora, ale kedeze som zvyknuty pisat uvedenu konstrukciu ako
>
>array[j*width+i]++;
To mi připomnělo http://www.vtipkar.cz/s-1135-prijde-pepicek-ze-skoly-a-povida-tatinkovi-ze-dostal-petku-z-matiky-jak-to-pta-se-podrazdene-ot/ :-D
BTW: "hezké" SEO URL jsou ve spoustě případů pěkně hnusné. -
Pavel TišnovskýZlatý podporovatelZ hlediska programátora v céčku je skutečně 2D pole 1D pole ukazatelů (směrníků), ale to je jen pohled programátora. V paměti je to 2D struktura s prvky uloženými za sebe. Jinými slovy, když pro 2D pole napíšu int *p=pole[3], tak sice dostanu ukazatel na čtvrtý řádek (resp. na první prvek na tom řádku), ale ten ukazatel je vypočten právě pomocí width*3 (je samozřejmě možné, že si ty ukazatele překladač někde vytvoří jako temporary hodnoty, ale obecně to neplatí, což se dá ukázat například na char pole[10000000L][1] - tam by samotné ukazatele zabraly víc než součet bytů na řádku).
Blíže viz http://www.fredosaurus.com/notes-cpp/arrayptr/23two-dim-array-memory-layout.html nebo "Herout" -
anonymníTo ale vsetko plati pre staticke alebo pseudostaticke pole..
ako nahale pouzivam 2D pole napr. strtuktur napr. struct dirent a potrebujem dynamicky menit velkost pola tak mam vyhodnejsie "rozhadzat" 2D tabulku na riadky, umiestnene v RAM tak, aby kazda bola v inom riadku cache a samotne struktury tak, aby tiez boli kazda v inej riadke chache... Ak je aj pole pointrov na riadky v inom riadku cache, tak dosiahnem max rychlost behu.. -
Pavel TišnovskýZlatý podporovatelTo je samozřejmě pravda (i v tom odkazu se o tom mluví - arrays of arrays), typické je to u polí řetězců, ale na těchto "zubatých" polích by nebyly tak pěkně vidět ty výpadky cache, resp. by se to svádělo na jiný formát této struktury.
-
hisaak (neregistrovaný)Jste si jisty ze dela jen polovinu podminek? Ja si to myslel na prvni pohled taky, ale nevypada to tak. Ja teda v cecku nic nenapsal uz hezkych par let, ale mam pocit, ze ten odkomentovany radek v cyklu by musel vypadat jinak, aby to "skakalo po dvou". Cekal bych tam neco jako (*y)++ a ne jen y++, protoze takhle to jen hybe s tim ukazatelem.
No, smiruji se s tim, ze je to na me moc slozite. :-) -
Jirka (neregistrovaný)Mas pravdu! Ted jsem si to ale vyzkousel a odkementovana verze bezi o tri procenta dele. Takze otazku "Proc bezi rychleji?" pokladam za nesmyslnou. Uz s optimalizaci -O1 prekladac pozna prazdny cyklus a vysledek je v obou pripadech 0.
Pokud se v odkomentovane verzi zmeni 7. radek na int &y = i; a program se prelozi jako C++, dojde k zrychleni, ktere jsem popisoval, a to asi o 9 %.
Testovano na i686 AMD Athlon(tm) XP 1800+ AuthenticAMD GNU/Linux s gcc 4.1.2. Sypu si popel na hlavu. -
kvr (neregistrovaný)Popravde me prekvapuje, ze oba kody nebezi stejnou a to nulovou dobu. Mam tu gcc 3.4.4 a kupodivu neprijde na to, ze se tam vlastne nic nedeje.
Nicmene po odkomentovani mi kod rozhodne bezi pomaleji. Zatimco (s optimalizacemi) prvni jen dekrementuje v registru i, dokud nedojde na nulu, tak druhy jde skutecne 0-10000 a navic si jeste promennou nesmyslne uklada do pameti (asi vznikle zmatkem pri alokaci registru pro y, ktere se pak vyhodi). y spravne ignoruji oba kody.
V kterem prekladaci je to naopak? -
Pavel TišnovskýZlatý podporovatelpo optimalizaci (tusim snad staci -O2) by prekladac mel tu smycku nahradit prirazenim i=koncova_hodnota
mas vystup z gcc -S ? Docela by me to zajimalo, proc tam smycku ponechal. -
mity (neregistrovaný)Hmmm. Taky me to zaujalo. Vyzkousel jsem to tu prelozit na stroji na 64bitech pomoci gcc verze 4.1.2 20061115 prerelease (netlucte me, ja ten stroj nespravuju).
Pri zapnute optimalizaci (staci -O nebo -O1) to celou smycku vyhodi a program vypise 0.
Pokud ale pustim gcc bez jakehokoliv optimalizacniho prepinace, pak tu opravdu verze bez komentaru bezi rychleji: s komentarem okolo 3330000, bez komentare 2920000.
Koukal jsem trochu, co z toho gcc vyplodilo a podle mych chabych znalosti assembleru se mi jevi, ze ta verze s komentari v te smychce dela addl primo na misto v pameti, kdezto ta verze bez komentaru inkrementuje obe ty promenne v registrech. -
Pavel TišnovskýZlatý podporovatelZajimave je to po kompilaci s Intelim prekladacem s rozbalenim smycek. Sice se jiz dneska spatne odhaduji parovani instrukci, naplneni instrukcnich pipeline atd, ale zda se me, ze Intel odvedl opravdu dobrou praci. Samozrejme je vhodne do te smycky dat neco, co prekladaci zabrani v jeji eliminaci, ale umozni jeji rozbaleni.
-
kvr (neregistrovaný)3.4 (odkomentovano):
movl $0, -8(%ebp)
call _clock
movl %eax, %ebx
movl -8(%ebp), %eax
jmp L9
.p2align 4,,7
L11:
incl %eax
movl %eax, -8(%ebp)
L9:
cmpl $999999999, %eax
jle L11
Tedy i[mem] = 0; i[reg] = i[mem]; while (i[reg] < 9999999) i[mem] = ++i[reg];
Se zakomentovanym to vypada zhruba:
movl $99999999, %eax
L9:
decl %eax
jns L9
gcc 4.0 oboji prelozi jako posledni kod.
%eax (ani pripadne i[mem]) uz nikde cteno neni, takze v obou pripadech je i write-only, predpokladam, ze novejsi prekladac to vyhodi uplne.
Takze vysvetleni bude asi skutecne takove, jak pise kolega vedle, v debug modu gcc nacpe kolem tolik kodu, nad kterym nepremysli, ze muze delsi kod lip nacpat pipeliny -
Ondrej 'SanTiago' Zajicek (neregistrovaný)V uvadenem prikladu s dvojrozmernym pristupem do pole je sirka pole mocnina dvojky. Mam zkusenost, ze pri takove sirce je pruchod 'po sloupcich' vyrazne pomalejsi, nez kdyz je sirka obecna - zrejme dochazi k spatnemu vyuziti cache kvuli neuplne asociativite cache.
Jinak vyborny clanek o vlivu pameti na program je tento: http://lwn.net/Articles/250967/ -
Rejpal (neregistrovaný)Něco na tenhle způsob? ;-)
array size bytes t1 t2 delta t 512 x 512 1048576 0.090 2.750 2.660 2955.6% 513 x 513 1052676 0.090 0.130 0.040 44.4% 1024 x 1024 4194304 0.360 11.630 11.270 3130.6% 1025 x 1025 4202500 0.390 2.030 1.640 420.5% 2048 x 2048 16777216 1.460 49.190 47.730 3269.2% 2049 x 2049 16793604 1.490 11.750 10.260 688.6%
-
Pavel TišnovskýZlatý podporovateljj, 2-way nebo 4-way asociativni cache. Sel jsi jeste do vyssich velikosti pole? Potom se to IMHO srovna (ve chvili, kdy se do cache nevejde ani cely radek tabulky).
-
Pavel Tišnovský (neregistrovaný)Teď večer už mi to nemyslí, ale mám pocit, že pro 4-way asociativní cahce by mělo stačit pole s pěti řádky a počtem sloupců odpovídající počtu bloků/4. Protože po přístupu na pátý řádek v jednom sloupci se ti vyhodí ten první (u délky řádku=mocnině 2), pro jednu adresu se stejným zbytkem po modulo 2^x jsou vyhrazeny maximálně 4 bloky. Ale možná kecám, musím si to nakreslit :-)
-
Pavel Tišnovský (neregistrovaný)Ano to je pravda, právě díky 2-way nebo 4-way asociativitě cache. Kdyby byla plně asociativní (což, pokud vím, v dnešních PC není), tak by ten rozdíl nebyl tak velký.
S rostoucí velikostí pole se to vyrovná, v limitě pak bude poměr v rychlostech čtení/zápisu roven poměru sizeof(velikost bloku v cache)/sizeof(int), lepší to nikdy nebude. Samozřejmě ten program ještě dělá násobení, inkrementace čítačů a podmíněné skoky, to reálný poměr může snížit (ostatně násobení jsem mohl oddělat a zvyšovat jeden čítač o width, ovšem trošku by se ten program zneprůhlednil). -
Ako som už skôr uviedol, v minuloročnom procesore sú obi2 L1 cache 8-way a L2 cache je 16-way associative
I-cache: 32Kb, 8-way, 64 bytes per line
D-cache: 32Kb, 8-way, 64 bytes per line
S-cache: 4096Kb, 16-way, 64 bytes per line
http://alasir.com/software/cpuinfo/index.html -
Pavel Tišnovský (neregistrovaný)Na druhou stranu je 64 bytů na blok 2x víc, než u 2-4-way asociativních cache, to taky na rychlosti v tomto případě nepřidá. Ale musím uznat, že je to technologická bomba - udělat při takové rychlosti 8-way asociativní cache, ono totiž zajištění oné asociativity chce docela dost logiky okolo a ta musí být setsakramentsky rychlá, když L1 cache jede na tak vysokých frekvencích.
