Názory k článku
Vyrovnávací paměti a optimalizace programů
17. 7. 2008 1:34
Nový
rdtsc
celé vlákno
InTheHell CPU od Pentium Pro pozná inštrukciu Read Timestamp Counter. Tá umožňuje zmerať počet hodinových cyklov v 64 bitovom čísle. Celkom dobré na optimalizáciu.
Rejpal (neregistrovaný)
17. 7. 2008 2:03
Nový
Re: rdtsc
celé vlákno
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ý)
17. 7. 2008 2:07
Nový
Re: rdtsc
celé vlákno
(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.)
17. 7. 2008 8:17
Nový
Re: rdtsc
celé vlákno
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.
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ý)
17. 7. 2008 11:03
Nový
Re: rdtsc
celé vlákno
>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.
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.
martin (neregistrovaný)
17. 7. 2008 1:48
Nový
Zaostalý autor
celé vlákno
Milý pan autor by si měl nastudovat, jak moderní procesory, například Core 2 Duo, pracují s pamětí. Patrně by přišel na zcela jiné myšlenky.
Rejpal (neregistrovaný)
17. 7. 2008 2:08
Nový
Re: Zaostalý autor
celé vlákno
Jistě se s námi podělíte o vlastní upřesnění článku, pokud o tom víte více, než tento autor. :->
بطر (neregistrovaný)
17. 7. 2008 8:46
Nový
Re: Zaostalý autor
celé vlákno
Spíš jak nepracují, ne? http://www.root.cz/zpravicky/predvedeni-bezpecnostnich-chyb-procesoru-intel/
aura:98
17. 7. 2008 9:31
Nový
Re: Zaostalý autor
celé vlákno
no 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
aura:82
17. 7. 2008 5:46
Nový
RE: Vyrovnávací paměti a optimalizace programů
celé vláknostrcmp(items[i].id_prvek, "")==0
A to je jako co? To je takhle napsané schválně, abych musel scrollovat? :D
aura:98
17. 7. 2008 10:10
Nový
RE: Vyrovnávací paměti a optimalizace programů
celé vlákno
Důležitější je to strncmp(), ale i toto porovnání se tam vyskytlo, prostě reálná komerční aplikace :-)
aura:98
17. 7. 2008 10:11
Nový
RE: Vyrovnávací paměti a optimalizace programů
celé vlákno
a příklad "skryté" smyčky
aura:82
17. 7. 2008 18:39
Nový
RE: Vyrovnávací paměti a optimalizace programů
celé vláknoNe, 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_prvek
Sice 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.
aura:98
17. 7. 2008 18:46
Nový
RE: Vyrovnávací paměti a optimalizace programů
celé vlákno
Nemusí 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.
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.
uživatel si přál zůstat v anonymitě
17. 7. 2008 8:12
Nový
Zaujimava konstrukcia array[i+j*width]++;
celé vlákno
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
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ý)
17. 7. 2008 9:18
Nový
Re: Zaujimava konstrukcia array[i+j*width]++;
celé vlákno
>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é.
>
>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é.
koroptev (neregistrovaný)
17. 7. 2008 9:39
Nový
Re: Zaujimava konstrukcia array[i+j*width]++;
celé vlákno
nez jsem si precetl ten vtip, tak jsem hledal deset rozdilu, dikes
aura:98
17. 7. 2008 9:52
Nový
Re: Zaujimava konstrukcia array[i+j*width]++;
celé vlákno
Z 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"
Blíže viz http://www.fredosaurus.com/notes-cpp/arrayptr/23two-dim-array-memory-layout.html nebo "Herout"
uživatel si přál zůstat v anonymitě
17. 7. 2008 10:23
Nový
Re: Zaujimava konstrukcia array[i+j*width]++;
celé vlákno
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..
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..
aura:98
17. 7. 2008 10:31
Nový
Re: Zaujimava konstrukcia array[i+j*width]++;
celé vlákno
To 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.
uživatel si přál zůstat v anonymitě
17. 7. 2008 11:00
Nový
Re: Zaujimava konstrukcia array[i+j*width]++;
celé vlákno
aha tak teraz uz chapem
nxina (neregistrovaný)
17. 7. 2008 9:26
Nový
Proč běží tento program po odkomentování rychleji?
celé vlákno
#include <stdio.h>
#include <time.h>
int main (void)
{
int i=0;
// int *y = &i;
clock_t ticks1, ticks2;
ticks1 = clock();
while (i < 1000000000)
{
i++;
// y++;
}
ticks2 = clock();
printf("Done! %ld\n", ticks2-ticks1);
return 0;
}
#include <time.h>
int main (void)
{
int i=0;
// int *y = &i;
clock_t ticks1, ticks2;
ticks1 = clock();
while (i < 1000000000)
{
i++;
// y++;
}
ticks2 = clock();
printf("Done! %ld\n", ticks2-ticks1);
return 0;
}
Jirka P (neregistrovaný)
17. 7. 2008 9:51
Nový
Re: Proč běží tento program po odkomentování rychleji?
celé vlákno
Žeby proto, že za jednu smyčku inkrementuje i dvakrát? Koukal jste se do assembleru, jestli překladač na vaši hru s pointrem přistoupil?
nxina (neregistrovaný)
17. 7. 2008 9:56
Nový
Re: Proč běží tento program po odkomentování rychleji?
celé vlákno
Nekoukala, to ani neumím, ale v té odkomentované verzi dělá jen věci navíc, nechápu, jak to může být rychlejší.
Jirka (neregistrovaný)
17. 7. 2008 10:37
Nový
Re: Proč běží tento program po odkomentování rychleji?
celé vlákno
No to tedy nedela. V cyklu skace po dvou, neprovadi polovinu podminek a skoku.
hisaak (neregistrovaný)
17. 7. 2008 10:49
Nový
Re: Proč běží tento program po odkomentování rychleji?
celé vlákno
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. :-)
No, smiruji se s tim, ze je to na me moc slozite. :-)
Jirka (neregistrovaný)
17. 7. 2008 17:12
Nový
Re: Proč běží tento program po odkomentování rychleji?
celé vlákno
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.
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.
Jirka (neregistrovaný)
17. 7. 2008 17:18
Nový
Re: Proč běží tento program po odkomentování rychleji?
celé vlákno
Jo a ta Tvoje verze s radkem 13 ve tvaru (*y)++; je take zrychleni, ale jen asi o 5 % (i kdyz tedy to mereni je +-autobus).
Michal Vyskocil (neregistrovaný)
17. 7. 2008 10:50
Nový
Re: Proč běží tento program po odkomentování rychleji?
celé vlákno
Opravdu? Vždyť y++ prostě posunuje hodnotu ukazatele a samotná hodnota i se vůbec nemění. Schválně si tam přidej čítač a porovnej oba výstupy. Aby platilo to, co říkáš, muselo by být na onom řádku (*y)++.
kvr (neregistrovaný)
17. 7. 2008 11:47
Nový
Re: Proč běží tento program po odkomentování rychleji?
celé vlákno
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?
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?
aura:98
17. 7. 2008 12:26
Nový
Re: Proč běží tento program po odkomentování rychleji?
celé vlákno
po 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.
mas vystup z gcc -S ? Docela by me to zajimalo, proc tam smycku ponechal.
mity (neregistrovaný)
17. 7. 2008 13:05
Nový
Re: Proč běží tento program po odkomentování rychleji?
celé vlákno
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.
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.
aura:98
17. 7. 2008 15:51
Nový
Re: Proč běží tento program po odkomentování rychleji?
celé vlákno
Zajimave 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ý)
17. 7. 2008 16:25
Nový
Re: Proč běží tento program po odkomentování rychleji?
celé vlákno
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
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ý)
17. 7. 2008 16:57
Nový
Sirka pole je mocnina dvojky.
celé vlákno
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/
Jinak vyborny clanek o vlivu pameti na program je tento: http://lwn.net/Articles/250967/
Rejpal (neregistrovaný)
17. 7. 2008 17:49
Nový
Re: Sirka pole je mocnina dvojky.
celé vlákno
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%
aura:98
17. 7. 2008 18:04
Nový
Re: Sirka pole je mocnina dvojky.
celé vlákno
jj, 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).
Rejpal (neregistrovaný)
17. 7. 2008 18:08
Nový
Re: Sirka pole je mocnina dvojky.
celé vlákno
Ufff, to abych pak pustil přes víkend, ne? ;-)
Pavel Tišnovský (neregistrovaný)
17. 7. 2008 21:24
Nový
Re: Sirka pole je mocnina dvojky.
celé vlákno
No nemusíš to samozřejmě přehánět a udělat jen tak velké pole, aby se celé vešlo do RAM. Já jsem si jen tak pro srandu udělal pole větší než je kapacita RAM a počítač ten příklad nerozchodil - podle "rychlosti" by mu ani ten víkend nestačil :-)
Rejpal (neregistrovaný)
17. 7. 2008 21:35
Nový
Re: Sirka pole je mocnina dvojky.
celé vlákno
To ale budu muset předělat na nečtvercové pole s přístupem po sloupcích. ;-) S 2 MB paměti na jádro nemám u čtvercového pole šanci dostat se s řádkem nad velikost cache a přitom nepřetéct z operační paměti s celým polem.
Pavel Tišnovský (neregistrovaný)
17. 7. 2008 21:49
Nový
Re: Sirka pole je mocnina dvojky.
celé vlákno
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 :-)
Jirka P (neregistrovaný)
17. 7. 2008 23:44
Nový
Re: Sirka pole je mocnina dvojky.
celé vlákno
Tak si to zkus nasimulovat ve valgrindu. Tam jdou velikosti keší i asociativita nastavit, takže z paměti nevylezeš :-)
Ondrej 'SanTiago' Zajicek (neregistrovaný)
17. 7. 2008 18:32
Nový
Re: Sirka pole je mocnina dvojky.
celé vlákno
Jo, presne tohle.
Pavel Tišnovský (neregistrovaný)
17. 7. 2008 21:29
Nový
Re: Sirka pole je mocnina dvojky.
celé vlákno
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).
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).
17. 7. 2008 22:53
Nový
Re: Sirka pole je mocnina dvojky.
celé vlákno
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
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ý)
17. 7. 2008 23:11
Nový
Re: Sirka pole je mocnina dvojky.
celé vlákno
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.
deda.jabko (neregistrovaný)
17. 7. 2008 22:00
Nový
pocitani cache miss
celé vlákno
neumi nejaky profiler pocitat jednotlive cache miss? nedavno jsem nasel problem, ktery podeziram, ze ho dela cache... ale chybi mi solidni dukaz. ;-]
Pavel Tišnovský (neregistrovaný)
17. 7. 2008 22:06
Nový
Re: pocitani cache miss
celé vlákno
Asi ne, ale přímo v procesoru (pokud myslíš platformu x86) jsou na to nějaké čítače. Ovšem otázkou je, jestli budou dostupné i z ringu uživatelských aplikací či pouze z jádra (ringu 0).
deda.jabko (neregistrovaný)
17. 7. 2008 22:29
Nový
Re: pocitani cache miss
celé vlákno
to asi na sparcu nepobezi, ze? ;-]
Rejpal (neregistrovaný)
17. 7. 2008 23:02
Nový
Re: pocitani cache miss
celé vlákno
deda.jabko (neregistrovaný)
17. 7. 2008 23:17
Nový
Re: pocitani cache miss
celé vlákno
diky za tip, zkusim (minimalne na x86). ja obvykle pouzivam qprof, protoze funguje jakz/takz vsude a zvladne relativne i vlakna, ale moc informaci z neho opravdu dostat nejde.
karel (neregistrovaný)
19. 7. 2008 16:40
Nový
Re: pocitani cache miss
celé vlákno
Umi to valgrind, resp. jeho tool cachegrind -- simuluje L1 i L2 cache a pocita hits/misses.
uživatel si přál zůstat v anonymitě
18. 7. 2008 11:19
Nový
RE: Vyrovnávací paměti a optimalizace programů
celé vlákno/* pocatecni vypln pole - skutecna alokace vsech jeho polozek */
memset(array, get_size(width), 0);
problem je, ze todle neudela vubec nic protoze je to blbe, zajimave, ze si nikdo nevsimnul... viz. man memset.
Jinak pekny serial!
aura:100
18. 7. 2008 11:20
Nový
RE: Vyrovnávací paměti a optimalizace programů
celé vlákno
Nechtel jsem "zůstat v anonymitě".. sorry.
