Obsah
1. Optimalizace programů z hlediska přístupu do operační paměti
2. Inkrementace či dekrementace adres při práci s poli?
3. Vliv optimalizace v překladači na výsledný strojový kód
4. Přístup do dvojrozměrného pole po řádcích či sloupcích
5. Vliv optimalizace
6. Složitější příklad
7. Literatura a odkazy na Internetu
8. Obsah další části seriálu
1. Optimalizace programů z hlediska přístupu do operační paměti
Při snaze o vytvoření co nejrychleji pracujících aplikací se mnohdy nevyhneme úvahám o tom, jak je rychlost běhu programu ovlivněna přítomností vyrovnávacích pamětí. Pokud by se v počítačích vyrovnávací paměti nepoužívaly a operační paměť by skutečně byla RAM (Random Access Memory), tj. náhodně adresovatelná (se stejnou dobou přístupu do jakékoli buňky), je možné programy optimalizovat s ohledem na složitost algoritmů a datových struktur, popř. se zaměřit na specifika dané platformy – například přítomnost instrukcí typu MMX, SSE, souběžné práce matematického koprocesoru s ALU atd. Ovšem kvůli tomu, že náhodné přístupy do operační paměti jsou provedeny pomaleji, než přístupy sekvenční a především díky vyrovnávacím pamětem se situace poněkud komplikuje, protože i zdánlivě rychlý algoritmus může být v praxi pomalejší než algoritmus s vyšší teoretickou složitostí. Také se ukazuje, že v některých případech bývá vhodné některá data nejprve transformovat a teprve poté s nimi provádět další manipulace (transpozice matice před maticovým násobením atd.). Dnes si ukážeme několik jednoduchých příkladů takové úpravy aplikací. Předem je ještě nutné říci, že by se optimalizace měly provádět až ve chvíli, kdy profiler přesně ukáže na místo, ve kterém dochází ke snižování výkonnosti. Profiling by se měl spouštět na reálných datech (ne na malé množině), právě s ohledem na vyrovnávací paměti.
2. Inkrementace či dekrementace adres při práci s poli?
V některých materiálech zabývajících se optimalizací, se lze dočíst, že při procházení polem, tj. sekvencí po sobě jdoucích adres, je výhodnější procházet vždy od začátku pole k jeho konci. Vyplývá to především z funkcí některých typů dynamických pamětí, které umožňují blokový přenos dat. Ovšem přítomnost vyrovnávacích pamětí v podstatě jakékoli rozdíly v rychlosti smaže, jelikož přenos bloků mezi vyrovnávací pamětí a operační pamětí je vždy prováděn blokově a na vzájemné pozici bloků v operační paměti do velké míry nezáleží. Samotný „opačný“ přístup do jednotlivého bloku uloženého ve vyrovnávací paměti pak nepřináší žádné měřitelné zpoždění, protože se jedná o SRAM. Výsledná rychlost programu tak plně závisí na tom, jakým způsobem je program přeložen do strojového kódu (uvidíme níže). Testovací program vypadá následovně:
/* ------------------------------------------------------------------------- */
/* Vypocet rozdilu casu pri pristupu do pole s inkrementaci a dekrementaci */
/* adresy. */
/* Autor: Pavel Tisnovsky */
/* */
/* soucast clanku "Co se deje v pocitaci?" na www.root.cz */
/* (/serialy/co-se-deje-v-pocitaci/) */
/* */
/* typicky preklad: gcc -std=c99 -Wall test.c */
/* ------------------------------------------------------------------------- */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define INNER_LOOP_COUNT 100
/* typ polozek ulozenych v poli */
typedef unsigned int item_type;
/* typ vlastniho pole */
typedef item_type * array_type;
/* ------------------------------------------------------------------------- */
/* vypocet velikosti pole v bytech pro zadany rozmer */
/* ------------------------------------------------------------------------- */
size_t get_size(int width)
{
return sizeof(item_type)*width;
}
/* ------------------------------------------------------------------------- */
/* alokace pole ve virtualni pameti */
/* ------------------------------------------------------------------------- */
array_type allocate_array(int width)
{
size_t size=get_size(width);
array_type array=(array_type)malloc(size);
if (array==NULL)
{
fprintf(stderr,
"Nelze alokovat pole o velikosti %ld bytu!\n",
(long)size);
exit(-1);
}
return array;
}
/* ------------------------------------------------------------------------- */
/* pocatecni vypln pole - skutecna alokace vsech jeho polozek */
/* ------------------------------------------------------------------------- */
void fill_array(array_type array, int width)
{
memset(array, get_size(width), 0);
}
/* ------------------------------------------------------------------------- */
/* dealokace pole (na nekterych systemech se pamet skutecne uvolni) */
/* ------------------------------------------------------------------------- */
void deallocate_array(item_type *array)
{
free(array);
}
/* ------------------------------------------------------------------------- */
/* sekvencni pristup ke vsem polozkam v poli se zvysujici se adresou */
/* ------------------------------------------------------------------------- */
void access_array_inc(array_type array, int width)
{
int i;
array_type p;
for (p=array, i=0; i<width; i++, p++)
{
(*p)++;
}
}
/* ------------------------------------------------------------------------- */
/* sekvencni pristup ke vsem polozkam v poli se snizujici se adresou */
/* ------------------------------------------------------------------------- */
void access_array_dec(array_type array, int width)
{
int i;
array_type p;
for (p=array+(width-1), i=0; i<width; i++, p--)
{
(*p)++;
}
}
/* ------------------------------------------------------------------------- */
/* vypocet casu pro oba dva zpusoby pristupu k poli */
/* ------------------------------------------------------------------------- */
void compute_times(int width, double *t1, double *t2)
{
array_type array=NULL;
clock_t t_start, t_end;
int i;
array=allocate_array(width);
fill_array(array, width);
t_start=clock();
for (i=0; i<INNER_LOOP_COUNT; i++)
{
access_array_inc(array, width);
}
t_end=clock();
*t1=((double)(t_end-t_start)/CLOCKS_PER_SEC);
t_start=clock();
for (i=0; i<INNER_LOOP_COUNT; i++)
{
access_array_dec(array, width);
}
t_end=clock();
*t2=((double)(t_end-t_start)/CLOCKS_PER_SEC);
deallocate_array(array);
}
/* ------------------------------------------------------------------------- */
/* funkce spustena po startu procesu */
/* ------------------------------------------------------------------------- */
int main(void)
{
int i, size=1;
double t1, t2;
printf("array size bytes t1 t2 delta t\n");
for (i=0; i<24; i++)
{
compute_times(size, &t1, &t2);
printf("%9d %9ld %6.3f %6.3f %6.3f\n",
size, (long)get_size(size), t1, t2, t2-t1);
size*=2;
}
return 0;
}
/* ------------------------------------------------------------------------- */
/* finito */
/* ------------------------------------------------------------------------- */ Zajímavý je pohled na to, jakým způsobem se jednotlivé smyčky přeloží. Přeložená smyčka funkce access_array_inc vypadá při vypnutých optimalizacích následovně:
LOOP1:
incl (%edx) - přístup do paměti
addl $4, %edx - zde se provádí zvýšení hodnoty ukazatele
decl %eax - počitadlo smyčky
jne LOOP1 Zatímco smyčka funkce access_array_dec používá opačný průchod:
LOOP2:
incl (%edx) - přístup do paměti
subl $4, %edx - zde se provádí snížení hodnoty ukazatele
decl %eax - počitadlo smyčky
jne LOOP2 Výsledné časy běhu programu (důležité jsou relativní hodnoty, ne absolutní) pro různé délky pole ukazuje následující tabulka:
array size bytes t1 t2 delta t
1 4 0.000 0.000 0.000
2 8 0.000 0.000 0.000
4 16 0.000 0.000 0.000
8 32 0.000 0.000 0.000
16 64 0.000 0.000 0.000
32 128 0.000 0.000 0.000
64 256 0.000 0.000 0.000
128 512 0.000 0.000 0.000
256 1024 0.000 0.000 0.000
512 2048 0.000 0.000 0.000
1024 4096 0.000 0.000 0.000
2048 8192 0.000 0.010 0.010
4096 16384 0.000 0.010 0.010
8192 32768 0.010 0.010 0.000
16384 65536 0.020 0.020 0.000
32768 131072 0.040 0.050 0.010
65536 262144 0.090 0.110 0.020
131072 524288 0.190 0.171 -0.019
262144 1048576 0.340 0.341 0.001
524288 2097152 0.691 0.691 0.000
1048576 4194304 1.382 1.402 0.020
2097152 8388608 2.784 2.794 0.010
4194304 16777216 5.558 5.568 0.010
8388608 33554432 11.146 11.156 0.010
3. Vliv optimalizace v překladači na výsledný strojový kód
I po optimalizaci strojového kódu na rychlost, tj. při použití přepínačů -O3 -funroll-all-loops -std=c89 -Wall, není mezi jednotlivými přístupy do pole žádný podstatný rozdíl, i když se samotný běh programu cca 2× urychlil:
array size bytes t1 t2 delta t
1 4 0.000 0.000 0.000
2 8 0.000 0.000 0.000
4 16 0.000 0.000 0.000
8 32 0.000 0.000 0.000
16 64 0.000 0.000 0.000
32 128 0.000 0.000 0.000
64 256 0.000 0.000 0.000
128 512 0.000 0.000 0.000
256 1024 0.000 0.000 0.000
512 2048 0.000 0.000 0.000
1024 4096 0.000 0.000 0.000
2048 8192 0.000 0.000 0.000
4096 16384 0.000 0.000 0.000
8192 32768 0.000 0.000 0.000
16384 65536 0.010 0.000 -0.010
32768 131072 0.010 0.010 0.000
65536 262144 0.020 0.020 0.000
131072 524288 0.040 0.040 0.000
262144 1048576 0.070 0.080 0.010
524288 2097152 0.160 0.150 -0.010
1048576 4194304 0.661 0.651 -0.010
2097152 8388608 1.492 1.493 0.001
4194304 16777216 3.034 3.024 -0.010
8388608 33554432 6.049 6.049 0.000
4. Přístup do dvojrozměrného pole po řádcích či sloupcích
Mnohem zásadnější je časový rozdíl při přístupu do dvojrozměrného pole. Zde se již naplno projeví vlastnosti DRAM i vyrovnávacích pamětí, především ve chvíli, kdy se velikost jednotlivých položek pole odlišuje od velikosti bloku ve vyrovnávací paměti. Vše si ukážeme na jednoduchém testovacím příkladu, ve kterém se přistupuje ke všem prvkům dvojrozměrného pole. První přístup je „po řádcích“, druhý „po sloupcích“. Z teoretického hlediska není mezi těmito přístupy rozdíl (složitost je O(n)), ovšem v praxi je patrné, že ve chvíli, kdy velikost pole překročí kapacitu vyrovnávací paměti, dojde k výraznému zpomalení nesekvenčního přístupu k položkám pole – je tomu tak z toho důvodu, že se sice do vyrovnávací pamětí načte vždy celý blok (může se jednat o například 8 položek pole), ale využije se z něj pouze jedna položka.
/* ------------------------------------------------------------------------- */
/* Vypocet rozdilu casu pri pristupu do pole po radcich a po sloupcich */
/* Autor: Pavel Tisnovsky */
/* */
/* soucast clanku "Co se deje v pocitaci?" na www.root.cz */
/* (/serialy/co-se-deje-v-pocitaci/) */
/* */
/* typicky preklad: gcc -std=c99 -Wall test.c */
/* ------------------------------------------------------------------------- */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define INNER_LOOP_COUNT 100
/* typ polozek ulozenych v poli */
typedef unsigned int item_type;
/* typ vlastniho pole */
typedef item_type * array_type;
/* ------------------------------------------------------------------------- */
/* vypocet velikosti pole v bytech pro zadane rozmery */
/* ------------------------------------------------------------------------- */
size_t get_size(int width, int height)
{
return sizeof(item_type)*width*height;
}
/* ------------------------------------------------------------------------- */
/* alokace pole ve virtualni pameti */
/* ------------------------------------------------------------------------- */
array_type allocate_array(int width, int height)
{
size_t size=get_size(width, height);
array_type array=(array_type)malloc(size);
if (array==NULL)
{
fprintf(stderr, "Nelze alokovat pole o velikosti %ld bytu!\n", (long)size);
exit(-1);
}
return array;
}
/* ------------------------------------------------------------------------- */
/* pocatecni vypln pole - skutecna alokace vsech jeho polozek */
/* ------------------------------------------------------------------------- */
void fill_array(array_type array, int width, int height)
{
memset(array, get_size(width, height), 0);
}
/* ------------------------------------------------------------------------- */
/* dealokace pole (na nekterych systemech se pamet skutecne uvolni) */
/* ------------------------------------------------------------------------- */
void deallocate_array(item_type *array)
{
free(array);
}
/* ------------------------------------------------------------------------- */
/* sekvencni pristup ke vsem polozkam v poli */
/* ------------------------------------------------------------------------- */
void access_array_sequentially(array_type array, int width, int height)
{
int i, j;
for (j=0; j<height; j++)
{
for (i=0; i<width; i++)
{
array[i+j*width]++;
}
}
}
/* ------------------------------------------------------------------------- */
/* pristup k polozkam pole po sloupcich */
/* ------------------------------------------------------------------------- */
void access_array_by_columns(array_type array, int width, int height)
{
int i, j;
for (i=0; i<width; i++)
{
for (j=0; j<height; j++)
{
array[i+j*width]++;
}
}
}
/* ------------------------------------------------------------------------- */
/* vypocet casu pro oba dva zpusoby pristupu k poli */
/* ------------------------------------------------------------------------- */
void compute_times(int width, int height, double *t1, double *t2)
{
array_type array=NULL;
clock_t t_start, t_end;
int i;
array=allocate_array(width, height);
fill_array(array, width, height);
t_start=clock();
for (i=0; i<INNER_LOOP_COUNT; i++)
{
access_array_sequentially(array, width, height);
}
t_end=clock();
*t1=((double)(t_end-t_start)/CLOCKS_PER_SEC);
t_start=clock();
for (i=0; i<INNER_LOOP_COUNT; i++)
{
access_array_by_columns(array, width, height);
}
t_end=clock();
*t2=((double)(t_end-t_start)/CLOCKS_PER_SEC);
deallocate_array(array);
}
/* ------------------------------------------------------------------------- */
/* funkce spustena po startu procesu */
/* ------------------------------------------------------------------------- */
int main(void)
{
int i, size=2;
printf(" array size bytes t1 t2 delta t\n");
for (i=0; i<12; i++)
{
double t1, t2;
double delta_t, proc;
compute_times(size, size, &t1, &t2);
delta_t=t2-t1;
proc=t1<1e-5 ? 0 : 100.0*(delta_t)/t1;
if (t2<t1) {double x=t1;t1=t2;t2=x;}
printf("%5d x%5d %9ld %7.3f %7.3f %7.3f %5.1f%%\n", size, size, (long)get_size(size, size), t1, t2, delta_t, proc);
size*=2;
}
return 0;
}
/* ------------------------------------------------------------------------- */
/* finito */
/* ------------------------------------------------------------------------- */ Podívejme se na výsledky získané při běhu tohoto příkladu přeloženého bez optimalizací, tj. pouze s volbami -std=c99 -Wall:
array size bytes t1 t2 delta t proc poznámka
2 x 2 16 0.000 0.000 0.000 0.0% (pod přesnost měření času)
4 x 4 64 0.000 0.000 0.000 0.0% (pod přesnost měření času)
8 x 8 256 0.000 0.000 0.000 0.0% (pod přesnost měření času)
16 x 16 1024 0.000 0.000 0.000 0.0% (pod přesnost měření času)
32 x 32 4096 0.000 0.010 0.010 0.0% (pod přesnost měření času)
64 x 64 16384 0.010 0.020 0.010 100.0% (pod přesnost měření času)
128 x 128 65536 0.040 0.040 0.000 0.0%
256 x 256 262144 0.120 0.160 0.040 33.3%
512 x 512 1048576 0.471 0.621 0.150 31.8%
1024 x 1024 4194304 1.902 14.992 13.090 688.2%
2048 x 2048 16777216 7.621 72.755 65.134 854.7%
4096 x 4096 67108864 30.814 304.908 274.094 889.5%
Větší pole nebylo možné použít, neboť na testovacím systému (notebook) mám pouze 256 MB operační paměti, z toho si cca 80 MB alokuje operační systém a jeho pomocné aplikace. Po alokaci dalšího pole s 256 MB by tedy došlo ke swapování, tj. meziukládání jednotlivých stránek paměti na disk, což by celé měření zkreslilo.
5. Vliv optimalizace
Mnohem zajímavějších výsledků je možné dosáhnout při překladu výše uvedeného testovacího programu se zapnutou optimalizací. Tabulka zobrazená níže byla získána po překladu s volbami -O3 -funroll-all-loops -std=c89 -Wall. Všimněte si, že se u obou typů smyček většinou snížily časy výpočtu (což se ostatně dá od optimalizovaného programu očekávat), ovšem časový rozdíl mezi jednotlivými smyčkami se neúměrně zvýšil. Je to logické, protože v optimalizovaném programu se překladači podařilo zrychlit provádění samotných smyček, ovšem u druhého typu smyčky program při svém běhu musí neustále čekat na přesuny dat z operační paměti do paměti vyrovnávací. Z toho vyplývá ponaučení, že je skutečně zapotřebí dbát na dodržení lokality dat (zde může jednoduchým prohozením smyček dojít až k dvacetinásobnému urychlení) a také, že ne vždy dokáže překladač program optimalizovat tak, jak by se možná dalo předpokládat (to je však téma, které by samo o sobě vydalo na celý článek):
array size bytes t1 t2 delta t proc poznámka
2 x 2 16 0.000 0.000 0.000 0.0% (pod přesnost měření času)
4 x 4 64 0.000 0.000 0.000 0.0% (pod přesnost měření času)
8 x 8 256 0.000 0.000 0.000 0.0% (pod přesnost měření času)
16 x 16 1024 0.000 0.000 0.000 0.0% (pod přesnost měření času)
32 x 32 4096 0.000 0.000 0.000 0.0% (pod přesnost měření času)
64 x 64 16384 0.000 0.000 0.000 0.0% (pod přesnost měření času)
128 x 128 65536 0.010 0.030 0.020 200.0%
256 x 256 262144 0.020 0.120 0.100 500.0%
512 x 512 1048576 0.080 0.551 0.471 588.8%
1024 x 1024 4194304 0.661 15.312 14.651 2216.5%
2048 x 2048 16777216 3.014 71.753 68.739 2280.7%
4096 x 4096 67108864 12.057 307.483 295.426 2450.2%
Optimalizovaná část kódu vypadá poněkud složitě, což je způsobeno částečným přeuspořádáním smyček (například se na začátku skáče dovnitř těla smyčky atd.):
L18:
xorl %edx, %edx
jmp L26
L27:
leal (%edx,%ecx), %eax
incl %edx
incl (%esi,%eax,4)
L26:
cmpl %ebx, %edx
jl L27
incl %edi
addl %ebx, %ecx
cmpl 16(%ebp), %edi
jl L18
6. Složitější příklad
V další ukázce programového kódu (jedná se konkrétně o část programu pro zobrazení vektorových dat přestavujících kolejovou síť) je jasně patrná jak lokalita dat, tak i lokalita programového kódu. Funkce drawEntities sice obsahuje poměrně velké množství programových řádků, ovšem naprostou většinu času zabere provádění tří do sebe vnořených smyček (důležité je uvidět i onu nejvnitřnější smyčku, která je poněkud skryta), protože počet zpracovávaných objektů (pole items) v praxi dosahuje řádů tisíců. Lokalita dat již není tak zřejmá, ovšem největší pole (items) je procházeno lineárně (sekvenčně) a menší pole, ve kterém je neustále prováděno vyhledávání, je tak malé, že se zcela jistě uloží do několika bloků datové vyrovnávací paměti – počet prvků tohoto pole dosahuje řádu desítek, proto se zde nevyplatilo použití nějaké složitější datové struktury typu hešovací tabulka nebo binární strom. Na druhou stranu lze nejvnitřnější programovou smyčku skutečně nahradit, v tomto případě (při znalosti formátu vstupních dat) dvojicí porovnání dvou celočíselných hodnot.
void drawEntities(DrawBuffer * buffer, Item * items, int maxitems, DbITems * knowItems, int selected)
{
int i,j;
char *typEntity[]=
{
"Neznámá entita",
"Polyčára",
"Kruhový oblouk",
"Kružnice",
"Region",
"Multibod"
};
printfxy(4, 32, "vybrany prvek: %d", selected);
setTextRGBcolor(0x80, 0x00, 0x00);
printfxy(10, 48, "ID prvku:");
printfxy(10, 272, "typ entity:");
setTextRGBcolor(0x00, 0x00, 0x80);
printfxy(90, 48, "%s", items[selected].id_prvek);
printfxy(90, 272, typEntity[items[selected].entityType]);
for (i=0; i<maxitems; i++)
{
int color=0;
int c;
if (items[i].activeItem)
{
int j;
for (j=0; knowItems[j].color; j++)
{
if (strncmp(knowItems[j].tudu, items[i].id_prvek, 8)==0)
{
color=knowItems[j].color;
c=color;
break;
}
}
}
if (!viewAll && (items[i].id_prvek==0 || strcmp(items[i].id_prvek, "")==0))
{
continue;
}
// program dále pokračuje
}
}
7. Literatura a odkazy na Internetu
- Pavel Valášek, Roman Loskot: Polovodičové paměti,
BEN – Technická literatura, Praha 1998, ISBN-80–86056–18-X - Budínský J.: Polovodičové paměti a jejich použití,
SNTL, Praha 1977 - Budínský J.: Polovodičové paměti – Názvosloví a definice,
TESLA VÚST, Praha 1980 - Janů K.: Paměti a řadiče – část I.,
ČSVTS, Knižnice mikroprocesorová technika, Praha 1982 - Great Microprocessors of the Past and Present (V 13.0.0)
- Revisiting the Cache Interference Costs of Context Switching (http://citeseer.ist.psu.edu/252861.html)
- Java theory and practice: Urban performance legends (http://www.ibm.com/developerworks/java/library/j-jtp04223.html)
- Java theory and practice: Urban performance legends, revisited (http://www-128.ibm.com/developerworks/java/library/j-jtp09275.html?ca=dgr-lnxw01JavaUrbanLegends)
- PDC05: Day Five (Five Things Every Win32 Developer Should Know) (http://www.lily.org/blog/2005/09/pdc05-day-five-five-things-every-win32.html)
- David Majda: Něco málo o optimalizaci (http://www.majda.cz/zapisnik/?220)
- Cache Mapping and Associativity (http://www.pcguide.com/ref/mbsys/cache/funcMapping-c.html)
- Wikipedia: Cache (http://en.wikipedia.org/wiki/Cache)
- Wikipedia: CPU cache (http://en.wikipedia.org/wiki/CPU_cache)
- Wikipedia: Cache algorithms (http://en.wikipedia.org/wiki/Cache_algorithms)
- Memory part 2: CPU caches (http://lwn.net/Articles/252125/)
- Memory part 5: What programmers can do (http://lwn.net/Articles/255364/)
- Cache Performance for SPEC CPU2000 Benchmarks (http://www.cs.wisc.edu/multifacet/misc/spec2000cache-data/)
8. Obsah další části seriálu
V následující části seriálu o funkci počítačů již opustíme problematiku operačních pamětí i pamětí vyrovnávacích, protože se začneme zabývat dalším rozsáhlým a přitom zajímavým a stále ještě aktuálním tématem – technologiemi magnetických pamětí, především páskových mechanik, disketových jednotek a pevných disků. Posléze se zaměříme i na paměti optické a magnetooptické. I přes velký vzrůst kapacity pamětí typu Flash EPROM a současném poklesu jejich ceny (přepočtené na jeden bit) jsou totiž u mnoha aplikací magnetické a optické paměti prozatím těžko nahraditelné.
