na czym polega pisanie cache friendly?

jak przepisac kod na wersje bardziej cache
friendly?

czy da sie patrzac na kod i wiedzac ile
procek ma cache projektowac tak struktury
danych by procek wyrabial sie w cache?

(w sensie rozroznienia pisania 'slabego' i 'mocnego'
chache friendly)

np jesli mam gierke z jakas duza iloscia agentow
i ich dane trzymam w tablicy agent[] to wiekszosc
kodu update() dziala niemal wylacznie na tej
teblicy agent[]

ale sa jeszcze funkcje draw() (dla kazdego agenta)
ktore dzialaj na danych agent[] i pisza do drugiej
tablicy pixelbufor[]

sam decyduje czy mam przeplatac drawy z updatami

for(int i=0; i<1000; i++)
{
agent_update(i);
agent_draw(i)
}

czy tez nie przeplatac :

for(int i=0; i<1000; i++) // uzywa agent[]
agent_update(i);

for(int i=0; i<1000; i++) // uzywa agent[] i pixelbufor[]
agent_draw(i)

druga forma wydaje sie ew bardziej cache
friendly

czy sa jakies dobrze okreslone reguly by pisac
kod mocno cache firendly?


((

oprocz kache friendly wydaje mi sie ze warto zwracac uwage
na align friendly (niestety nie wiem czy w c jest jakis
standardowy (np slowo kluczowe) sposob okreslania alignmentów
(w sumie dwu bo chodzi o poczatek i rozlozenie)

osobiscie wolalbym by dane byly w strukturach jednak upakowywane
ale pewne mechanizmy do automatycznego jak i jawnego narzucania
alignmentu by tez sie przydaly


pozatym jest jeszcze cos co bym nazwal fpu friendly - jest
zdaje sie cos co powoduje ze albo rzutowanie albo przelaczanie
int / float potrafi byc masakrycznie kosztowne (czytalem cos
w tutorialu gourleya o dynamice plynow ale nie doczytalem)
a jakos malo ludzi ma ta swiadomosc

[np
By default, the floating-point unit (FPU) converts floating-point
values to integers using rounding; but C specifies truncation. So
each float-to-int conversion requires changing the FPU mode to
&#8220;truncation,&#8221; but to do that safely requires first saving the old
control word, then restoring it after the conversion.

o tyle jest to pewien szok - rzutowanie z floata na inta moze
byc a zapewne jest b wolne (jesli powoduje zapisanie i odczytanie
'ustawien' fpu :/

]

jeszcze jakies metodyki optymisation friendly?
moze jakies zaawansowane artykuly do optymalizacji?

))




--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

<f...@N...gazeta.pl> napisał(a):

> na czym polega pisanie cache friendly?
Stosuje tylko bardzo proste zasady, bez wnikania w
szczegoly, a przyspieszenie bywa ogromne, rzedu 10-30 razy.

Ladnie to widac na mnozeniu macierzy. Operacje sa proste,
bo tylko mnozenie i dodawanie, ale pamieci duzo. Wiec przerzuty
pomiedzy poziomami cache moga byc waskim gardlem.

Generalnie jesli sa np. dwie tablice:
typ1 tab1[N];
typ2 tab2[N];

I przewidujesz ze zaraz po obliczeniu na tab1[i] program bedzie
wykonywal obliczenia na tab2[i], to lepiej upakowac w strukture:
struct X {
typ1 t1;
typ2 t2;
} tab[N];


Jesli obliczenia zaczynaja sie od t2, to lepiej odwrocic kolejnosc:
struct X {
typ2 t2;
typ1 t1;
} tab[N];


Generalnie dane ukladamy tak, aby program nie musial skakac na wpol
losowo po duzej przestrzeni adresowej, ale zeby mogl pracowac w
miare sekwencyjnie.

Pozdrawiam


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

M.M. <m...@g...pl> napisał(a):

> <f...@N...gazeta.pl> napisał(a):
>
> > na czym polega pisanie cache friendly?
> Stosuje tylko bardzo proste zasady, bez wnikania w
> szczegoly, a przyspieszenie bywa ogromne, rzedu 10-30 razy.
>
> Ladnie to widac na mnozeniu macierzy. Operacje sa proste,
> bo tylko mnozenie i dodawanie, ale pamieci duzo. Wiec przerzuty
> pomiedzy poziomami cache moga byc waskim gardlem.
>
> Generalnie jesli sa np. dwie tablice:
> typ1 tab1[N];
> typ2 tab2[N];
>
> I przewidujesz ze zaraz po obliczeniu na tab1[i] program bedzie
> wykonywal obliczenia na tab2[i], to lepiej upakowac w strukture:
> struct X {
> typ1 t1;
> typ2 t2;
> } tab[N];
>
>
> Jesli obliczenia zaczynaja sie od t2, to lepiej odwrocic kolejnosc:
> struct X {
> typ2 t2;
> typ1 t1;
> } tab[N];
>
>
> Generalnie dane ukladamy tak, aby program nie musial skakac na wpol
> losowo po duzej przestrzeni adresowej, ale zeby mogl pracowac w
> miare sekwencyjnie.
>

tylko takie zasady ? a jak duzych skokow nalezy unikac



wlasnie nie wiem jak jest dokladnie z tymi zasadami
kojarze tylko ze linijka cache ma mw 256 bajtow
(lub cos takiego),tak ze nawet nie wiem czy trzeba unikac

- GRUBOZIARNISTY ROZRZUT (?? powinno czy nie powinno robic rozxnicy)
- DROBNOZIARNISTY ROZRZUT (?? powinno czy nie powinno robic rozxnicy)

rozrzutu w przestrzeni adresowej czy chodzi o wyczerpywanie

- WYCZERPYWANIE

sie cache - nie wiem tez czy odwrocona kolejnosc

- ODWROCONA_KOLEJNOSC (??)

np dostepy sekwencyjne w tyl po adresach mialyby byc
wolniejsze czy nie

inna sprawa to kwestia tego by wogole unikac trzymania

- RAM DOSTEPY

np danych posrednich w ramie a c tego raczej jakos nie
nie wspiera, kwestie:

- czy jesli nie uzywam jawnego definiowania zmiennych
posrednich przy obliczaniu wyrazen to mam pewnosc ze
kompilator sam nie wrzuci mi niektorych posrednich etapow
wyliczen do jakichs komorek w ramie tylko wszystko
wyliczy na rejestrech i stacku fpu

- i tak nie wiadomo jak wtedy pogodzic przydatnosc
przechowywania wynikow czesciowych z przydatnoscia
nie uzywania przy tym ramu

int temp1 = x*x; // potrzebne tylko jako posrednie wyniki
int temp2 = y*y; // do dalszych wyliczen ale nie powinno byc w ram

int a = temp1+temp2;
int b = temp1-temp2;


sam uzywam zwykle duzych tablic sporych (kilkadziesiat
do kilkaset bajtow) rekordow
po czym zwykle gesto uzywam tylko malej czesci pol
o tych samych offsetach (np tych blizej poczatku
struktury a reszta jest uz bardziej sporadycznie) -
tym samym marnuje zdaje sie cache na cala tablice
- przy czym dla malej ilosci danych ona calo moze
sie moze miescic w cache a dla duzej juz nie miescic

ew jakbym znal dokladniej te reguly to moglbym dla
eksperymantu pisac specjalnie pod cache

- a jak sie ma sprawa z alignmentem? sam nie uzywam
alignmentu i zakladam niejako ze c nie robi 'paddingu'
ze tak powiem

char x; // adr pola = pocz_stukturyr + 0
float y; // adr pola = pocz_stukturyr + 1 a nie + 4
int z; // adr pola = pocz_struktury + 5 a nie + 8


(globalne wyrownywanie w b55 jest ustawione na
4 bajty tak ze nowe encje jak mysle sa wyrownywane
do 4 ale zakladam ze same pola w srodku nie sa rozstawiane
i 'padowane'

mechanizmy kontroli nad tym by sie przydaly bo np duze tablice
warto by wyrownywac chyba nawet do 4096



--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry

<f...@g...pl> napisał(a):
> tylko takie zasady ? a jak duzych skokow nalezy unikac
> wlasnie nie wiem jak jest dokladnie z tymi zasadami
> kojarze tylko ze linijka cache ma mw 256 bajtow
> (lub cos takiego),tak ze nawet nie wiem czy trzeba unikac
[ciach]
> ew jakbym znal dokladniej te reguly to moglbym dla
> eksperymantu pisac specjalnie pod cache

Nie wiem nic wiecej o szczegolach. Przed laty przeczytalem ksiazke
Kaspersky'ego i tyle mi do dzis w pamieci zostalo. Pierwsze pytanie
czy warto brnac w szczegoly, jesli podstawowe zasady daja duze
przyspieszenie? A co z roznymi architekturami sprzetowymi, na kazda
pisac osobno?
Pozdrawiam


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/

do góry