Problemy z typami danych cz II.

Do pomiaru rozmiaru struktur danych służy operator sizeof(). Sprawdzimy na początek ile pamięci zajmują wybrane standardowe typy danych.

#include <stdio.h>

int main(void)
{
  printf("%d\n", sizeof(char));
  printf("%d\n", sizeof(short));
  printf("%d\n", sizeof(int));
  return 0;
}

Program wypisze nam ile bajtów zajmuje każdy z następujących typów danych: char, short oraz int. Wyniki zwracane przez program będą różne dla różnych architerktur komputerów na których były uruchomione. Polecam uruchomienie tego programu na własnym komputerze. Na moim komputerze wyniki to: 1 bajt dla chara, 2 bajty dla shorta i 4 bajty dla inta.

Zbadamy teraz ile bajtów zajmują zdefiniowane przez nas struktury danych. Zaczniemy od prostej, lecz często stosowanej konstrukcji.

// Przykład 1

struct struktura
{
  char a;
};

sizeof(struktura) == 1;

Wszystko wygląda w porządku. Mamy w strukturze jedną zmienną typu char, która zajmuje 1 bajt. Zatem cała struktura zajmie nam w pamięci 1 bajt. Nic nadzwyczajnego tu się nie dzieje. Przejdźmy do drugiego przykładu.

// Przykład 2

struct struktura
{
  char a;
  short b;
};

sizeof(struktura) == 4;

Tutaj stało się coś dziwnego.. Zmienna char zajmuje 1 bajt, a zmienna short 2 bajty. Zatem intuicyjnie struktura zawierający te dwie zmienne, powinna zajmować 3 bajty. Natomiast sizeof() informuje nas, że struktura zajmuje aż 4 bajty! Czy to błąd kompilatora albo funkcji sizeof? A może celowe działanie? Spróbuję to wytłumaczyć w dalszej części tego artykułu. Na razie przyjrzyjmy się kolejnemu przykładowi:

// Przykład 3

struct struktura
{
  char a;
  int b;
  char c;
};

sizeof(struktura) == 12;

Pewnie spodziewaliśmy się, że i w tym przypadku rozmiar struktury będzie nieco większy niż wynikałoby to z prostej matematyki. Ale że struktura będzie zajmowała dwa razy więcej miejsca niż zmienne w strukturze? I to jeszcze nie koniec! Przyjrzyjmy się kolejnemu przykładowi.

// Przykład 4

struct struktura
{
  char a;
  char c;
  int b;
};

sizeof(struktura) == 8;

Struktura z praktycznego punktu widzenia nie różni się tak bardzo od poprzedniej. I tu i tu mamy po dwa chary i jednego inta. Zmienne nawet w obu przypadkach są tak samo nazwane! Różnica jest jedynie w kolejności w jakiej te zmienne występują. Dzięki tej z pozoru nieistotnej zmianie zyskaliśmy aż 4 bajty w pamięci. Dlaczego tak się dzieje? O tym w kolejnej części.

Problemy z typami danych cz I.

Notka będzie najeżona dużą dawką informacji. Zacznijmy!
Na początek tabelka rozmiarów podstawowych typów danych.

char      1
short     2
int       4 (na 32-bitowych komputerach!)
long long 8

Przyjrzyjmy się bliżej typowi int. Jego zakres to -2³¹ ... 2³¹-1. Warto przy tym wspomnieć, że liczba 2³¹-1 (0x7fffffff) jest liczbą pierwszą. Zapamiętaj to! Znajomość dużych liczb pierwszych przyda Ci się przy kilku algorytmach.
W związku z tym, że mamy o jedną liczbę ujemną więcej niż dodatnią, rodzi się nasz pierwszy problem. Spójrzmy na następujący kod źródłowy programu C++:

int x = -231;
int y = -x;
pritnf("%d\n", y);

Pierwsza linijka nie stanowi żadnego kłopotu (nie licząc tego, że kompilator jej nie zaakceptuje). Druga linia rodzi pewien problem. Teoretycznie zmienna x powinna przyjąć wartość 2³¹. Jednak ta liczba nie mieści się w zakresie inta. Pytanie: Jaką zatem wartość ma zmienna y?
Aby to ustalić spójrzmy jak w systemie binarnym zapisane są wybrane liczby całkowite.

 0    00000000 00000000 00000000 00000000
 1    00000000 00000000 00000000 00000001
-1    11111111 11111111 11111111 11111111
-231  10000000 00000000 00000000 00000000

Prześledźmy działanie operatora unarnego "-":
- Negujemy wszystkie bity liczby
- Dodajemy do liczby jeden
Prześledźmy jak ten operator działa dla powyższych liczb. Zero poprawnie przechodzi na zero. Jeden przechodzi na minus jeden, a minus jeden na jeden. Natomiast -2³¹ przechodzi na... -2³¹. To nie koniec niespodzianek.

Przeanalizujmy następujący program:

printf("%d", 1 << 2);
printf("%d", 1 << 31);
printf("%d", 1 << 32);

Pierwsze dwie linie programu działają według naszych przypuszczeń. Pierwsza linijka wypisze na ekran "4", natomiast druga "-2³¹". Natomiast z trzecią linijką jest kłopot o czym informuje nas już kompilator: "warning: left shift count >= width of type". Na ekranie zostanie wypisane "0". Ale spójrzmy jeszcze na to:

int x = 32;
printf("%d", 1 << x);

Program nie powinien się różnić od poprzedniego przykładu, a jednak. Po pierwsze kompilator nie informuje nas o zagrożeniu (kompilator "nie może wiedzieć" czy wartość x przekracza dozwolony zakres). Po drugie, na ekranie zostanie wypisana "1". Procesor bowiem weźmie resztę z dzielenia liczby x przez 32 i o taką liczbę bitów przesunie 1 w lewo. Trzeba o tym pamiętać i mieć to na uwadze.

W drugiej części przedstawię kolejne problemy, tym razem z własnymi strukturami danych.

Przewidywanie skoków w procesorze

Przeanalizujmy następujący program.

const n = 10000000;
int P[n];

for (int i = 0; i < n; i++)
  scanf("%d", &p[i]);

for (int i = 0; i < n; i++)
{
  if (p[i] < N/2) ++w;
  else ++y;

  if (p[(i+100)%N] < N/2) ++w;
  else ++h;
}

Program na wejściu dostaje permutację liczb 1, 2, ..., n. Program nie liczy nic ciekawego. Ważną rzeczą jest, że dla dowolnej permutacji każda instrukcja w programie zostanie wykonana dokładnie taką samą ilość razy. Mimo to dla permutacji <1, 2, ..., n> program działa szybciej niż dla jakiejkolwiek losowej permutacji:

Losowa permutacja: 4.07 s
Posortowane dane: 3.91 s

Minimalnej różnicy mogliśmy się spodziewać. Czas działania tego programu jest opóźniony przez operację wejścia / wyjścia. Jednak dlaczego program na posortowanych danych działa szybciej?

W każdym programie około 10% instrukcji to skoki. Problemem dla procesora są zwłaszcza tak zwane skoki warunkowe. Gdy procesor wykonuje jakąś komendę, to następne instrukcje już lądują w specjalnej kolejce do tego przeznaczonej. W sytuacji w której wykonujemy skok warunkowy, nie możemy stwierdzić które instrukcje powinny być następnie wykonywane, dopóki nie zostanie sprawdzony warunek. Jednak czekając tak długo tracimy cenne cykle procesora... Jest jednak wyjście z tej sytuacji.

Procesor gdy napotyka na skok warunkowy próbuje "przewidzieć" wynik skoku i odpowiednie instrukcje trafiają do kolejki. Jeśli procesor "zgadł", to instrukcje są wykonywane normalnie. W przeciwnym przypadku instrukcje znajdujące w kolejce są anulowane i wszelkie efekty działania tych instrukcji (tak, tak - procesor czasem wykona te operacje), a do kolejki trafiają poprawne instrukcje.

W sytuacji w której dane są posortowane - procesorowi będzie łatwiej przewidzieć skoki, podczas gdy dla losowych danych takie przewidywania są niemal niemożliwe. Dlatego program dla danych posortowanych działał szybciej.

Jaki jest morał z tego wykładu? Przecież zwykle nie mamy wpływu na dane wejściowe. Zgadza się! Ale czasami chcielibyśmy obliczyć ile program działa w najgorszym wypadku. Mimo, że permutacja <1, 2, ..., n> jest największa z możliwych, a każda instrukcja wykonywana jest w każdej permutacji taką samą ilość razy, to jednak to nie jest najgorsza możliwa permutacja dla tego programu.. Niejeden programista się na tym przejechał.

Mały FAQ dla chcących wiedzieć więcej:
Jak dobrze procesor "przewiduje skoki"? Bardzo dobrze. W zależności od procesora ok 70 - 90%.
Czy gra jest warta świeczki? Czy procesor po prostu nie mógłby poczekać aż zostanie obliczony warunek skoku? Nie! Jeśli w kolejce trzymanych jest 100 operacji to wśród nich jest około 10 skoków! Bez zgadywania w takiej sytuacji procesor byłby 10-krotnie mniej wydajny.
Na podstawie czego procesor przewiduje skoki? Istnieją dwie metody. Pierwsza z nich to metoda statyczna. Każdemu skokowi przyporządkowuje przepowiednię. Faktycznie - dla większości skoków możemy powiedzieć, która z opcji będzie częściej wykonywana po warunku. Druga metoda to metoda dynamiczna. Dla każdego skoku spamiętujemy jego ostatnie wyniki. Na podstawie nich obliczamy naszą "przepowiednię".
Coś więcej na temat algorytmu dynamicznego? Spragnionych wiedzy odsyłam do wyszukiwarki google.

Wierszami czy kolumnami? cz III. (Mnożenie macierzy)

W niniejszej notce omówię algorytm mnożenia macierzy. Jeśli czytelnik z mnożeniem macierzy spotyka się po raz pierwszy to odsyłam do wikipedii (http://pl.wikipedia.org/wiki/Mno%C5%BCenie_macierzy). Operacja mnożenia macierzy jest tam bardzo ładnie wytłumaczona.
Przed napisaniem tej notki wyszukałem w googlach hasło "mnożenie macierzy C++". Pobieżne przejrzenie wyników potwierdziło moje przypuszczenia - zdecydowana większość programistów pisze pętle w złej kolejności. Przedstawmy najpierw typową implementację mnożenia macierzy:

const int N = 1000;
static int T[N][N];
static int A[N][N];
static int B[N][N];

for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
  {
    T[i][j] = 0;
    for (int k = 0; k < N; k++)
      T[i][j] += A[i][k] * B[k][j];
  }

Gdzie leży błąd można na pierwszy rzut oka nie zauważyć. Wytłumaczę to zatem, aby wszyscy mogli to zauważyć, a w razie innego algorytmu - powtórzyć rozumowanie.
Z tablicą T nie ma problemów. Wewnątrz pętli odwołujemy się do elementu T[i][j]. Przy czym przechodzimy ją po wierszach. To znaczy, że pętla iterująca po j-tach znajduje się wewnątrz pętli iterującej po zmiennej i. Podobna sytuacja jest z tablicą A. Odwołujemy się do elementu A[i][k], czyli przechodzimy ją po wierszach (pętla iterująca po zmiennej k znajduje się wewnątrz pętli iterującej po zmiennej i). Problem jest z tablicą B.
W przypadku tablicy B odwołujemy się do elementu B[k][j]. Przechodzimy ją zatem po kolumnach - pętla iterująca po j-tach znajduje się na zewnątrz pętli iterującej po zmiennej k. Procesor zatem nie będzie wczytywał optymalnie tablicy B do pamięci cache.
Możemy to poprawić przestawiając miejscami pętle ze zmienną k z pętlą ze zmienną j. Musimy też stworzyć osobne pętle zerujące tablicę.

const int N = 1000;
static int T[N][N];
static int A[N][N];
static int B[N][N];

for (int i = 0; i < N; i++)
  for (int j = 0; j < N; j++)
    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++)
      T[i][j] += A[i][k] * B[k][j];

Tutaj już wszystko powinno działać w porządku. Wszystkie tablice przechodzimy po wierszach.
Przykład ten jest często wykorzystywany przy omawianiu przechodzenia tablicy po wierszach i kolumnach. Oba algorytmy mają nawet swoje nazwy potoczne. Pierwszy z nich nazywamy algorytmem ijk, natomiast drugi (jak nietrudno się domyślić) ikj.
Czas na przetestowanie obu rozwiązań. Różnica jest odczuwalna:
algorytm ijk - 0:13.63
algorytm ikj - 0:10.45
Motto tego trzy częściowego kursu jest następujące: "Iterowanie po wierszach przyśpiesza program". Czasem o kilka sekund, czasem nawet ośmiokrotnie. Warto o tym pamiętać bo przestawianie dwóch pętli nas nic nie kosztuje.

Wierszami czy kolumnami? cz II.

Szybkość działania programu nie zależy wyłącznie od ilości wykonanych operacji. Na to czy program zadziała szybko ma wpływ wiele innych czynników. Dzisiaj poznamy jeden z nich.
Procesor posiada specjalną pamięć podręczną zwaną pamięcią cache. Jest ona o wiele szybsza od pamięci RAM. Gdy procesor potrzebuje jakiś danych to najpierw sprawdza czy są one dostępne w pamięci cache. Jeśli tak to świetnie! Dostaniemy do nich dostęp bardzo szybko. Jeśli nie - dostęp do tych danych potrwa nieco dłużej. Często będzie nam zależeć na tym, aby ten drugi przypadek starać się wykluczyć.
Procesor stara się przewidzieć jakie dane będą potrzebne w najbliższej przyszłości. Dwa podstawowe warunki jakimi sugeruje się procesor to:

• Jeśli jakiś obiekt był ostatnio używany, to istnieje duże prawdopodobieństwo, że będzie używany w najbliższej przyszłości
• Jeśli jakiś obiekt był ostatnio używany, to istnieje duże prawdopodobieństwo, że w najbliższej przyszłości będą używane obiekty leżące blisko niego
  

Jako elementy "blisko niego" rozumiemy tutaj elementy, które znajdują się koło niego w pamięci RAM (mają podobny adres maszynowy). Zadeklarujmy tablicę dwuwymiarową i sprawdźmy które elementy znajdują się koło których w pamięci. Podejrzewamy, że bezpośrednio koło elementu T[0][0] znajduje się albo element T[0][1], albo T[1][0]. Poniższy program rozwieje nasze wątpliwości.

const int N = 1000;
static char T[N][N];

printf("0x%08x\n0x%08x\n0x%08x\n0x%08x\n",
  &T[0][0], &T[0][1], &T[1][0], &T[0][N-1]);

Po uruchomieniu programu dostałem następujące wyniki (zachęcam do uruchomienia programu na własnym sprzęcie):

0x00404040
0x00404041
0x00404428
0x00404427

Zatem koło adresu T[0][0] znajduje się element T[0][1]. Natomiast element T[1][0] znajduje się o 1000 adresów dalej. Zachęcam do dalszych eksperymentów, w których wykażemy, że koło elementu T[0][1] znajduje się element T[0][2] itd.
Po analizie naszego programu możemy wywnioskować również, że w pamięci po elemencie T[0][N-1] występuje element T[1][0]. Najlepiej iterować tablicę dwuwymiarową w kolejności występowania elementów w pamięci - czyli w kolejności: T[0][0], T[0][1], ..., T[0][N-1], T[1][0], ..., T[N-1][N-1].
Wyjaśniło się nam zatem dlaczego algorytm iterujący po wierszach działa szybciej niż program iterujący po kolumnach. Starajmy się iterować w ten sposób tablice wielowymiarowe zawsze wtedy, kiedy mamy taką możliwość!
W następnej notce przedstawię często spotykany algorytm, w którym stosując poznaną tu sztuczkę zwiększymy szybkość jego działania o kilka sekund.

Wierszami czy kolumnami? cz I.

Zaczniemy od czegoś bardzo prostego. Sztuczkę tą powinni znać wszyscy programiści. Przyjrzyjmy się poniższemu programowi, dynamicznie liczącemu wartość pewnej tablicy.

const int N = 10000;
static int t[N][N];

for (int i = 1; i < N; i++)
  for (int j = 1; j < N; j++)
    t[i][j] = max(t[i-1][j], t[i][j-1], t[i-1][j-1]);

Poniżej prezentuję ten sam program, z przestawionymi dwoma pętlami. Wyniki obu programów są takie same. Dla wyniku w tym przypadku nie ma bowiem znaczenia która pętla jest zewnętrzna a która wewnętrzna

const int N = 10000;
static int t[N][N];

for (int j = 1; j < N; j++)
  for (int i = 1; i < N; i++)
    t[i][j] = max(t[i-1][j], t[i][j-1], t[i-1][j-1]);

Policzmy jednak czasy działania obu programów (jak zwykle w tym miejscu polecam własne eksperymenty w domu). Wynik być może niektórych zaskoczy. Pierwszy program działa 3-4 razy szybciej. Oto przykładowe czasy działania algorytmów na moim sprzęcie:

Algorytm pierwszy - 0:26.26
Algorytm drugi - 1:13.37

Mojemu znajomemu po drobnej modyfikacji kodu udało się uzyskać następujące czasy:

Algorytm pierwszy - 0:01.23
Algorytm drugi - 0:09.67

Czyli pierwszy program działał 8 razy szybciej niż drugi.
Oba programy wykonują jednakową liczbę operacji i liczą dokładnie to samo (tylko w innej kolejności). Zatem dlaczego pierwszy z nich działa o wiele szybciej? Napiszę o tym w następnej notce.