Hierarchiczność klas (kaskadowość) a wydajność - odwoływanie się do zmiennych

Odpowiedz Nowy wątek
2015-01-24 14:16
WojtekMK
0

Witam, nie wiem, czy tytuł jest poprawny, ale mam takie pytanie:
Powiedzmy, że mam w jednej klasie obiekty innych klas, które zawierają jeszcze inne klasy itd. Dla uproszczenia załóżmy, że wszystkie są publiczne. Odwołanie się do jakiegoś obiektu niższego rzędu może odbywać się następująco:

Obiekt_Klasy_1.Obiekt_K2.Obiekt_K3.Obiekt_K4;

analogicznie, gdy są to wskaźniki tj.

Obiekt_Klasy_1->Obiekt_K2->Obiekt_K3->Obiekt_K4;

Moje pytanie brzmi jak kompilator zinterpretuje taki zapis? Czy on sobie skróci zapis do postaci: Obiekt_Klasy_1.Obiekt_K4; lub analogicznie Obiekt_Klasy_1->Obiekt_K4;?
Czy może będzie przechodził po kolei przez wszystkie obiekty?

Tzn. Czy wydajniejsze jest trzymanie wskaźnika na ostatni element takiej hierarchii (gdy często korzystamy z takiego obiektu) czy nie ma to znaczenia?

Z góry dziękuję za odpowiedź.

Pozostało 580 znaków

2015-01-24 14:35
2

Jednoznaczną odpowiedź ciężko udzielić, ale generalnie jest tak, że:

  • struktury zagnieżdżone są wewnątrz struktury nadrzędnej i mają stałe przesunięcia względem początku tej struktury nadrzędnej, wobec czego w zasadzie zawsze kompilator powinien być w stanie wyliczyć przesunięcie pola w strukturze zagnieżdżonej na etapie kompilacji,
  • wskaźniki są dynamiczne, w tym sensie, że na etapie kompilacji nie wiadomo gdzie wskaźnik będzie wskazywał, a co za tym idzie trzeba sprawdzić zawartość wszystkich wskaźników po kolei, by wiedzieć gdzie szukać danych. Jednak kompilator na etapie kompilacji wyszukuje wspólne podwyrażenia w kodzie i może zoptymalizować ilość dereferencji przez trzymanie ich w jakiejś postaci pamięci podręcznej (np rejestry procesora czy kolejne dodatkowe zmienne), przez co strata wydajności może być pomijalna,

Trzeba jeszcze zwrócić uwagę na zajętość pamięci podręcznej procesora. Jeżeli używasz dużych struktur ze strukturami zagnieżdżonymi, ale wykorzystujesz tylko niewiele pól z nich w danym czasie to wtedy, z powodu dość dużej ziarnistości pamięci podręcznej (linia pamięci podręcznej to zwykle 64 bajty i w takich kawałkach są przechowywane i transferowane pomiędzy poziomami pamięci podręcznej i pamięci RAM), możesz ją mocno nieoptymalnie wykorzystywać. W ogólności trzeba kierować się zasadą: co jest używane razem powinno być przechowywane razem. Używanie razem oznacza używanie w mniej więcej tym samym momencie, czyli np skala tysięcy taktów procesora (procesor 1 GHz wykonuje miliard taktów na sekundę). Przechowywane razem, czyli tak ułożone by zajmowały jak najmniej linii pamięci podręcznej.

Więcej na agner.org./optimize

PS:
Zapomniałem napisać o cache miss (o czym wspomniał Shalom). Cache miss to sytuacja w której dane nie znajdują się w pamięci podręcznej i trzeba je załadować z RAMu. To kosztuje sporo czasu i trzeba ilość takich sytuacji minimalizować. Dereferencja wskaźnika ma dużo większą szansę spowodować cache miss niż odwoływanie się do kolejnych pól jakiejś mega struktury ponieważ w przypadku dostępu do kolejnych pól w dużej strukturze:

  • kolejne pola mogą się znajdować w tej samej linii pamięci podręcznej co poprzednie, więc dane będą wciągnięte za jednym zamachem,
  • procesory mają wbudowane mechanizmy, które wykrywają liniowy dostęp do pamięci i wczytują kolejne linie pamięci podręcznej w tle (kolejne w sensie, że koleje adresy),

"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 3x, ostatnio: Wibowit, 2015-01-24 14:44

Pozostało 580 znaków

2015-01-24 14:36
0

Może wypowie się ktoś bardziej kompetentny, ale wydaje mi się że to trochę zależy. Jeśli masz pola alokowane razem z obiektem "zawierajacym", tzn masz nie-wskaźniki to jak najbardziej kompilator może sobie "policzyć" gdzie w pamięci będzie dany obiekt w dość prosty sposób. Przy wskaźnikach pojawia sie problem, bo nie ma takiej możliwości i faktycznie musi zajść przeskakiwanie po lokacjach w pamięci żeby znaleźć ten obiekt na końcu.

Czy trzymanie wskaźnika na ostatni obiekt będzie szybsze? To zależy. Jeśli masz tam pola a nie wskaźniki na dynamiczne obiekty to może sie okazać wolniejsze. Jeśli masz wskaźniki to generalnie unikniesz tych "skoków", ale one nie są wybitnie kosztowne. Większy problem z takim skakaniem po pamieci to cache miss, a tego w takiej sytuacji nie wyeliminujesz niestety.

Podkreślam ze to tylko moje domysły!


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...
edytowany 1x, ostatnio: Shalom, 2015-01-24 14:37

Pozostało 580 znaków

2015-01-24 15:01
WojtekMK
0

Dziękuję Wam bardzo za wyjaśnienie!

Wibowit napisał(a):
  • struktury zagnieżdżone są wewnątrz struktury nadrzędnej i mają stałe przesunięcia względem początku tej struktury nadrzędnej, wobec czego w zasadzie zawsze kompilator powinien być w stanie wyliczyć przesunięcie pola w strukturze zagnieżdżonej na etapie kompilacji,

Jeszcze tylko dopytam: pisząc o strukturach zagnieżdżonych masz na myśli również coś takiego:

class Klasa1
{
Klasa2 obiekt;
}

czy jako:

class Klasa1
{
   class Klasa2
   {
   //...
   }
}

Pozostało 580 znaków

2015-01-24 15:05
0

Mam na myśli to pierwsze. Aczkolwiek to drugie nie wyklucza pierwszego (tzn też można dodać Klasa2 obiekt przed ostatnim nawiasem, chyba - ekspertem od C++ nie jestem ;p). Chodzi mi o ułożenie i rodzaj pól, a nie miejsce definicji klas.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 2x, ostatnio: Wibowit, 2015-01-24 15:06

Pozostało 580 znaków

2015-01-24 15:09
0

Tutaj masz coś do zabawy: http://goo.gl/UMn1ye

Są tam dwie hierarchie klas. Jedna zbudowana na wskaźnikach, druga na normalnych składnikach. Dla każdej hierarchii jest funkcja, która zmienia jakiś tam głęboko zakopany element. Widać, że tam gdzie operuje się na wskaźnikach wykonywana jest cała seria "skoków" do kolejnych obiektów. W przypadku normalnych składników nie ma żadnych skoków - jest tylko przesunięcie. Aby łatwiej zobaczyć to przesunięcie zakomentuj jakiś składnik dummy - widać, że wynik funkcji source jest zapisywany do innego miejsca na stosie (liczba przesunięcia od początku stosu rbp w mov DWORD PTR [rbp-4], eax będzie inna, w eax jest wynik funkcji source).

To dobrze widać tylko bez optymalizacji, bo potem kompilator orientuje się, że ten kod nie ma za dużego sensu i robi inne optymalizacje, które zaciemniają wynik. W każdym razie zawsze będzie tak, że wskaźniki wymagaja przejść a normalne składniki wymagają jedynie obliczenia pozycji.

Zazwyczaj nie należy się czymś takim przejmować, chyba, że to na prawde jakieś wąskie gradło wskazane przez profiler.


"(...) otherwise, the behavior is undefined".
edytowany 2x, ostatnio: Endrju, 2015-01-24 15:16
Pokaż pozostałe 4 komentarze
Miałem na myśli problem cache miss - satirev 2015-01-24 15:37
Jasne, ale akurat kwestia cache miss i niemożliwego read-ahead która przy implementacji ze wskaźnikami będzie praktycznie nie do uniknięcia dla wersji z obiektami może w ogóle nie występować. I różnica w wydajności może być spora ;) A to że projekt musi być dobry to jasne! :) - Shalom 2015-01-24 15:39
No dobrze. Ale ja nie rozważałem cache miss tylko skoki i te skoki chciałem pokazać w ASM. O to pytał autor wątku. - Endrju 2015-01-24 15:45
Pytał też o to jakie rozwiązanie będzie wydajniejsze ;) - Shalom 2015-01-24 15:47

Pozostało 580 znaków

2015-01-24 15:26
0

Generalnie udzielił już @Wibowit. Warto jednak dodać kilka słów wyjaśnienia.
Jeśli odwołujesz się do jakiegoś, zagnieżdżonego w strukturze typu w via wskaźnik/referencje to za każdym razem otrzymujesz cache miss (chyba, że akurat te obiekty znajdują się obok siebie w pamięci...). Przykład:

foo->bar->buzz(); // znalezienie bar = cache miss (pomijam problem wydajności metod wirtualnych, o ile buzz jest wirtualna)

Jeśli foo asocjowałby obiekt bar to znalezienie tego obiektu w pamięci będzie z pewnością wydajniejsze (bo istnieje stały offset, który determinuje położenie bar) ale nie oznacza to, że na pewno nie wystąpi cache miss (bo możemy np., mieć kolekcję takich obiektów, które same w sobie są bardzo złożone i przez to nie mieścić się w cache).
Z tego wysuwa się wniosek, że trzymanie pointera na ostatni obiekt z tego łańcucha wywołań, co prawda nie uchroni nas przed cache miss ale z pewnością zniweluje liczbę cache miss do max 1, ergo będzie to wydajniejsze niż łańcuch odwołań via ptr/ref. Jeśli chodzi o porównanie z dostępem przez pole klasy, to w przypadku małych obiektów (mieszących się w cache) ten drugi sposób powinien być wydajniejszy.

Podsumowując, wydajność uzyskujemy wtedy, gdy działamy na stosunkowo małych obiektach, najlepiej tego samego typu (w przypadku kolekcji).
Polecam poczytać to: http://gameprogrammingpatterns.com/data-locality.html

Pozostało 580 znaków

2015-01-28 12:15
WojtekMK
0

Hey, mam jeszcze jedno pytanie dot. omawianego problemu:
Czy jeśli mam funkcję, która przyjmuje jako argument wskaźnik bądź referencję do takiego obiektu a następnie często korzysta z tych wewnętrznych obiektów (lub jednego konkretnego) tj. np.

void funkcja1(Klasa* klasa)
{
funkcja2(klasa->obiekt->x);
funkcja3(klasa->obiekt->x);
double zmienna = cos_tam*klasa->obiekt->x;
//... itd (często wykorzystywana zmienna to: klasa->obiekt->x)
}

To czy kompilator/program za każdym razem, gdy odwołujemy się do x będzie robił cache missy i takie tam? Czy może on sobie to jakoś zoptymalizuje i zapisze tą zmienną?

Z góry dzięki za pomoc.

Pozostało 580 znaków

2015-01-28 23:18
0

Jeśli chodzi o cache miss:
Pamięć podręczna jest podzielona na zbiory linii danych. Zbiór dla danej linii danych jest wyliczany na podstawie jej adresu. Linie pamięci w zbiorze mają nadane priorytety i jeżeli jest ładowana nowa linia pamięci do zbioru to wypiera ona tę która ma najniższy priorytet. Priorytet jest obliczany na podstawie głównie czasu od ostatniego użycia, ale czasem chyba też od ilości użyć. Załadowana linia pamięci generalnie siedzi w pamięci podręcznej dopóki jakaś inna jej nie wyprze. Stąd wniosek, że w typowym przypadku prawdopodobieństwo że interesująca na linia pamięci została wyrzucona po drodze zależy od stosunku ilości danych załadowanych na tej drodze do ilości pamięci podręcznej.
:]

Upraszczając: jeżeli pomiędzy odwołaniami się do tego samego miejsca w pamięci nie ładujesz dziesiątek czy setek kilobajtów pamięci (zależnie od rozmiarów pamięci w procesorze i rozproszenia ładowanych danych) to linia pamięci nie powinna zostać wyrzucona z pamięci podręcznej, a co za tym idzie ponowne odwołania nie powinny wywołać cache miss.

A wracając do meritum problemu, czyli co zrobi kompilator w przypadku twojego programu?
Hm, wydaje mi się, że o ile nie zinlineuje (wklei wprost) ciał wywoływanych funkcji i wykryje jakieś fajne sposoby na optymalizacje, to wygeneruje chodzenie po wskaźnikach za każdym razem. Generalnie kompilator nie może zrobić optymalizacji które zmieniają działanie programu, a przecież np funkcja2 może w jakiś sposób znać adres obiektu zawarty w zmiennej klasa i podmieć w tym obiekcie pole obiekt i wtedy kolejne wywołanie klasa->obiekt->x da inny wynik. Jeżeli jesteś pewien, że klasa->obiekt->x da za każdym razem ten sam wynik w tej funkcji to zrób kolejną zmienną lokalną. Nie tylko ułatwisz zadanie kompilatorowi, ale też dasz wyraźną wskazówkę innym programistom, że w kodzie żadna ukryta magia się nie dzieje i wskaźniki są cały czas takie same.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2015-01-29 15:41
WojtekMK
0

@Wibowit dziękuję Ci bardzo za Twoje rzetelne wypowiedzi!!!
Pozdrawiam.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0