Prev   Up   Next 21 z 25
Optymalizacja C++
Literatura
Cały ten rodział jest streszczeniem dokumentu Optimizing software in C++: An optimization guide for Windows, Linux and Mac platforms. Podane w tym rozdziale strony odnoszą się to tego manuala.
Optymalizacja a Programowanie Obiektowo Orientowane

We współczesnym programowaniu kładzie się nacisk na obiektowe orientowanie, modularność, wielokrotne wykorzystanie kodu, bezpieczeństwo.

Zaleca się aby funkcje nie były dłuższe niż kilka linii aby było łatwo je testować i utrzymać.

To często utrudnia optymalizację kodu ze względu na szybkość czy rozmiar.

Wybór systemu operacyjnego

Nie ma znaczącej różnicy w szybkości pomiędzy 32 a 64 bitowymi systemami.

64 bitowe systemy :

Windows i Linux w 32-bitach używają tej samej konwencji więc wydajność jest zbliżona.

Mac OS X (na procesorach Intela) może być trochę wolniejszy bo używa domyślnie adresowania relatywnego i późnego łączenia.

Język programowania

Wybór języka programowania:

Kompilator C++

Wybór kompilatora C++:

Wybór bibliotek standardowych: Optimizing software in C++ strona 13.

GCC: -fno-builtin znacznie przyspiesza (zamiast wbudowanego kodu używa wersji bibliotecznych)

Profiler

Aby znaleźć "wąskie gardło" programu można posłużyć się profilerem.

Większość kompilatorów ma swoje profilery. Istnieją też zewnętrzne np. AQtime, Intel VTune, AMD CodeXL, AMD CodeAnalyst.

Rodzaje profilerów:

Czasami najlepsze rezultaty daje własnoręczne dodanie liczników do wybranych funkcji czy miejsc.

Częste problemy z pofilerami:

Gnu profiler gprof

Przykład : test_gprof.c test_gprof_new.c (Pokaż/ukryj kod) 

//test_gprof.c
// gcc -Wall -pg test_gprof.c test_gprof_new.c -o test_gprof
 
#include<stdio.h>
void new_func1(void);
 
void func1(void) {
    printf("\n Inside func1 \n");
    int i = 0;
    for(;i<0x1fffffff;i++);
    new_func1();
}
static void func2(void) {
    printf("\n Inside func2 \n");
    int i = 0;
    for(;i<0x2fffffaa;i++);
}
int main(void) {
    printf("\n Inside main()\n");
    int i = 0;
    for(;i<0xffffff;i++);
    func1();
    func2();
    func1();
    return 0;
}
 

(Pokaż/ukryj kod) 

//test_gprof.c
// gcc -Wall -pg test_gprof.c test_gprof_new.c -o test_gprof
 
#include<stdio.h>
void new_func1(void);
 
void func1(void) {
    printf("\n Inside func1 \n");
    int i = 0;
    for(;i<0x1fffffff;i++);
    new_func1();
}
static void func2(void) {
    printf("\n Inside func2 \n");
    int i = 0;
    for(;i<0x2fffffaa;i++);
}
int main(void) {
    printf("\n Inside main()\n");
    int i = 0;
    for(;i<0xffffff;i++);
    func1();
    func2();
    func1();
    return 0;
}
 

(Pokaż/ukryj kod) 

//test_gprof_new.c
#include<stdio.h>
void new_func1(void) {
    printf("\n Inside new_func1()\n");
    int i = 0;
    for(;i<0x1fffffee;i++);
}
 

Krok 1: Kompilujemy i linkujemy z opcją -pg

gcc -Wall -pg test_gprof.c test_gprof_new.c \
    -o test_gprof

Krok 2: Wykonujemy kod 

./test_gprof
To wygeneruje informacje do pliku gmon.out w bieżącym katalogu.

Krok 3: Analizujemy informacje używając gprof

gprof test_gprof gmon.out > analysis.txt
Parametrami są program który profilujemy oraz plik z wygenerowanymi informacjami.

Plik analysis.txt zawiera zestawienie funkcji posortowanych względem sumarycznego czasu wykonania oraz graf wywołań (która funkcja wywoływała daną funkcję i ile razy).

Gnu profiler gprof

Profilowanie tylko wybranych funkcji

Tylko wybrane pliki kompilujemy z opcją -pg 

gcc -Wall -pg -c test_gprof.c -o test2_gprof.o
gcc -Wall -c test_gprof_new.c -o test2_gprof_new.o
gcc -Wall -pg test2_gprof.o test2_gprof_new.o -o test2

Po uruchomieniu i analizie gprof otrzymujemy plik plik.

Podobny efekt otrzymamy dla funkcji bibliotecznych.

Profilowanie biblioteki linpack

Biblioteka linpack służy do obliczeń numerycznych, dostarcza bardzo wydajnych algorytmów algebry liniowej zooptymalizowanych dla danego systemu i procesora.

Wygenerujemy raport dla jednego z testów wydajnościowych:

Krytyczne czynności

Przed przystąpieniem do optymalizacji kodu należy ustalić gdzie naprawdę znajduje się krytyczne miejsce. Często problem nie leży w wydajności operacji ale np.

Kolizje linii cache
Transpozycja macierzy (Pokaż/ukryj kod) 
#include <iostream>
#include <cstdio>
#include <time.h>
#include <cstdlib>
using namespace std;
 
// Example 9.9a
 
const int SIZE = 512; // number of rows/columns in matrix
//const int SIZE = 513; // number of rows/columns in matrix
const int liczba_powtorzen = 2000; 
 
void transpose(double a[SIZE][SIZE]) { // function to transpose matrix
 // define a macro to swap two array elements:
 #define swapd(x,y) {temp=x; x=y; y=temp;}
 int r, c; double temp;
 for (r = 1; r < SIZE; r++) { // loop through rows
 for (c = 0; c < r; c++) { // loop columns below diagonal
  swapd(a[r][c], a[c][r]); // swap elements
 // swap(a[r][c], a[c][r]); // standard swap elements 
 
 }
 }
}
void test () {
 alignas(64) // align by cache line size
 double matrix[SIZE][SIZE]; // define matrix
 transpose(matrix); // call transpose function
}
 
int main(){
 
	 clock_t start, stop;
   start = clock();
 
   for(int i=0; i<liczba_powtorzen; i++){
		  test();
   }
   stop = clock();
   printf("\n time = %f  ( %d cykli)", (stop - start)*1.0/CLOCKS_PER_SEC, (stop - start));
   return 0;
}
 

Strona 104.

Przechowywanie zmiennych

Należy unikać zmiennych globalnych jeżeli to jest możliwe (lepsze cache'owanie).
Przykłady kiedy jest to wskazane:

Należy też unikać dynamicznego przydziału pamięci:

Lookup tables

Jeżeli zbiór możliwych wartości jest skończony można zastąpić obliczenia lookup table 

int factorial (int n) { // n!
  int i, f = 1;
  for (i = 2; i <= n; i++) f *= i;
  return f;
}
int factorial (int n) {  // n!
  // Table of factorials:
  static const int FactorialTable[13] = {
    1, 1, 2, 6, 24, 120, 720, 5040, 40320, 
    362880, 3628800, 39916800, 479001600};
  if ((unsigned int)n < 13) 
    return FactorialTable[n]; // Table lookup
  else 
    return 0;     // return 0 if out of range
}
Dodanie static const umożliwia optymalizację przez propagacje stałych. 

float a; bool b;
a = b  ? 1.0f : 2.5f;
float a; int b;
static const float lookup[2] = {1.0f, 2.5f};
a = lookup[b];
Nawet jeżeli b jest typu bool nie mamy pewności, że wartość to 0 lub 1, jeżeli pochodzi z niezaufanej funkcji. 

int n;
switch (n) {
  case 0: printf("Alpha"); break;
  case 1: printf("Beta");  break;
  case 2: printf("Gamma"); break;
  case 3: printf("Delta"); break;
}
int n;
static char const * const Greek[4] = {
  "Alpha", "Beta", "Gamma", "Delta"
};
if ((unsigned int)n < 4) { 
  printf(Greek[n]);
}

Sprawdzenie zakresu

const int size = 16; int i;
float list[size];
...
if (i < 0 || i >= size) {
  cout << "Error: Index out of range";
} else {
  list[i] += 1.0f;
}
if ((unsigned int)i < (unsigned int)size) {
  list[i] += 1.0f;
} else {
  cout << "Error: Index out of range";
}

const int min = 100, max = 110;
...
if (i >= min && i <= max) { ...
if ((unsigned int)(i - min) <= (unsigned int)(max - min)) { ...

Sprawdzanie wielu warunków przez operacje bitowe

enum Weekdays {
   Sunday, Monday, Tuesday, Wednesday, 
   Thursday, Friday, Saturday
};
Weekdays Day;
if (Day == Tuesday || Day == Wednesday 
    || Day == Friday) {
  DoThisThreeTimesAWeek();
}
enum Weekdays {
  Sunday = 0x01, Monday = 0x02, Tuesday = 0x04, 
  Wednesday = 0x08, Thursday = 0x10, 
  Friday = 0x20, Saturday = 0x40
};
Weekdays Day;
if (Day & (Tuesday | Wednesday | Friday)) {
  DoThisThreeTimesAWeek();
}

Mnożenie

Jeżeli rozmiary wierszy macierzy są wielokrotnościami dwójki to obliczenia będą szybsze 

const int rows = 10, columns = 8;
float matrix[rows][columns];
int i, j;
int order(int x);
...
for (i = 0; i < rows; i++) {
  j = order(i);
  matrix[j][0] = i;
}

Zapis 

matrix[j][0]
jest zamieniany na 
// ogólny przypadek
(int)&matrix[0][0] + j * (columns * sizeof(float))
 
// rozmiar wiersza jest wielokrotnością dwójki
(int)&matrix[0][0] + j << 5

Czasami sztuczne powiększenie struktury aby jej rozmiar był potęgą dwójki może przyspieszyć działanie programu 

struct S1 {
 int a;
 int b;
 int c;
 int UnusedFiller; // "Sztuczne" wypełnienie
};
int order(int x);
const int size = 100;
S1 list[size]; int i, j;
...
for (i = 0; i < size; i++) {
  j = order(i); // przeglądamy w zadanej kolejności
  list[j].a = list[j].b + list[j].c;
}

Dzielenie

strona 147.

Metaprograming

strona 154.


Tomasz Kapela, Kraków 2011-2020