Witam,
mam takie pytanie. Kiedy chodze wiele razy po 2 wymiarowej tablicy i ja nadpisuje (czasami nadpisujac w miejscach, ktore juz byly wczesniej nadpisane), to lepiej jest sprawdzac powiedzmy:
if(tab[i][y]==0) tab[i][y]=1;
Czy od razu:
tab[i][y]=1;
?
Zaznacze, ze w tablicy poczatkowo sa same 0.
Od razu
tab[i][y]=1;
Bo po co sprawdzać?
A właśnie, że chyba nie do konca ;P
Przed chwila zrobilem testy czasowe, i z wersja:
tab[i][y]=1;
Sredni czas dzialania to 4.10s.
Natomiast z wersja:
if(tab[i][y]==0) tab[i][y]=1;
Sredni czas dzialania to 3.85s.
Oczywiscie ja przeprowadzilem tylko kilka testow, przydaloby sie wiecej, ale prawdpodobnie jednak oplaca sie sprawdzac.
Zauważ, że w pierwszym przypadku jest przypisanie, czyli jedna operacja, a w drugim porównanie i ewentualnie przypisanie, czyli jedna lub dwie operacje.
PS. Jeżeli bardzo zleży ci na szybkości to najlepiej użyć SSE
Nie nie, az tak mi nie zalezy na szybkosci. Ale prawda jest taka, ze oplaca sie sprawdzac - ale na pewno tylko w konkretnych przypadkach, gdzie to nadpisywanie tej samej wartosci zdazalo by sie bardzo czesto. Mysle, ze to ciekawa sprawa, jaki jest prog oplacalnosci takiego zabiegu.
W moim programie akurat oplacalo sie sprawdzac, bo jak widac - czas wykonywania spadl.
Prawdopodobnie dlatego, ze sprawdzanie jest duzo szybsze, niz nadpisywanie, i lepiej jest czasami wykonac dwie operacje i czasami jedna (ale szybsza), niz wykonywac ciagle jedna, ale wolniejsza.
Wersja pierwsza
mov DWORD PTR [rbp-16], 1
wersja druga
mov eax, DWORD PTR [rbp-16]
test eax, eax
jne .L2
mov DWORD PTR [rbp-16], 1
.L2:
Wyraźnie widać, że pierwsza jest szybsza.
lukasz1235 napisał(a)
Wersja pierwsza
mov DWORD PTR [rbp-16], 1
wersja druga
mov eax, DWORD PTR [rbp-16]
test eax, eax
jne .L2
mov DWORD PTR [rbp-16], 1
.L2:
Wyraźnie widać, że pierwsza jest szybsza.
Wyraźnie widać, że nie masz o tym pojęcia. Obie wersje wciągają całą tablicę do cache'u, pierwsza modyfikuje wszystkie linie i wszystkie linie odsyła z powrotem do RAMu, druga odsyła tylko te, które faktycznie musiały zostać uaktualnione. Jeśli tablica jest dostatecznie duża, elementów niezerowych wystarczająco mało to koszt dodatkowego sprawdzenia będzie znacznie niższy niz koszt ciągłego odsyłania każdej kolejnej linii do pamięci fizycznej, co do najszybszych operacji nie należy.
W każdym razie zależy to ściśle od ilości elementów zerowych, a ogólnie wersja pierwsza jest szybsza.
lukasz1235 napisał(a)
ogólnie wersja pierwsza jest szybsza.
Yhy, wiesz to ze szklanej kuli? Od wielu lat procesory potrafią wykonywać wiele operacji równolegle, mają długie potoki, bardzo krótkie pętle są nieefektywne, nie wykorzystują możliwości sprzętu. Istnienie różnicy czasu wykonywania i jej rozmiar zależą od konkretnego modelu procesora, na niektórych procesorach nawet w przypadku pesymistycznym obie pętle mogą mieć podobny czas wykonywania.
OK. Są warunki w których jest szybsza pierwsza opcja, a także warunki w których szybsza jest opcja druga. Zadowolony?
bzyku:
A co to za testy były?
[CIACH!] ojciec:
Bierzesz pod uwagę dwie sytuacje:
Na procku Core 2 E8400 losowe zapisy są szybsze niż nie-sprefetchowane losowe odczyty: Losowe odczyty vs losowe zapisy dzięki temu, że zapisy są dokonywane asynchronicznie (tzn są osobne write-buffery w procesorze, które się tym zajmują).
Wibowit napisał(a)
Jest jeszcze co najmniej jedna sytuacja do brania pod uwagę:
3. Zapis
Tzn po prostu zapis bez odczytu. Wtedy odczytywanie jest zwykle nieopłacalne, no chyba, że np możemy sobie zprefetchować odczyty, a rzadko komórki pamięci zmieniają wartość przy zapisie.
Jasne, pisałem o tym konkretnym przypadku. Póki co mamy do czynienia za zwykłym kodem w C, nie ma kompilatora, który bez udziału użytkownika sam wygeneruje instrukcje z rodziny movnt. Całkowite pominięcie cache'u lub chociaż ręczne kierowanie fetchowaniem znacząco zmienia sytuację.
Nie wiem dokładnie co się dzieje przy tym asynchronicznym zapisie, ale i tak jest szybszy niż nieprefetchowany odczyt. Zakładając (hipotetyczny scenariusz), że mamy np 3 porty do asynchronicznego zapisu wartości i procesor sobie prefetchuje 3 miejsca w pamięci naraz, potem uaktualnia i zapisuje. No chyba, że cache nie jest stricte typu write-back, tzn w pewnych sytuacjach jest "inteligentne".
Tak czy siak, bez prefetchingu, losowy zapis jest szybszy niż losowy odczyt na procesorach z asynchronicznym zapisem. Na procesorach bez asynchronicznego zapisu losowe odczyty i losowe zapisy są tak samo szybkie. Tak wynika z moich testów. A więc jeśli nasz przypadek to tylko i wyłącznie zapis do losowego miejsca w pamięci, a nie chcemy się bawić w ręczny prefetching, to lepiej nie bawić się w odczytywanie wartości i sprawdzanie czy się zmieni. Tak mówi praktyka :P
trzeba zadać pytanie: a co chcemy? czy chcemy
• nadpisywać wartość, czy
• nadpisywać wartość tylko i wyłącznie gdy jest tam zero, pozostawiając inne wartości takie jakie były.
jeśli w tablicy są same zera i jesteśmy tego pewni, to sprawdzanie nie ma sensu.
a jeśli w tablicy nie są zera, to musimy sobie odpowiedzieć na pytanie, co chcemy zrobić.
kod z warunkiem był szybszy być może dlatego, że w tablicy były wartości niezerowe, więc zmodyfikowano mniejszą ilość liczb.