nieznany napisał(a)
Nie wiem gdzie to umiescic, bo to temat niezalezny od jezyka wiec niech bedzie tu.
1: majac petle np.
for(i=1; i<5; i++)
for(j=1; j<1000; j++)
A[i,j]=i+j;
i
for(j=1; j<1000; j++)
for(i=0; j<5; i++)
A[i,j]=i+j;
dlaczego pierwsza bedzie szybsza niz druga? Przeciez w obu przpadkach mamy tyle samo wykonan, chyba ze ja czegos nie widze
Owszem, nie widzisz - cache'u procesora i mechanizmu stronnicowania pamięci.
- pierwsza pętla iteruje po kolejnych elemntach kolejnych podtablic - przetwarza całościowo kolejne tablice. Dla procesora jest znacznie łatwiej - ładuje kolejne linie do cache'u i przechodzi przez nie kolejno, pudło trafia się raz na linię - raz na 32 bajty. Od strony stronnicowania zaś jest mniej skakania po stronach, mniej chaotyczne doczytywanie z dysku itd.
- druga pętla pobiera n-ty element kolejnych tablic, skacze chaotycznie po stronach pamięci, ciągle aktualizuje cache...
Cały cyrk polega na tym aby pamięci używać sekwencyjnie, aby operacje były przewidywalne dla procesora, cache jest niemal tak szybki jak rejestry procesora. Odpowiednie użycie pamięci pozwala na optymalne użycie cache'u przez procesor. Swego czasu pisząc ultrawydajny algorytm na SSE dorzuciłem ręczne sterowanie ładowaniem pamięci do cache'u - słownie dwie instrukcje i zmieniłem zapisujące wynik na składujące bezpośrednio w RAM z pominięciem pamięci podręcznej. Konwersja obrazu przy większych bitmapach była nawet 10x szybsza. Poczytaj dokumentacje Intela, przede wszystkim tom o optymalizacji.
Inna sprawa, że skakanie pomiędzy pętlami to dodatkowe utrudnienie dla procesora - in głębsza pętla tym więcej iteracji powinna mieć - mniej nieregularności wykonywania, mniej zmian w dostępie do cache'u... Druga pętle znacznie więcej razy będzie przeskakiwać pomiędzy sprawadzaniem warunków - więcej rozgałęzień, więcej opóźnień.
nieznany napisał(a)
2:
albo dlaczego
for(i=0; i<100; i++)
T[i]=i;
dziala wolniej niz
for(i=0; i<100)
{
T[i++]=i;
T[i++]=i;
}
Hm, masz chyba drobny błąd - aby kody były rónoważne w drugim liczba iteracji powinna być dwukrotnie mniejsza. To tak zwane rozwijanie pętli, sytuacja ma się w sumie podobnie jak poprzednio. Spore znaczenie ma tu praca potokowa - procesor potrafi wykonywać kilka operacji jednocześnie. Skoki powodują wstrzymanie wszystkich strumieni i ich oczyszczenie - strata czasu. Dwukrotnie więcej iteracji to drukrotnie więcej opóźnień. Do tego drugi kod może zostać zoptymalizowany przez kompilator - może on używać np. dwóch rejestrów przez cos równocześnie wpisuje dwie wartości i zwiększa obie o 2. W obecnych czasach rozkazy IA-32 są emulowane - dekodery rozkładają opkody x86 na mikrokod i przekształcają w celu uzyskania lepszej wydajności, tymczasowych rejestrów wewnętrzych zaś jest bodaj 128 /zastępują 8 rejestrów ogólnych przy właściwym wykonywaniu/. Dłuższa iteracja, zawierająca więcej instrukcji daje większe pole manewru w budowaniu 'mikroprogramu' i zarządzaniu cache'm. Idealnym rozwiązaniem jest rozwinięcie pętli do operacji na 2^n bajtów w jednej iteracji, najczęściej mówi się 4 lub 8 operacjach. Duże znaczenie ma też wyrównanie danych - adres danych /w uogólnieniu/ powinien być wielokrotnością rozmiaru danych - dword do 4 itd, ma to związek z ładowaniem danych do cache'u. Najlepsze wyniki daje adres wyrównany do 32 i operacje na 32 bajtach w jednej iteracji /no... jeżeli operujemy na czymś większym - qword czy struktury, np. piksele/.
nieznany napisał(a)
3: albo ze obrazek podzielony wczyta sie szybciej z www niz jako calosc. Przeciez i tak musi pobrac tyle samo danych.
ma to związek z szybkością przesyłania danych w jednym połączeniu, wiele serwerów ma limity itd, różne cuda są. W każdym razie jednoczesne pobieranie na n połączeniach zwykle idzie szybciej /np. omija wspomniane ograniczenia/ niż na pojedynczym.
nieznany napisał(a)
4: albo ze zamiast pojedynczej petli
for
lepiej uzyc do .. while
bo bedzie szybciej.
Zależy, <b>for</b> równie dobrze może być tak samo szybki jak <b>while</b>. <b>do</b>... <b>while</b> sprawdza warunek pod koniec, wszystkie operacje sterujące są odpowiednio 'poustawiane' przez programistę - kompilator niejednokrotnie może to lepiej zoptymalizować. Chociaż jak znam życie to masz na myli coś takiego:
```cpp
int baiji = 69; // czy tam coś wygenerowanego dynamicznie
do {
// ...
} while (--baiji);
Na czym owa sztuczka polega? Predekrementacja ustawia flagi procesora - sprawdzenie czy baiji == 0 odbywa się jakby za darmo, skok warunkowy wykonuje się zależnie od dekrementacji, bez dodatkowych testów.
</quote>
@Fr3m3n: nie zauważyłeś kilku rzeczy ale jak sam na ircu przyznałeś zmęczony jesteś :-)</b>
p.s. takiego indeksowania: A[i,j] nie ma w standardzie, i,j to blok, z którego liczy się tylko ostatni symbol, przyjmijmy, że to pseudokod a w 'prawdziwym' powinno być A[i][j]