Pierwotne pytanie
Dlaczego jedna pętla jest o wiele wolniejsza niż dwie pętle?
Wniosek:
Przypadek 1 to klasyczny problem interpolacji, który okazuje się nieefektywny. Myślę też, że był to jeden z głównych powodów, dla których wiele architektur maszyn i programistów zakończyło budowę i projektowanie systemów wielordzeniowych z możliwością wykonywania aplikacji wielowątkowych, a także programowania równoległego.
Patrząc na to z tego rodzaju podejścia, bez angażowania sposobu, w jaki sprzęt, system operacyjny i kompilator (y) współpracują ze sobą, aby dokonać alokacji sterty obejmującej pracę z pamięcią RAM, pamięcią podręczną, plikami stron itp. matematyka, która leży u podstaw tych algorytmów, pokazuje nam, które z tych dwóch jest lepszym rozwiązaniem.
Możemy użyć analogii Bossbytu, Summationktóry będzie reprezentował coś For Loop, co musi podróżować między pracownikami Ai B.
Łatwo zauważyć, że przypadek 2 jest co najmniej o połowę szybszy, jeśli nie nieco większy niż przypadek 1, ze względu na różnicę w odległości potrzebnej do podróży i czas między pracownikami. Ta matematyka pokrywa się niemal wirtualnie i doskonale zarówno z BenchMark Times, jak i liczbą różnic w instrukcjach montażu.
Teraz zacznę wyjaśniać, jak to wszystko działa poniżej.
Ocena problemu
Kod PO:
const int n=100000;
for(int j=0;j<n;j++){
a1[j] += b1[j];
c1[j] += d1[j];
}
I
for(int j=0;j<n;j++){
a1[j] += b1[j];
}
for(int j=0;j<n;j++){
c1[j] += d1[j];
}
Rozważanie
Biorąc pod uwagę pierwotne pytanie OP dotyczące 2 wariantów pętli for i jego poprawione pytanie dotyczące zachowania pamięci podręcznej, a także wiele innych doskonałych odpowiedzi i użytecznych komentarzy; Chciałbym spróbować zrobić tutaj coś innego, stosując inne podejście do tej sytuacji i problemu.
Podejście
Biorąc pod uwagę dwie pętle i całą dyskusję na temat pamięci podręcznej i archiwizacji stron, chciałbym przyjąć inne podejście, patrząc na to z innej perspektywy. Ten, który nie wymaga pamięci podręcznej i plików stron ani wykonywania alokacji pamięci, w rzeczywistości takie podejście nawet nie dotyczy rzeczywistego sprzętu ani oprogramowania.
Perspektywa
Po dłuższym spojrzeniu na kod stało się jasne, na czym polega problem i co go generuje. Rozłóżmy to na problem algorytmiczny i spójrzmy na to z perspektywy używania notacji matematycznych, a następnie zastosuj analogię do problemów matematycznych, a także do algorytmów.
Co wiemy
Wiemy, że ta pętla będzie działać 100 000 razy. Wiemy również, że a1, b1, c1i d1są wskaźnikami na architekturze 64-bitowej. W C ++ na maszynie 32-bitowej wszystkie wskaźniki mają 4 bajty, a na maszynie 64-bitowej mają 8 bajtów, ponieważ wskaźniki mają stałą długość.
Wiemy, że w obu przypadkach mamy 32 bajty. Jedyną różnicą jest to, że przydzielamy 32 bajty lub 2 zestawy 2-8 bajtów na każdą iterację, przy czym w drugim przypadku przydzielamy 16 bajtów na każdą iterację dla obu niezależnych pętli.
Obie pętle nadal mają 32 bajty w całkowitej alokacji. Dzięki tym informacjom przejdźmy teraz do przedstawienia ogólnej matematyki, algorytmów i analogii tych pojęć.
Wiemy, ile razy ten sam zestaw lub grupa operacji musi być wykonana w obu przypadkach. Wiemy, ile pamięci trzeba przydzielić w obu przypadkach. Możemy ocenić, że całkowity nakład pracy związany z przydziałami między obydwoma przypadkami będzie w przybliżeniu taki sam.
Czego nie wiemy
Nie wiemy, jak długo potrwa dla każdego przypadku, chyba że ustawimy licznik i przeprowadzimy test porównawczy. Jednak testy porównawcze zostały już uwzględnione w pierwotnym pytaniu, a także w niektórych odpowiedziach i komentarzach; i widzimy znaczącą różnicę między nimi i to jest całe uzasadnienie tej propozycji tego problemu.
Zbadajmy
Widać już, że wielu już to zrobiło, patrząc na przydział sterty, testy porównawcze, pamięć RAM, pamięć podręczną i pliki stronicowania. Uwzględniono także określone punkty danych i konkretne wskaźniki iteracji, a różne rozmowy na temat tego konkretnego problemu powodują, że wiele osób zaczyna kwestionować inne powiązane kwestie. Jak zacząć patrzeć na ten problem, stosując algorytmy matematyczne i stosując do niego analogię? Zaczynamy od kilku twierdzeń! Następnie stamtąd budujemy nasz algorytm.
Nasze twierdzenia:
- Pozwolimy, aby nasza pętla i jej iteracje były sumowaniem, które zaczyna się od 1, a kończy od 100000 zamiast od 0, ponieważ w pętlach, ponieważ nie musimy się martwić schematem indeksowania 0 adresowania pamięci, ponieważ jesteśmy zainteresowani sam algorytm.
- W obu przypadkach mamy 4 funkcje do pracy i 2 wywołania funkcji, przy czym dla każdego wywołania funkcji wykonywane są 2 operacje. Będziemy je skonfigurować jako funkcji i wywołań funkcji jak:
F1(), F2(), f(a), f(b), f(c)i f(d).
Algorytmy:
Pierwszy przypadek: - Tylko jedno sumowanie, ale dwa niezależne wywołania funkcji.
Sum n=1 : [1,100000] = F1(), F2();
F1() = { f(a) = f(a) + f(b); }
F2() = { f(c) = f(c) + f(d); }
Drugi przypadek: - Dwa podsumowania, ale każde ma swoje własne wywołanie funkcji.
Sum1 n=1 : [1,100000] = F1();
F1() = { f(a) = f(a) + f(b); }
Sum2 n=1 : [1,100000] = F1();
F1() = { f(c) = f(c) + f(d); }
Jeśli zauważyłeś, F2()istnieje tylko Sumz Case1którym F1()zawarta jest w Sumod Case1a zarówno Sum1i Sum2od Case2. Będzie to widoczne później, gdy zaczniemy wnioskować, że w drugim algorytmie odbywa się optymalizacja.
Iteracje przez pierwsze Sumwywołania przypadku f(a), które dodadzą do siebie, f(b)a następnie wywołania f(c), które zrobią to samo, ale dodadzą f(d)do siebie dla każdej 100000iteracji. W drugim przypadku mamy Sum1i Sum2oba działają tak samo, jakby były tą samą funkcją wywoływaną dwa razy z rzędu.
W tym przypadku możemy traktować Sum1i Sum2jak zwykły stary, Sumgdzie Sumw tym przypadku wygląda to tak: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); }a teraz wygląda to na optymalizację, w której możemy po prostu uznać, że jest to ta sama funkcja.
Podsumowanie z analogią
Z tym, co widzieliśmy w drugim przypadku, wygląda na to, że istnieje optymalizacja, ponieważ obie pętle mają tę samą dokładną sygnaturę, ale to nie jest prawdziwy problem. Problemem nie jest praca, która jest wykonywana przez f(a), f(b), f(c), i f(d). W obu przypadkach i porównaniu między nimi, różnica w odległości, jaką musi pokonać Podsumowanie w każdym przypadku, daje różnicę w czasie wykonania.
Myśleć o For Loopsjak będąc Summationsktóre wykonuje iteracje jak bycie Boss, który wydawał rozkazy do dwóch osób Ai B, a ich praca jest do mięsa Ci Dodpowiednio i odebrać od nich jakąś paczkę i odesłać go. W tej analogii same pętle for lub iteracje sumowania i kontrole warunków nie reprezentują w rzeczywistości Boss. To, co tak naprawdę reprezentuje, Bossnie pochodzi z rzeczywistych algorytmów matematycznych, ale z rzeczywistej koncepcji Scopei Code Blockprocedury, podprogramu, metody, funkcji, jednostki tłumaczeniowej itp. Pierwszy algorytm ma 1 zakres, w którym drugi algorytm ma 2 kolejne zakresy.
W pierwszym przypadku na każdym odcinku połączenia Bossidzie do Ai wydaje zamówienie, a następnie Apobiera B'spaczkę, a następnie Bossidzie do Ci daje rozkazy, aby zrobić to samo i odebrać paczkę z Dkażdej iteracji.
W drugim przypadku Bossdziała bezpośrednio, Aaby przejść i pobrać B'spakiet, aż wszystkie pakiety zostaną odebrane. Następnie Bossdziała Ctak samo, aby uzyskać wszystkie D'spakiety.
Ponieważ pracujemy z 8-bajtowym wskaźnikiem i zajmujemy się przydzielaniem sterty, rozważmy następujący problem. Powiedzmy, że Bossjest 100 stóp od, Aa to Ajest 500 stóp od C. Nie musimy się martwić o to, jak daleko Bosspoczątkowo jest to z Cpowodu kolejności wykonywania. W obu przypadkach Bosspoczątkowo podróżuje od Apierwszego do następnego B. Ta analogia nie oznacza, że odległość ta jest dokładna; jest to po prostu przydatny scenariusz testowy, który pokazuje działanie algorytmów.
W wielu przypadkach podczas przydzielania sterty i pracy z pamięcią podręczną i plikami stron odległości te między lokalizacjami adresów mogą się nie różnić tak bardzo lub mogą się znacznie różnić w zależności od rodzaju typów danych i rozmiarów tablicy.
Przypadki testowe:
Pierwszy przypadek: przy pierwszej iteracjiBossmusi początkowo przejść 100 stóp, aby przekazać dowód zamówienia,AiAznika, i robi swoje, ale potemBossmusi przebyć 500 stóp,Caby dać mu dowód zamówienia. Następnie przy następnej iteracji i każdej innej iteracji po tymBossmusi iść w tę iz powrotem 500 stóp między nimi.
Drugi przypadek:Boss ma do przebycia 100 stóp na pierwszej iteracji doA, ale po tym, on już tam jest i tylko czekaA, aby wrócić aż wszystkie zrazy są wypełniane. NastępnieBossmusi przejechać 500 stóp przy pierwszej iteracji do,CponieważCjest 500 stóp odA. PonieważBoss( Summation, For Loop )jest to wywoływane zaraz po pracy,Aon po prostu czeka tam, tak jak to zrobił,Aaż do wykonania wszystkichC'sodcinków zamówienia.
Różnica w przebytych odległościach
const n = 100000
distTraveledOfFirst = (100 + 500) + ((n-1)*(500 + 500);
// Simplify
distTraveledOfFirst = 600 + (99999*100);
distTraveledOfFirst = 600 + 9999900;
distTraveledOfFirst = 10000500;
// Distance Traveled On First Algorithm = 10,000,500ft
distTraveledOfSecond = 100 + 500 = 600;
// Distance Traveled On Second Algorithm = 600ft;
Porównanie wartości arbitralnych
Łatwo zauważyć, że 600 to znacznie mniej niż 10 milionów. Nie jest to do końca dokładne, ponieważ nie znamy faktycznej różnicy odległości między adresem pamięci RAM lub z którego pamięci podręcznej lub pliku strony każde wywołanie każdej iteracji będzie spowodowane wieloma innymi niewidocznymi zmiennymi. Jest to tylko ocena sytuacji, na którą należy zwrócić uwagę, i spojrzenie na nią z najgorszego scenariusza.
Z tych liczb wyglądałoby to prawie tak, jakby Algorytm pierwszy był 99%wolniejszy niż algorytm drugi; Jest to jednak tylko Boss'sczęść lub odpowiedzialność algorytmów i nie uwzględnia rzeczywistych pracowników A, B, C, i D, a co mają robić na każdej iteracji pętli. Tak więc praca szefa stanowi jedynie około 15 - 40% całkowitej wykonanej pracy. Większość pracy wykonanej przez pracowników ma nieco większy wpływ na utrzymanie stosunku różnic prędkości między prędkościami około 50-70%
Obserwacja: - Różnice między dwoma algorytmami
W tej sytuacji jest to struktura procesu wykonywanej pracy. Pokazuje to, że przypadek 2 jest bardziej efektywny zarówno od częściowej optymalizacji posiadania podobnej deklaracji funkcji, jak i definicji, gdy tylko zmienne różnią się nazwą i przebytą odległością.
Widzimy również, że całkowita odległość przebyta w przypadku 1 jest znacznie większa niż w przypadku 2 i możemy rozważyć tę odległość przebytą przez nasz współczynnik czasu między dwoma algorytmami. Przypadek 1 wymaga znacznie więcej pracy niż przypadek 2 .
Można to zaobserwować na podstawie dowodów ASMinstrukcji pokazanych w obu przypadkach. Wraz z tym, co już powiedziano o tych przypadkach, nie oznacza to, że w przypadku 1 szef będzie musiał poczekać na oba Ai Cwrócić, zanim będzie mógł wrócić do Akażdej iteracji. Nie bierze również pod uwagę faktu, że jeśli Alub Bzajmuje to bardzo dużo czasu, zarówno obaj, jak Bossi pozostali robotnicy czekają na wykonanie.
W przypadku 2 jedyną bezczynnością jest czas Bosspowrotu pracownika. Nawet to ma wpływ na algorytm.
Zmienione pytania PO
EDYCJA: Pytanie okazało się nie mieć znaczenia, ponieważ zachowanie w znacznym stopniu zależy od rozmiarów tablic (n) i pamięci podręcznej procesora. Więc jeśli jest dalsze zainteresowanie, przeformułowuję pytanie:
Czy mógłbyś zapewnić rzetelny wgląd w szczegóły, które prowadzą do różnych zachowań pamięci podręcznej, co ilustruje pięć regionów na poniższym wykresie?
Interesujące może być również wskazanie różnic między architekturami procesorów / pamięci podręcznej poprzez zapewnienie podobnego wykresu dla tych procesorów.
Odnośnie tych pytań
Jak wykazałem bez wątpienia, istnieje problem leżący u podstaw jeszcze przed zaangażowaniem sprzętu i oprogramowania.
Teraz jeśli chodzi o zarządzanie pamięcią i buforowaniem wraz z plikami stron itp., Które wszystkie działają razem w zintegrowanym zestawie systemów między następującymi elementami:
The Architecture {Sprzęt, oprogramowanie układowe, niektóre sterowniki wbudowane, jądra i zestawy instrukcji ASM}.The OS{Systemy zarządzania plikami i pamięcią, sterowniki i rejestr}. The Compiler {Jednostki tłumaczeniowe i optymalizacje kodu źródłowego}.- A nawet
Source Codesam z zestawem charakterystycznych algorytmów.
Już teraz widać, że nie jest wąskim gardłem, co dzieje się w ciągu pierwszego algorytmu zanim jeszcze zastosować go do dowolnego urządzenia z dowolnym Architecture, OSoraz Programmable Languagew stosunku do drugiego algorytmu. Wystąpił już problem przed zaangażowaniem się we współczesny komputer.
Końcowe wyniki
Jednak; nie można powiedzieć, że te nowe pytania nie mają znaczenia, ponieważ same są i w końcu odgrywają pewną rolę. Wpływają one na procedury i ogólną wydajność, co widać na podstawie różnych wykresów i ocen wielu osób, które udzieliły odpowiedzi i / lub komentarzy.
Jeśli zwrócić uwagę na analogię Boss, a dwóch pracowników Ai Bktórzy mieli pójść i pobrać pakiety Ci Dodpowiednio i rozważa matematycznej notacji dwóch algorytmów w pytaniu; widać bez udziału sprzętu komputerowego, a oprogramowanie Case 2jest w przybliżeniu 60%szybsze niż Case 1.
Gdy spojrzysz na wykresy i wykresy po zastosowaniu tych algorytmów do jakiegoś kodu źródłowego, skompilowaniu, zoptymalizowaniu i wykonaniu przez system operacyjny w celu wykonania ich operacji na danym sprzęcie, możesz nawet zauważyć nieco większą degradację między różnicami w tych algorytmach.
Jeśli Datazestaw jest dość mały, na pierwszy rzut oka może się wydawać, że nie ma aż takiej różnicy. Ponieważ jednak Case 1jest o wiele 60 - 70%wolniejszy niż Case 2możemy spojrzeć na wzrost tej funkcji pod względem różnic w wykonywaniu czasu:
DeltaTimeDifference approximately = Loop1(time) - Loop2(time)
//where
Loop1(time) = Loop2(time) + (Loop2(time)*[0.6,0.7]) // approximately
// So when we substitute this back into the difference equation we end up with
DeltaTimeDifference approximately = (Loop2(time) + (Loop2(time)*[0.6,0.7])) - Loop2(time)
// And finally we can simplify this to
DeltaTimeDifference approximately = [0.6,0.7]*Loop2(time)
To przybliżenie jest średnią różnicą między tymi dwiema pętlami, zarówno algorytmicznymi, jak i operacjami maszyny obejmującymi optymalizacje oprogramowania i instrukcje maszynowe.
Gdy zbiór danych rośnie liniowo, rośnie również różnica czasu między nimi. Algorytm 1 ma więcej pobrań niż algorytm 2, co jest oczywiste, gdy Bossmusi podróżować do przodu i do tyłu maksymalną odległość między Ai Cdla każdej iteracji po pierwszej iteracji, podczas gdy Algorytm 2 Bossmusi jechać Araz, a następnie po Azakończeniu musi podróżować maksymalna odległość tylko jeden raz, jadąc od Ado C.
Próba Bossskupienia się na robieniu dwóch podobnych rzeczy naraz i żonglowaniu nimi w jedną i drugą stronę zamiast skupiania się na podobnych kolejnych zadaniach sprawi, że pod koniec dnia będzie dość zły, ponieważ musiał dwukrotnie podróżować i pracować. Dlatego nie trać zakresu sytuacji, pozwalając szefowi dostać się do interpolowanego wąskiego gardła, ponieważ małżonek szefa i dzieci nie doceniliby tego.
Poprawka: Zasady projektowania oprogramowania
- Różnica między Local Stacki Heap Allocatedobliczenia zasięgu iteracyjny dla pętli, a różnica między ich zwyczajów, ich wydajności i skuteczności -
Algorytm matematyczny, który zaproponowałem powyżej, dotyczy głównie pętli, które wykonują operacje na danych przydzielonych na stercie.
- Kolejne operacje na stosie:
- Jeśli pętle wykonują operacje na danych lokalnie w ramach pojedynczego bloku kodu lub zakresu, który znajduje się w ramce stosu, nadal będzie to miało zastosowanie, ale lokalizacje pamięci są znacznie bliżej tam, gdzie są zwykle sekwencyjne, a różnica w przebytej odległości lub czasie wykonania jest prawie nieistotne. Ponieważ w stercie nie są wykonywane przydziały, pamięć nie jest rozproszona, a pamięć nie jest pobierana przez RAM. Pamięć jest zwykle sekwencyjna i odnosi się do ramki stosu i wskaźnika stosu.
- Podczas wykonywania kolejnych operacji na stosie, nowoczesny procesor buforuje powtarzalne wartości i adresy, utrzymując te wartości w lokalnych rejestrach pamięci podręcznej. Czas operacji lub instrukcji tutaj jest rzędu nanosekund.
- Kolejne przydzielone operacje sterty:
- Kiedy zaczniesz stosować przydziały sterty, a procesor musi pobierać adresy pamięci podczas kolejnych wywołań, w zależności od architektury CPU, kontrolera magistrali i modułów pamięci RAM, czas operacji lub wykonania może być rzędu mikro do milisekundy. W porównaniu z buforowanymi operacjami stosu są one dość powolne.
- Procesor będzie musiał pobrać adres pamięci z pamięci RAM i zazwyczaj wszystko w magistrali systemowej jest wolne w porównaniu do wewnętrznych ścieżek danych lub magistrali danych w samym CPU.
Kiedy więc pracujesz z danymi, które muszą znajdować się na stercie, i przechodzisz przez nie w pętlach, bardziej efektywne jest utrzymywanie każdego zestawu danych i odpowiadających mu algorytmów w ramach jednej pojedynczej pętli. Uzyskasz lepsze optymalizacje w porównaniu do próby wyodrębnienia kolejnych pętli poprzez umieszczenie wielu operacji różnych zestawów danych znajdujących się na stercie w jednej pętli.
Można to zrobić z danymi znajdującymi się na stosie, ponieważ są one często buforowane, ale nie w przypadku danych, które muszą mieć sprawdzany adres pamięci podczas każdej iteracji.
Tutaj zaczyna się gra Inżynieria oprogramowania i Projektowanie architektury oprogramowania. Jest to umiejętność wiedzieć, jak zorganizować dane, wiedzieć, kiedy je buforować, wiedzieć, kiedy przydzielić dane na stercie, jak zaprojektować i wdrożyć algorytmy oraz wiedzieć, kiedy i gdzie je wywołać.
Możesz mieć ten sam algorytm, który dotyczy tego samego zestawu danych, ale możesz chcieć jednego projektu implementacji dla jego wariantu stosu, a drugiego dla jego wariantu alokacji sterty tylko z powodu powyższego problemu, który wynika z jego O(n)złożoności algorytmu podczas pracy z kupą.
Z tego, co zauważyłem przez lata, wiele osób nie bierze tego pod uwagę. Będą mieli tendencję do projektowania jednego algorytmu, który działa na określonym zbiorze danych i będą go używać niezależnie od tego, czy zbiór danych jest lokalnie buforowany na stosie, czy też został przydzielony na stercie.
Jeśli chcesz prawdziwej optymalizacji, tak, może się to wydawać duplikacją kodu, ale uogólnienie byłoby bardziej wydajne, gdyby dwa warianty tego samego algorytmu. Jedna do operacji na stosie, a druga do operacji na stosie, które są wykonywane w pętlach iteracyjnych!
Oto pseudo przykład: dwie proste struktury, jeden algorytm.
struct A {
int data;
A() : data{0}{}
A(int a) : data{a}{}
};
struct B {
int data;
B() : data{0}{}
A(int b) : data{b}{}
}
template<typename T>
void Foo( T& t ) {
// do something with t
}
// some looping operation: first stack then heap.
// stack data:
A dataSetA[10] = {};
B dataSetB[10] = {};
// For stack operations this is okay and efficient
for (int i = 0; i < 10; i++ ) {
Foo(dataSetA[i]);
Foo(dataSetB[i]);
}
// If the above two were on the heap then performing
// the same algorithm to both within the same loop
// will create that bottleneck
A* dataSetA = new [] A();
B* dataSetB = new [] B();
for ( int i = 0; i < 10; i++ ) {
Foo(dataSetA[i]); // dataSetA is on the heap here
Foo(dataSetB[i]); // dataSetB is on the heap here
} // this will be inefficient.
// To improve the efficiency above, put them into separate loops...
for (int i = 0; i < 10; i++ ) {
Foo(dataSetA[i]);
}
for (int i = 0; i < 10; i++ ) {
Foo(dataSetB[i]);
}
// This will be much more efficient than above.
// The code isn't perfect syntax, it's only psuedo code
// to illustrate a point.
Do tego miałem na myśli osobne implementacje wariantów stosu w porównaniu do wariantów stosu. Same algorytmy nie mają większego znaczenia, to struktury zapętlające, w których będziesz ich używał.
