Z poniższych trzech programów pierwszy działa u mnie na komputerze 0,6 sekundy, drugi 4,7 sekundy, a trzeci 1,3 sekundy. Czasy są mniej więcej powtarzalne. Programy kompilowałem z optymalizacją -O2. Dlaczego tak się dzieje?
Program 1: "normalny":
#include <cstdio>
#define N (1 << 13)
int tab[N][N];
int main()
{
long long suma = 0;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
tab[i][j] = i * j;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
suma += tab[i][j];
printf("%lld\n", suma);
return 0;
}
Program 2: "na odwrót":
#include <cstdio>
#define N (1 << 13)
int tab[N][N];
int main()
{
long long suma = 0;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
tab[j][i] = i * j; // tutaj
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
suma += tab[i][j];
printf("%lld\n", suma);
return 0;
}
Program 3: "na odwrót, ale większa tablica":
#include <cstdio>
#define N ((1 << 13) + 1) // tutaj
int tab[N][N];
int main()
{
long long suma = 0;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
tab[j][i] = i * j; // tutaj
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
suma += tab[i][j];
printf("%lld\n", suma);
return 0;
}
Chodzi tu o mądre wykorzystywanie pamięci cache procesora. Szczegółowe wyjaśnienie można znaleźć w artykule Krzysztofa Piecucha z Delty (PDF). Dobre rady dotyczące wykorzystania pamięci cache – w skrócie:
Chcemy pomnożyć dwie macierze rozmiaru n na n. Normalnie zrobilibyśmy to tak jak poniżej. (Przy okazji zwracamy uwagę na reprezentację macierzy jako struct oraz na używanie stałych referencji).
#define N 1000 // na przykład
struct macierz {
int t[N][N];
};
macierz operator*(const macierz& A, const macierz& B) {
macierz C;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j) {
C.t[i][j] = 0;
for (int k = 0; k < N; ++k)
C.t[i][j] += A.t[i][k] * B.t[k][j];
}
return C;
}
W powyższym rozwiązaniu po macierzach A i C chodzimy wierszami, ale po macierzy B – kolumnami. Jeśli jednak zmienimy kolejność pętli, to już będzie dobrze:
#define N 1000 // na przykład
struct macierz {
int t[N][N];
};
macierz operator*(const macierz& A, const macierz& B) {
macierz C;
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
C.t[i][j] = 0;
for (int i = 0; i < N; ++i)
for (int k = 0; k < N; ++k)
for (int j = 0; j < N; ++j)
C.t[i][j] += A.t[i][k] * B.t[k][j];
}
return C;
}
Przy podanych ograniczeniach mamy 3-4-krotny zysk czasowy.
Chcemy wyznaczyć liczbę liczb pierwszych z zakresu między 2 a N, N jest rzędu 108. Można by to zrobić za pomocą sita Eratostenesa, wypełniając wielką tablicę p[N+1] (złożoność czasowa O(N log log(N))), ale wtedy będziemy losowo skakać po ogromnej tablicy, która, zresztą, nie zmieści się w pamięci. Tablicę tę można upchnąć w pamięci za pomocą masek bitowych, ale wciąż będziemy po niej skakać w sposób losowy.
Rozwiązanie przyjazne względem pamięci cache jest takie, żeby podzielić tablicę p na kawałki mieszczące się w cache'u i wykonywać sito na każdym z kawałków z osobna. Rozmiar cache L1 (ten szybszy, bo jest jeszcze cache L2) możemy zazwyczaj sprawdzić tak:
dmesg | grep L1
Można też wyrzucić z rozważań wszystkie liczby parzyste. Więcej szczegółów w artykule Tomka Idziaszka z Delty: Kolejność ma znaczenie.
Rozważmy następujący program, który wczytuje napis złożony z 107 zer i jedynek i zlicza poszczególne cyfry:
#include#define M 10000000 char st[M + 1]; int main() { int x0 = 0, x1 = 0; gets(st); for (int i = 0; i < M; ++i) if (st[i] == '0') ++x0; else ++x1; printf("%d %d\n", a, b); return 0; }
Uruchamiamy powyższy program na dwóch testach. Pierwszy to 5 ⋅ 106 zer i 5 ⋅ 106 jedynek: program działa u mnie średnio 0.085 sekundy. Drugi to taki sam test, tyle że zera i jedynki rozmieszczone są w napisie w losowej kolejności: program działa u mnie średnio 0.125 sekundy, czyli o 50% więcej. Wyniki są powtarzalne. Zauważmy, że w obu przypadkach program wykonuje dokładnie takie same instrukcje, tylko w innej kolejności. O co więc chodzi?
Chodzi tu o przewidywanie skoków w procesorze w ramach przetwarzania potokowego instrukcji. Dokładne wyjaśnienie można znaleźć w artykule Tomka Idziaszka, który za kilka miesięcy ukaże się w Delcie (PDF). Jest to zagadnienie, które zapewne będzie omówione na Architekturze komputera. Nie trzeba się tym bardzo przejmować, ale warto mieć świadomość tego, że w przypadku użycia instrukcji warunkowych takie różnice mogą wystąpić. W powyższym programie takie różnice nie występują, jeśli wyeliminuje się instrukcję warunkową if.
Warto być świadomym, że kompilowanie programów z optymalizacją -O2 może powodować istotne zmiany w ich działaniu. Spośród czterech poniższych programów, tylko czwarty skompilowany z optymalizacją konsumuje więcej niż 64 MB RAM.
Program 1: po prostu duża tablica:
#include <cstdio>
using namespace std;
#define N 100000000
int main()
{
int tab[N];
puts("ABC");
return 0;
}
Program 2: zerujemy:
#include <cstdio>
using namespace std;
#define N 100000000
int main()
{
int tab[N];
for (int i = 0; i < N; ++i)
tab[i] = 0;
puts("ABC");
return 0;
}
Program 3: obliczamy sumę:
#include <cstdio>
using namespace std;
#define N 100000000
int main()
{
int tab[N];
long long suma = 0;
for (int i = 0; i < N; ++i) {
tab[i] = i;
suma += tab[i];
}
printf("%d\n", suma);
puts("ABC");
return 0;
}
Program 4: wreszcie optymalizator nie daje rady:
#include <cstdio>
using namespace std;
#define N 100000000
int main()
{
int tab[N];
long long suma = 0;
for (int i = 0; i < N; ++i) {
tab[i] = i;
if (i >= 3)
suma += tab[i - 3];
}
printf("%d\n", suma);
puts("ABC");
return 0;
}
To w sumie dobrze, że optymalizator jest taki sprytny. Trzeba być jednak świadomym, że w przypadku błędnych programów (np. programy piszące po nieswojej pamięci) program skompilowany z optymalizacją może zwracać inne wyniki niż bez optymalizacji.
Zadanie domowe: implementacja rozwiązania zadania Liczby pierwsze na ASD-SIO.