Wilkening-Online Logo

Performance-Optimierungen in C++



Von Detlef Wilkening
18.04.2012
Version: 1

Hinweis - dieser Artikel entspricht den Folien des Vortrags, den ich am 18.04.2012 auf dem 5-ten C++ Treffen in Düsseldorf gehalten habe.

1. Einführung

1.1 Performance

1.2 Hinweise zu den Tabellen mit den Messwerten

2. Praxis

2.1 Schleifen

2.1.1 Konstante Ausdrücke außerhalb der Schleife berechnen


// Variante 1 - Berechnung innerhalb der Schleife

int fct1(int n, int m)
{
   int res = 0;
   for (int i=0; i<65536; ++i)
   {
      res += n*m;
   }
   return res;
}


// Variante 2 - Berechnung ausserhalb der Schleife

int fct2(int n, int m)
{
   int res = 0;
   const int mul = n*m;
   for (int i=0; i<65536; ++i)
   {
      res += mul;
   }
   return res;
}


GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
Innerhalb 1,7 1,0 1,0 1,0 1,1 1,0 1,0
Ausserhalb 1,0 1,0 1,0 1,0 1,0 1,0 1,0

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.1.2 Scope Variablen wiederverwenden


// Variante 1 - immer neue Scope-Variable "s"

void f1(const vector<string>& v)
{
   
   for (unsigned int i=0; i<v.size(); ++i)
   {
      string s(v[i]);
   }
}


// Variante 2 - Variable "s" wiederverwenden

void f2(const vector<string>& v)
{
   string s;
   for (unsigned int i=0; i<v.size(); ++i)
   {
      s=v[i];
   }
}


GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
Neu 1,0 1,0 1,0 1,1 1,1 1,05 1,05
Wiederverwendung 1,0 1,0 1,35 1,0 1,0 1,0 1,0

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.1.3 Schleifen rückwärts statt vorwärts durchlaufen


// Variante 1 - vorwaerts

int fct1(int n)
{
   int res = 0;
   for (int i=0; i<n; ++i) 
   {
      res += i;
   }
   return res;
}


// Variante 2 - rueckwaerts

int fct2(int n)
{
   int res = 0;
   for (int i=n-1; i>=0; --i)
   {
      res += i;
   }
   return res;
}


GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
Vorwärts 1,0 1,0 1,0 1,4 1,4 1,0 1,0
Rückwärts 1,0 1,3 1,0 1,0 1,0 1,0 1,0

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.1.4 Schleifen ausrollen


// Variante 1 - normale Schleife

int fct1(int n)
{
   int res = 0;
   for (int i=0; i<n; ++i) 
   {
      res += i;
   }
   return res;
}


// Variante 2 - Schleife für 2 Werte

int fct2(int n)
{
   int res = 0;
   for (int i=0; i<n-1; i+=2) 
   {
      res += i + i + 1;
   }
   if (n%2)
      res += n-1;
   return res;
}


// Variante 3 - Schleife für 3 Werte

int fct3(int n)
{
   int res = 0
   for (int i=0; i<n-2; i+=3) 
   {
      res += i + i + 1 + i + 2;
   }
   int rest = n%3;
   if (rest==1)
      res += n - 1;
   else if (rest==2)
      res += n + n - 3;
   return res;
}


// Variante 4 - Schleife für 10 Werte
// Achtung - Case-Bloecke absichtlich ohne "break"

int fct4(int n)
{
   for (int i=0; i<n-9; i+=10) 
   {
      res += 10*i + 45;
   }
   switch (n%10) 
   {
   case 9:
      res += n - 9;
   case 8:
      res += n - 8;
   case 7:
      res += n - 7;
   case 6:
      res += n - 6;
   case 5:
      res += n - 5;
   case 4:
      res += n - 4;
   case 3:
      res += n - 3;
   case 2:
      res += n - 2;
   case 1:
      res += n - 1;
   }
   return res;
}


GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
Schleife 1-fach 7,3 5,2 8,8 9,0 9,1 5,2 5,7
Schleife 2-fach 4,2 4,3 4,5 4,2 4,3 4,3 3,5
Schleife 3-fach 3,8 2,8 3,0 2,8 2,9 2,9 2,6
Schleife 10-fach 1,0 1,0 1,0 1,0 1,0 1,0 1,0

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.2 Sprünge

2.2.1 Fallunterscheidungen sortieren

2.2.2 Sprung-Tabellen nutzen


// Variante 1 - switch

int fct1(const vector<e>& v)
{
   int res = 0;
   for (int i=0; i<int(v.size()); ++i)
   {
      switch (v[i])
      {
      case e1:
         res += f1();
         break;
      case e2:
         res += f2();
         break;
      case e3:
         res += f3();
         break;
      case e4:
         res += f4();
         break;
      case e5:
         res += f5();
         break;
      case e6:
         res += f6();
         break;
      case e7:
         res += f7();
         break;
      case e8:
         res += f8();
         break;
      case e9:
         res += f9();
         break;
      }
   }
   return res;
}


// Variante 2 - switch sortiert

int fct2(const vector<e>& v)
{
   int res = 0;
   for (int i=0; i<int(v.size()); ++i)
   {
      switch (v[i])
      {
      case e9:
         res += f9();
         break;
      case e6:
         res += f6();
         break;
      case e7:
         res += f7();
         break;
      case e3:
         res += f3();
         break;
      case e8:
         res += f8();
         break;
      case e5:
         res += f5();
         break;
      case e4:
         res += f4();
         break;
      case e2:
         res += f2();
         break;
      case e1:
         res += f1();
         break;
      }
   }
   return res;
}


// Variante 3 - if/else

int fct3(const vector<e>& v)
{
   int res = 0;
   for (int i=0; i<int(v.size()); ++i)
   {
      if (v[i]==e1)
      {
         res += f1();
      }
      else if (v[i]==e2)
      {
         res += f2();
      }
      else if (v[i]==e3)
      {
         res += f3();
      }
      else if (v[i]==e4)
      {
         res += f4();
      }
      else if (v[i]==e5)
      {
         res += f5();
      }
      else if (v[i]==e6)
      {
         res += f6();
      }
      else if (v[i]==e7)
      {
         res += f7();
      }
      else if (v[i]==e8)
      {
         res += f8();
      }
      else if (v[i]==e9)
      {
         res += f9();
      }
   }
   return res;
}


// Variante 4 - if/else sortiert

int fct4(const vector<e>& v)
{
   int res = 0;
   for (int i=0; i<int(v.size()); ++i)
   {
      if (v[i]==e9)
      {
         res += f9();
      }
      else if (v[i]==e6)
      {
         res += f6();
      }
      else if (v[i]==e7)
      {
         res += f7();
      }
      else if (v[i]==e3)
      {
         res += f3();
      }
      else if (v[i]==e8)
      {
         res += f8();
      }
      else if (v[i]==e5)
      {
         res += f5();
      }
      else if (v[i]==e4)
      {
         res += f4();
      }
      else if (v[i]==e2)
      {
         res += f2();
      }
      else if (v[i]==e1)
      {
         res += f1();
      }
   }
   return res;
}


// Variante 5 - Array mit Funktions-Zeigern

int fct5(const vector<e>& v)
{
   static array<int(*)(), 9> fcts = { f1, f2, f3, f4, f5, f6, f7, f8, f9 };

   int res = 0;
   for (int i=0; i<int(v.size()); ++i)
   {
      res += fcts[v[i]]();
   }
   return res;
}


// Variante 6 - Map mit Funktions-Zeigern

int fct6(const vector<e>& v)
{
   static map<e, int(*)()> fcts;
   if (fcts.empty())
   {
      fcts[e1] = f1;
      fcts[e2] = f2;
      fcts[e3] = f3;
      fcts[e4] = f4;
      fcts[e5] = f5;
      fcts[e6] = f6;
      fcts[e7] = f7;
      fcts[e8] = f8;
      fcts[e9] = f9;
   }

   int res = 0;
   for (int i=0; i<int(v.size()); ++i)
   {
      res += fcts[v[i]]();
   }
   return res;
}


GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
switch --- --- 1,6 --- --- 1,4 1,4
switch sortiert --- --- 1,4 --- --- 1,5 1,1
if/else --- --- 1,9 --- --- 3,2 2,7
if/else sortiert --- --- 1,2 --- --- 1,3 1,0
Array --- --- 1,0 --- --- 1,0 1,8
Map --- --- 3,3 --- --- 4,5 6,6

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.2.3 Vererbung statt Fallunterscheidungen


// Variante 1 - switch ueber Typ-Enumeration

struct A
{
   Type type;
};

void fct1(A& a)
{
   switch (a.type)
   {
   case BType:
      fb(a);
      break;
   case CType:
      fc(a);
      break;
   }
}


// Variante 2 - Vererbung

struct A
{
   virtual ~A() {}
   virtual void f() = 0;
};

struct B : A
{
   virtual void f() { fb(*this); }
}

struct C : A
{
   virtual void f() { fc(*this); }
}

void doit(A& a)
{
   a.f();
}

2.2.4 Sprünge minimieren


// Variante 1 - Originalcode

int fct1()
{
   int res = 0;
   if (i%2) res += f1();
   res += f2();
   if (i%2) res += f3();
   res += f4();
   if (i%2) res += f5();
   res += f6();
   return res;
}


// Variante 2 - weniger Spruenge, aber Code-Verdopplung

int fct2()
{
   int res = 0;
   if (i%2)
   {
      res += f1();
      res += f2();
      res += f3();
      res += f4();
      res += f5();
      res += f6();
   }
   else
   {
      res += f2();
      res += f4();
      res += f6();
   }
   return res;
}


GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
Original 1,3 1,3 1,3 1,3 1,3 1,6 1,5
Optimiert 1,0 1,0 1,0 1,0 1,0 1,0 1,0

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.2.5 Sprünge vermeiden


// Variante 1 - Wandlung mit If-Anweisung (Sprung)

char fct1(int v)
{
   assert(v>=0);
   assert(v<16);
   if (v>9)
      return 'A'+v-10;
   return '0'+v;
}


// Variante 2 - Wandlung mit Array-Zugriff

char fct2(int v)
{
   assert(v>=0);
   assert(v<16);
   return "0123456789ABCDEF"[v];
}


GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
If-Anweisung 1,3 1,3 1,3 1,3 1,3 1,1 1,0
Array-Zugriff 1,0 1,0 1,0 1,0 1,0 1,0 1,0

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.3 Funktionen

2.3.1 Korrekte Übergabe-Art

2.3.1.1 Vergleich Übergabe elementarer Datentypen per "cbv" und "cbcr"

GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
char cbv 1,0 1,0 1,0 1,0 1,0 1,0 1,0
char cbcr 1,2 1,0 1,1 1,1 1,0 1,0 1,0
short cbv 1,0 1,0 1,0 1,0 1,0 1,0 1,0
short cbcr 1,2 1,0 1,1 1,1 1,0 1,0 1,0
int cbr 1,0 1,0 1,0 1,0 1,0 1,0 1,0
int cbcr 1,2 1,0 1,0 1,1 1,0 1,0 1,0
long cbv 1,0 1,0 1,0 1,0 1,0 1,0 1,0
long cbcr 1,2 1,0 1,0 1,1 1,0 1,0 1,0
float cbv 1,0 1,0 1,0 1,0 1,0 1,0 1,0
float cbcr 1,0 1,0 1,0 1,0 1,0 1,0 1,0
double cbv 1,0 1,0 1,0 1,0 1,0 1,0 1,0
double cbcr 1,0 1,0 1,0 1,0 1,0 1,05 1,0
long double cbv 1,2 1,0 1,0 1,0 1,0 1,0 1,0
long double cbcr 1,0 1,0 1,0 1,0 1,0 1,05 1,0

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.3.1.2 Vergleich Übergabe von Klassen per "cbv" und "cbcr"

GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
1 x int - cbv 1,4 1,2 1,2 1,2 1,1 1,8 1,0
2 x int - cbcr 1,0 1,0 1,0 1,0 1,0 1,0 1,0
2 x int - cbv 1,6 1,3 1,4 1,5 1,5 2,0 1,0
2 x int - cbcr 1,0 1,0 1,0 1,0 1,0 1,0 1,0
3 x int - cbv 1,8 1,7 2,2 2,3 2,1 2,1 1,0
3 x int - cbcr 1,0 1,0 1,0 1,0 1,0 1,0 1,0
4 x int - cbv 2,2 1,7 2,5 2,8 2,2 2,2 1,0
4 x int - cbcr 1,0 1,0 1,0 1,0 1,0 1,0 1,0

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.3.1.3 Vergleich Übergabe eines Shared-Pointers per "cbv" und "cbcr"

GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
Shared-Ptr cbv 2,1 10,2 7,8 16,0 39,0 8,1 8,1
Shared-Ptr cbcr 1,0 1,0 1,0 1,0 1,0 1,0 1,0

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.3.2 Parallele Funktionen implementieren


// Variante 1 - nur String-Funktion

struct A
{
   bool name_match(const string& s) const
   {
      return name_==s;
   }

   string name_;
};


// Variante 2 - parallele Funktion

struct B
{
   bool name_match(const string& s) const
   {
      return name_==s;
   }

   bool name_match(const char* p) const
   {
      return name_==p;
   }

   string name_;
};


GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
Nur String 8,4 5,2 6,4 2,1 4,5 3,5 4,5
Parallele Fkt 1,0 1,0 1,0 1,0 1,0 1,0 1,0

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.3.3 Return Wert Optimierung


// Variante 1 - RVO Normallform

A fct1(int n1, int n2, int n3, int n4)
{
   return A(n1, n2, n3, n4);
}

int main()
{
   A a(fct1(1, 2, 3, 4));
}


// Variante 2 - RVO in Anweisung

A fct2(int n1, int n2, int n3, int n4)
{
   return A(n1, n2, n3, n4);
}

int main()
{
   A a;
   a += fct2(1, 2, 3, 4);
}


// Variante 3 - RVO benanntes Objekt

A fct3(int n1, int n2, int n3, int n4)
{
   A a(n1, n2, n3, n4);
   return a;
}

int main()
{
   A a(fct3(1, 2, 3, 4));
}


// Variante 4 - RVO, Setter

A fct4(int n1, int n2, int n3, int n4)
{
   A a;
   a.set(n1, n2, n3, n4);
   return a;
}

int main()
{
   A a(fct4(1, 2, 3, 4));
}


// Variante 5 - Referenz-Parameter

void fct5(A& a, int n1, int n2, int n3, int n4)
{
   a.set(n1, n2, n3, n4);
}

int main()
{
   A a;
   fct5(a, 1, 2, 3, 4);
}


GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
RVO Normalform 1,0 1,0 1,0 1,0 1,0 1,0 1,0
RVO in Anweisung 1,2 1,0 1,0 1,4 1,4 1,2 1,0
Benanntes Objekt 1,3 1,0 1,0 1,2 1,0 1,0 1,0
Obj. mit Setter 1,3 1,0 1,0 1,2 1,0 1,0 1,0
Referenz-Parameter 1,0 1,0 1,0 1,0 1,0 1,0 1,0

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.3.4 Alternative Rückgabe-Optimierung


// Variante 1 - Kopie-Rueckgabe

string name_as_copy() const
{
   return "Mein toller Name";
}


// Variante 2 - Referenz-Rueckgabe

const string& name_as_reference() const
{
   static string s("Mein toller Name");
   return s;
}


GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
Kopie 50,0 29,1 38,6 42,1 33,3 21,6 61,5
Referenz 1,0 1,0 1,0 1,0 1,0 1,0 1,0

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.3.5 Funktions-Objekte statt Funktionen


// Variante 1 - Funktion

bool my_lt(int arg1, int arg2)
{
   return arg1<arg2;
}

vector<int> v = { ... };
sort(v.begin(), v.end(), my_lt);


// Variante 2 - Funktions-Objekt

struct MyLt
{
   bool operator()(int arg1, int arg2) const
   {
      return arg1<arg2;
   }
};

vector<int> v = { ... };
sort(v.begin(), v.end(), MyLt());


// Variante 3 - Funktions-Objekt mit Boost-Lambda-Library (BLL)

#include <boost/lambda/lambda.hpp>
using namespace boost::lambda;

vector<int> v = { ... };
sort(v.begin(), v.end(), _1<_2);


// Variante 4 - C++11 Lambda-Ausdruck

vector<int> v = { ... };
sort(v.begin(), v.end(), [](int arg1, int arg2) { return arg1<arg2; });


GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
Funktion 3,2 2,6 2,6 2,2 2,2 2,3 2,3
Fkt-Objekt 1,0 1,0 1,0 1,0 1,0 1,0 1,0
BLL 4,9 1,0 1,0 1,0 1,0 1,0 1,0
C++11 Lambda --- --- --- --- --- 1,0 1,0

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.4 Kopien

2.4.1 Schleifen-Elemente als Referenz auslegen


// Variante 1 - Kopie

string::size_type fct1(const vector<string>& v)
{
   string::size_type res = 0;
   vector<string>::const_iterator it = v.begin();
   vector<string>::const_iterator eit = v.end();
   for (; it!=eit; ++it)
   {
      string s = *it;
      res += s.length();
   }
   return res;
}


// Variante 2 - Const-Referenz

string::size_type fct1(const vector<string>& v)
{
   string::size_type res = 0;
   vector<string>::const_iterator it = v.begin();
   vector<string>::const_iterator eit = v.end();
   for (; it!=eit; ++it)
   {
      const string& s = *it;
      res += s.length();
   }
   return res;
}


GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
Kopie 80,0 62,0 12,3 47,0 15,0 21,0 20,7
Const-Referenz 1,0 1,0 1,0 1,0 1,0 1,0 1,0

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.4.2 Temporäre Objekte bei der Addition verhindern


// Variante 1 - Operator +

string fct1(const string& s1, const string& s2, const string& s3, const string& s4)
{
   return s1 + s2 + s3 + s4;
}


// Variante 2 - Operator +=

string fct2(const string& s1, const string& s2, const string& s3, const string& s4)
{
   string s = s1;
   s += s2;
   s += s3;
   s += s4;
   return s;
}


// Variante 3 - Operator += und reserve

string fct2(const string& s1, const string& s2, const string& s3, const string& s4)
{
   string::size_type len = s1.length() + s2.length() + s3.length() + s4.length();
   string s;
   string s.reserve(len);
   s += s1;
   s += s2;
   s += s3;
   s += s4;
   return s;
}


GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
Operator + 1,9 3,1 3,1 5,6 7,2 2,4 2,5
Operator += 1,0 2,2 2,2 2,6 3,3 2,6 2,6
+= & reserve 1,0 1,0 1,0 1,0 1,0 1,0 1,0

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.4.3 Nutze "swap" statt einer Zuweisung


// Variante 1 - Zuweisung

void fct1(string& s)
{
   string res("abcdefghijklmnopqrstuvwxyz");
   res += "12345678901234567890123456789012345678901234567890";
   s = res;
}


// Variante 2 - swap

void fct1(string& s)
{
   string res("abcdefghijklmnopqrstuvwxyz");
   res += "12345678901234567890123456789012345678901234567890";
   s.swap(res);
}


GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
Zuweisung 1,4 1,5 1,3 1,1 1,2 2,1 2,1
swap 1,0 1,0 1,0 1,0 1,0 1,0 1,0

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.5 Speicher-Management

2.5.1 Lokalen Speicher (Stack) bevorzugen


// Variante 1 - lokale Variable

void fct1()
{
   char a[100];
}


// Variante 2 - alloca

void fct2()
{
   char* p = (char*)alloca(100);
}


// Variante 3 - Heap

void fct3()
{
   char* p = new char[100];
   delete [] p;
}


GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
Lokale Var. 1,0 1,0 1,0 1,0 1,0 1,0 1,0
Alloca 1,4 1,3 1,3 1,25 1,25 3,5 3,5
Heap - new 45,0 32,0 26,6 43,0 43,0 37,3 35,5

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.5.2 Nutze "reserve" bei möglichen Typen

2.6 Lokalität

Cache-Struktur aktueller Computer

2.6.1 Daten linear durchlaufen

Array-Durchlauf aus Sicht des Speichers

// Variante 1 - linearer Speicher-Durchlauf

int fct1(const array<array<int, 8192>, 1024>& a)
{
   int res = 0;
   const size_t ei = a.size();
   const size_t ej = a[0].size();
   for (size_t i=0; i<ei; ++i)
   {
      for (size_t j=0; j<ej; ++j)
      {
         res += a[i][j];
      }
   }
   return res;
}


// Variante 2 - sprunghafter Speicher-Durchlauf

int fct2(const array<array<int, 8192>, 1024>& a)
{
   int res = 0;
   const size_t ei = a[0].size();
   const size_t ej = a.size();
   for (size_t i=0; i<ei; ++i)
   {
      for (size_t j=0; j<ej; ++j)
      {
         res += a[j][i];
      }
   }
   return res;
}


GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
Linear 1,0 1,0 1,0 1,0 1,0 1,0 1,0
Sprunghaft 22,2 22,1 23,9 26,0 25,5 19,6 19,7

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.6.2 Daten lokal packen


// Variante 1 - Daten lokal gepackt

const int size = 8192;

struct A
{
   A();
   int  a[size];
   int* p[size];
};

A::A()
{
   for (int i=0; i<size; ++i) 
   {
      a[i] = i;
      p[i] = &a[i];
   } 
}

int fct1(const A& a)
{
   int res = 0;
   for (int i=0; i<size; ++i)
   {
      res += *a.p[i];
   }
   return res;
}


// Variante 2 - Daten verstreut

const int size = 8192;

struct B
{
   B();
   ~B();
   int* p[size];
};

B::B()
{
   for (int i=0; i<size; ++i) 
      p[i] = new int(i);
}
  
B::~B()
{
   for (int i=0; i<size; ++i) 
      delete p[i];
}

int fct2(const B& b)
{
   int res = 0;
   for (int i=0; i<size; ++i)
   {
      res += *b.p[i];
   }
   return res;
}


GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
Lokal 1,0 1,0 1,0 1,0 1,0 1,0 1,0
Gestreut 6,8 8,2 13,3 5,9 6,1 7,2 7,8

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.6.3 Bandbreite durch Packen optimieren

Speicher-Layouts verschiedener Objekte
GCC 2.95 GCC 4.1 GCC 4.6 MS 2003 MS 2005 MS 2010 MS 11Beta
Gepackt 1,0 1,0 1,0 1,0 1,0 1,0 1,0
Ungepackt 1,2 1,2 1,2 1,2 1,2 1,2 1,2

Achtung - bei der Interpretation der Messergebnisse vergessen Sie bitte nicht die Hinweise aus Kapitel 1.2.

2.7 Lokalität & Algorithmen

Performance für das Sieb-des-Eratosthenes mit und gegen Cache-Größe

3. Fazit

4. Profiler

Zum Messen der Performance nimmt am Besten einen Profiler - das sind Tools, die speziell für diesen Anwendungsfall erstellt sind. Hier eine alphabetische Liste der mir bekannten C++ Profiler und Profiling-Bibliotheken - Stand: 18.04.2012.

5. Literatur

6. Links

7. Versions-Historie

Die Versions-Historie dieses Artikels:
Schlagwörter: