Faster Code « C++Guns

29.01.2015

Five Myths about C++ BUSTED!

Filed under: Allgemein — Tags: Cpp, Faster Code — Thomas @ 03:01

This is a short of http://www.stroustrup.com/Myths-final.pdf

Myth 1: “To understand C++, you must first learn C”

C is almost a subset of C++, but it is not the best subset to learn first because C lacks the notational
support, the type safety, and the easier-to-use standard library offered by C++ to simplify simple tasks.
Consider a trivial function to compose an email address:

Busted!

Myth 2: “C++ is an Object-Oriented Language”

3. Myth 2: “C++ is an Object-Oriented Language”
C++ supports OOP and other programming styles, but is deliberately not limited to any narrow view
of “Object Oriented.” It supports a synthesis of programming techniques including object-oriented and
generic programming. More often than not, the best solution to a problem involves more than one style
(“paradigm”). By “best,” I mean shortest, most comprehensible, most efficient, most maintainable, etc.

Busted!

Myth 3: “For reliable software, you need Garbage Collection”
In short:
Never use new or delete. Use some classes which does the memory management for you, e.g. std::vector. For short living object, create them on the stack, Instead on the heap with new. Use destructor to clean up memory (and other resources like file handles) if the lifetime of an object comes to an end.

If you have to pass an object around, don't use raw pointer. If it is possible, don't use pointer at all. If there exist only one owner at a time, use the move magic with rvalue reverences. If the object is shared by more than one owner, use std::shared_pointer to store a pointer. It implements a reference counting and deletes the object of nobody owns them anymore. Use auto and make_shared<> for syntactic sugar.

Naked deletes are dangerous – and unnecessary in general/user code. Leave deletes
inside resource management classes, such as string, ostream, thread, unique_ptr, and shared_ptr.

For resource management, I consider garbage collection a last choice, rather than “the solution” or an ideal:
1.Use appropriate abstractions that recursively and implicitly handle their own resources. Prefer such objects to be scoped variables.
2. When you need pointer/reference semantics, use “smart pointers” such as unique_ptr and
shared_ptr to represent ownership.
3. If everything else fails (e.g., because your code is part of a program using a mess of pointers
without a language supported strategy for resource management and error handling), try to
handle non-memory resources “by hand” and plug in a conservative garbage collector to handle
the almost inevitable memory leaks.

Busted!

Myth 4: “For efficiency, you must write low-level code”

I have seen sort run 10 times faster than qsort. How come? The C++ standard-library sort is
clearly at a higher level than qsort as well as more general and flexible. It is type safe and parameterized
over the storage type, element type, and sorting criteria. There isn’t a pointer, cast, size, or a byte in
sight. The C++ standard library STL, of which sort is a part, tries very hard not to throw away information. This makes for excellent inlining and good optimizations.

Generality and high-level code can beat low-level code. It doesn’t always, of course, but the sort/qsort comparison is not an isolated example. Always start out with a higher-level, precise, and type safe version of the solution. Optimize (only) if needed.

Busted!

Myth 5: “C++ is for large, complicated, programs only”

C++ is a big language. The size of its definition is very similar to those of C# and Java. But that does not
imply that you have to know every detail to use it or use every feature directly in every program.

After all, C++ is designed for flexibility and generality, but not every
program has to be a complete library or application framework.

Busted!

Read the paper for detailed examples.
Busted!!

Comments Off

02.01.2015

raw speed of C using OO with C++

Filed under: Allgemein — Tags: C, Cpp, Faster Code — Thomas @ 20:01

Programs written in C are very very fast. Those written in C++ can be slower due to the fact that copying object is not alway easy as copying an array of numbers. One have to call the copy constructor maybe with side effects like allocate some space.

The language C++ is full backwards compatible to C. So what must we do to use classes and objects with the copy speed of C?

First of all, in C there exist so called POD (plan old data) types like integers, floating point numbers as well as structs und unions. The C language have no class keyword. But classes in C++ can be POD too under certain circumstances. What exactly we need to get a class POD can be read in the C++11 Standard or under [1].
The great benefit of POD types is that it can be copied by simply moving bytes in RAM from one location to another. No call to constructors is needed. That speed up copying enormously.

Enough theory, lets build our own object oriented POD class!
Let's start with a simple class Point that represent a point in 2D. We want to construct a Point object by passing its x and y coordinate. We also want some getter and setter for the coordinates to make the member variables private.

Here is our first implementation:


#include < iostream >
#include < type_traits >

class Point {
public:
  Point() : x(0), y(0) {}
  Point(double x, double y) : x(x), y(y) {}

  void setX(double x) { this->x = x; }
  void setY(double y) { this->y = y; }
  double getX() const { return x; }
  double getY() const { return y; }

private:
  double x, y;
};

int main() {
  Point p(1,2);
  Point p2;

  std::cout << p.getX() << " " << p.getY() << std::endl;

  return 0;
}

Pretty straight forward, right? Save it under point.cpp and compile it with:

$ g++-4.7 -Wall -Wextra -std=c++11 point.cpp 
$ ./a.out 
1 2

I use as compiler gnu g++ version 4.7 to test backwards compatibility. Current is 4.9.2 and 5.0 will be released soon. But you can use any compiler as long it supports c++11. Except for g++ 4.6 thats too old.

To test of a type id POD c++11 provides a simple test [2] which is defined in header file "type_traits". Add this line to our main() function, recompile and run again


std::cout << std::boolalpha;
std::cout << "Point is POD " << std::is_pod::value << "\n";

$ g++-4.7 -Wall -Wextra -std=c++11 point.cpp 
$ ./a.out
1 2
Point is POD false

This shouldn't be too much surprising. As mentioned earlier there are strict rules for when a type is POD. For example the class must be a TrivialType [3]. We can test with is_trivial().


std::cout << "Point is TrivialType " << std::is_trivial::value << "\n";

$ g++-4.7 -Wall -Wextra -std=c++11 point.cpp 
$ ./a.out
1 2
Point is POD false
Point is trivial false

A TrivialType in turn must be TriviallyCopyable [4] and must have Trivial default constructor [5]. Lets test these:


std::cout << "Point is TriviallyCopyable " << std::is_trivially_copyable::value << "\n";
std::cout << "Point is trivially default-constructible " << std::is_trivially_default_constructible::value << "\n";

...

Unfortunately g++ 4.9 does not implement these tests. So we have to wait for version 5.
Instead we can have a closer look about what a "Trivial default constructor" is.

The default constructor for class T is trivial (i.e. performs no action) if all of the following is true:

The constructor is not user-provided (that is, implicitly-defined or defaulted)

T has no virtual member functions

T has no virtual base classes

T has no non-static members with brace-or-equal initializers

Every direct base of T has a trivial default constructor

Every non-static member of class type has a trivial default constructor

Right the first condition does not hold. We provide a user default constructor which simply set x and y to zero. Lets remove this constructor and see whats happen:

$ g++-4.7 -Wall -Wextra -std=c++11 point.cpp 
point.cpp: In function ‘int main()’:
point.cpp:20:9: error: no matching function for call to ‘Point::Point()’
point.cpp:20:9: note: candidates are:
point.cpp:7:3: note: Point::Point(double, double)
point.cpp:7:3: note:   candidate expects 2 arguments, 0 provided
point.cpp:4:7: note: constexpr Point::Point(const Point&)
point.cpp:4:7: note:   candidate expects 1 argument, 0 provided
point.cpp:4:7: note: constexpr Point::Point(Point&&)
point.cpp:4:7: note:   candidate expects 1 argument, 0 provided

It seems we don't have any default constructor anymore. Only the explicit user defined with two arguments and the implicit copy constructor. Thats right. That c++ standard say, that when a explicit user constructor is provided, the compiler don't have to create default constructors.

With the new 2011 standard we can explicit request a implicit default constructor!
Replace this line with the following:


Point() : x(0), y(0) {}
Point() = default;

$ g++-4.7 -Wall -Wextra -std=c++11 point.cpp 
$ ./a.out 
1 2
Point is POD true
Point is TrivialType true

Congratulations! We have a object oriented class that is as fast as old C style stuff.

One important note: Variables in C are not automatic initialized! So our class Point is also not default initialized! See [6] for details. You have to call a constructor explicit e.g.
Point p = Point();

Here is some nice code to make sure your types are POD. If something goes wrong and the
type is not POD, it gave an compiler error


#if __cplusplus >= 201103L
static_assert(!std::is_polymorphic::value, "Please do not add virtual functions to class Point!");
static_assert(std::is_pod::value, "Class Point is not POD!");
#endif

The #if __cplusplus stuff is to check if the compiler has enabled c++11 standard.
Did you know that gnu g++ has set __cplusplus simply to 1 and this bug was know over 10 years?! The reason is very simple: If they fix it, they broke solaris 8. See [7]. Stupid non standard compliant solaris 8 code!

You can download the example code here point.cpp.zip

[1] http://en.cppreference.com/w/cpp/concept/PODType
[2] http://en.cppreference.com/w/cpp/types/is_pod
[3] http://en.cppreference.com/w/cpp/concept/TrivialType
[4] http://en.cppreference.com/w/cpp/concept/TriviallyCopyable
[5] http://en.cppreference.com/w/cpp/language/default_constructor
[6] http://en.cppreference.com/w/cpp/language/default_initialization
[7] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=1773

todo:
*Ich glaube ja nicht daran, dass das Vorhandensein eines Konstruktors den Code langsamer macht.
*Eine Sache, die ich unterstreichen würde, ist, dass in C++ "harmlos" aussehender Code sehr ineffizient sein kann
*Für so eine Behauptung muss man schon vernünftige Benchmarks zeigen
*C++-03 noch kein Moven ga

Comments Off

07.10.2014

Faster Code – Part 6 – Sprungvorhersage - anschaulich

Filed under: Allgemein — Tags: C, Cpp, Faster Code — Thomas @ 12:10

Sehr schöne anschauliche Erklärung:

http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array

Comments Off

28.03.2013

Qt Source und kleine Perlen

Filed under: Allgemein — Tags: Cpp, Faster Code, Qt — Thomas @ 23:03

Ich habe in den letzten 3 Tagen viel Qt Source gelesen und da war schon viel Wirr und Krams dabei. Aber auch kleine Perlen wie diese Zeile in QRectF QPolygonF::boundingRect() const zeige
register const QPointF *pd = constData(); for (int i = 1; i < size(); ++i) { ++pd; }

Da kennt ein Performance-Fan das Keyword register. Ich war richtig überrascht und erfreut auch mal ein Stück optimierten Code zu finden.
Erklärung: das Keyword register sagt dem compiler, dass der Pointer bitte die ganze Zeit über in einem CPU Register bleiben soll. Die Registert sind ja die schnellsten Speicher die es in so einer CPU gibt, und da der Pointer in der nachfolgenden Schleife etliche mal benutzt wird, macht das auch Sinn.
Sogar das const keyword ist dabei. Das sagt dem Compiler, dass er diesen Pointer nicht in den Hauptspeicher zurück speicher muss, da er zu 100% nicht verändert worden ist. Und der Zugriff auf den Hauptspeicher ist im Vergleich zu dem Registert bestimmt 1000x langsamer.

++pd;
Selbst bei dieser recht unbedeuteten Zeile Code gibt es etwas zu sagen. Es gibt eine Menge Post im Internet die vermuten, dass ++i schneller sei als i++ [1] [2]. Aber der Compiler wird das schon optimieren. Jedenfalls weiß der Autor von QPolygonF::boundingRect() das, und ich finde es schön :)

[1] http://stackoverflow.com/questions/24853/what-is-the-difference-between-i-and-i
[2] http://stackoverflow.com/questions/24886/is-there-a-performance-difference-between-i-and-i-in-c

Comments (0)

09.04.2012

Faster Code – Part 6 – Sprungvorhersage again

Filed under: Allgemein — Tags: C, Cpp, Faster Code, Linux — Thomas @ 16:04

Wie im letzten Post angekündigt, gibt es jetzt die genauere Analyse meines Tests.
Hier erstmal das Programm:

int mymin(int a, int b) __attribute__ ((noinline));
int mymin(int a, int b)
{
  asm ("");
  if (b < a)
    return b;
  return a;
}

int mymin2(int a, int b) __attribute__ ((noinline));
int mymin2(int a, int b)
{
  asm ("");
  return  b ^ ((a ^ b) & -(a < b)); // min(a, b)
}

int main()
{
    int a = 0;
    int b = 0;
    int c = 0;
    long sum = 0;
    for(int i = 0; i < 1e7; i++) {
        a = rand();
        b = rand();
        c = std::min(a,b);
//        c = mymin1(a,b);
//        c = mymin2(a,b);
        sum+=c;
//        cout << a << " " << b << " " << c << "\n";
    }
    return 0;
}

Wie man sieht, gibt es zwei Funktion die jeweils die kleinere Zahl bestimmen. Einmal durch eine einfache if() Verzweigung und einmal durch eine Rechnung. Die beiden Funktionen sind mit den Attribute noinline [1] und einem inline Assembler Befehl versehen, damit der Compiler sie nicht weg optimiert. Sonst hat valgrind nichts zum messen ;)
Es gibt drei Durchläuft. Einmal mit std::min um die "normale Version" zu vermessen.
Dann meine min Version mit If. Und zum Schluss die Version mit Rechnung.
Compiliert wird immer mit

 g++ -O2  -g -Wall main.cpp

Bei Valgrind schalte ich die Cache Simulation ab, um die Ausführungszeit etwas zu verkürzen

valgrind --tool=cachegrind --branch-sim=yes --cache-sim=no ./a.out

Test 1
Mit std::min

==5210== I   refs:      1,821,485,345
==5210== 
==5210== Branches:        230,216,253  (210,213,194 cond + 20,003,059 ind)
==5210== Mispredicts:         657,699  (    657,279 cond +        420 ind)
==5210== Mispred rate:            0.2% (        0.3%     +        0.0%   )

--------------------------------------------------------------------------------
         Ir          Bc     Bcm         Bi Bim  file:function
--------------------------------------------------------------------------------
880,000,000  80,000,000 645,163          0   0  /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/stdlib/random_r.c:random_r
    353,545      54,035   3,217          0   0  /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/elf/dl-lookup.c:do_lookup_x
    176,933      28,792   2,876      2,144 252  /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/elf/../sysdeps/i386/dl-machine.h:_dl_relocate_object
    138,235      31,695   1,684          0   0  /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/string/strcmp.c:strcmp
    562,727      63,616   1,366          0   0  /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/elf/dl-lookup.c:_dl_lookup_symbol_x

--------------------------------------------------------------------------------
-- Auto-annotated source: /home/kater/qtcode/plaintest/plaintest/main.cpp
--------------------------------------------------------------------------------
        Ir         Bc Bcm Bi Bim 

-- line 13 ----------------------------------------
         .          .   .  .   .  
         .          .   .  .   .  int mymin2(const int& a, const int& b) __attribute__ ((noinline));
         .          .   .  .   .  int mymin2(const int& a, const int& b)
         .          .   .  .   .  {
         .          .   .  .   .    return  b ^ ((a ^ b) & -(a < b)); // min(a, b)
         .          .   .  .   .  }
         .          .   .  .   .  
         .          .   .  .   .  int main()
         7          0   0  0   0  {
         .          .   .  .   .      int a = 0;
         .          .   .  .   .      int b = 0;
         .          .   .  .   .      int c = 0;
         .          .   .  .   .      long sum = 0;
80,000,000 10,000,000   5  0   0      for(int i = 0; i < 1e7; i++) {
10,000,000          0   0  0   0          a = rand();
10,000,000          0   0  0   0          b = rand();
         .          .   .  .   .          c = std::min(a,b);
         .          .   .  .   .          //c = mymin(a,b);
         .          .   .  .   .          sum+=c;
         .          .   .  .   .  //        cout << a << " " << b << " " << c << "\n";
         .          .   .  .   .      }
         .          .   .  .   .      return 0;
        11          0   0  0   0  }

Interessant sind hier nur Conditional branches executed (Bc) and conditional branches mispredicted (Bcm).
Wir haben also 657,699 falsch vorhergesagte Sprünge und 645,163 gehen für die Random Funktion drauf. Der Rest verteilt sich auf diverse Systemfunktionen. Aber es gibt keine falschen Sprünge für std::min. Der Compiler ist gut ;)
Fünf gehen für die For Schleife drauf. Hier erkennt die Sprungvorhersage schnell, dass es eine Schleife ist und nimmt immer den richtigen Weg.

Test 2
Mit mymin; if()

==10996== I   refs:      1,946,482,984
==10996== 
==10996== Branches:        240,216,256  (220,213,197 cond + 20,003,059 ind)
==10996== Mispredicts:       5,658,603  (  5,658,183 cond +        420 ind)
==10996== Mispred rate:            2.3% (        2.5%     +        0.0%   )

--------------------------------------------------------------------------------
         Ir          Bc       Bcm         Bi Bim  file:function
--------------------------------------------------------------------------------
880,000,000  80,000,000   645,163          0   0  /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/stdlib/random_r.c:random_r
520,000,000 120,000,000        15          0   0  /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/stdlib/random.c:random
180,000,000           0         0          0   0  /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/stdlib/rand.c:rand
140,000,015  10,000,000         9          0   0  /home/kater/qtcode/plaintest/plaintest/main.cpp:main
120,001,144           0         0          0   0  /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/string/../sysdeps/i386/i686/multiarch/strcspn.S:???
 84,997,627  10,000,000 5,000,895          0   0  /home/kater/qtcode/plaintest/plaintest/main.cpp:mymin(int, int)

--------------------------------------------------------------------------------
-- Auto-annotated source: /home/kater/qtcode/plaintest/plaintest/main.cpp
--------------------------------------------------------------------------------
        Ir         Bc       Bcm Bi Bim 

         .          .         .  .   .  #include 
         .          .         .  .   .  #include 
         .          .         .  .   .  using namespace std;
         .          .         .  .   .  
         .          .         .  .   .  
         .          .         .  .   .  int mymin(int a, int b) __attribute__ ((noinline));
         .          .         .  .   .  int mymin(int a, int b)
30,000,000          0         0  0   0  {
34,997,627 10,000,000 5,000,895  0   0    asm ("");
         .          .         .  .   .    if (b < a)
         .          .         .  .   .      return b;
         .          .         .  .   .    return a;
20,000,000          0         0  0   0  }
         .          .         .  .   .  
         .          .         .  .   .  int mymin2(int a, int b) __attribute__ ((noinline));
         .          .         .  .   .  int mymin2(int a, int b)
         .          .         .  .   .  {
         .          .         .  .   .    asm ("");
         .          .         .  .   .    return  b ^ ((a ^ b) & -(a < b)); // min(a, b)
         .          .         .  .   .  }
         .          .         .  .   .  
         .          .         .  .   .  int main()
         8          0         0  0   0  {
         .          .         .  .   .      int a = 0;
         .          .         .  .   .      int b = 0;
         .          .         .  .   .      int c = 0;
         .          .         .  .   .      long sum = 0;
80,000,000 10,000,000         9  0   0      for(int i = 0; i < 1e7; i++) {
20,000,000          0         0  0   0          a = rand();
10,000,000          0         0  0   0          b = rand();
         .          .         .  .   .  //        c = std::min(a,b);
30,000,000          0         0  0   0          c = mymin(a,b);
         .          .         .  .   .  //        c = mymin2(a,b);
         .          .         .  .   .          sum+=c;
         .          .         .  .   .  //        cout << a << " " << b << " " << c << "\n";
         .          .         .  .   .      }
         .          .         .  .   .      return 0;
        12          0         0  0   0  }

Jetzt sieht die Sache schon anders aus. Wir haben fünf Millionen falsch vorhergesagte Sprünge. Das macht 50%. Wie es zu erwarten war.

Test 3
Mit der Rechnung:

==11057== I   refs:      1,991,485,357
==11057== 
==11057== Branches:        230,216,256  (210,213,197 cond + 20,003,059 ind)
==11057== Mispredicts:         657,699  (    657,279 cond +        420 ind)
==11057== Mispred rate:            0.2% (        0.3%     +        0.0%   )

--------------------------------------------------------------------------------
         Ir          Bc     Bcm         Bi Bim  file:function
--------------------------------------------------------------------------------
880,000,000  80,000,000 645,163          0   0  /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/stdlib/random_r.c:random_r
520,000,000 120,000,000      11          0   0  /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/stdlib/random.c:random
180,000,000           0       0          0   0  /build/buildd-eglibc_2.11.2-10-i386-GapcyD/eglibc-2.11.2/stdlib/rand.c:rand
140,000,015  10,000,000       5          0   0  /home/kater/qtcode/plaintest/plaintest/main.cpp:main
130,000,000           0       0          0   0  /home/kater/qtcode/plaintest/plaintest/main.cpp:mymin2(int, int)

--------------------------------------------------------------------------------
-- Auto-annotated source: /home/kater/qtcode/plaintest/plaintest/main.cpp
--------------------------------------------------------------------------------
        Ir         Bc Bcm Bi Bim 

-- line 9 ----------------------------------------
         .          .   .  .   .    asm ("");
         .          .   .  .   .    if (b < a)
         .          .   .  .   .      return b;
         .          .   .  .   .    return a;
         .          .   .  .   .  }
         .          .   .  .   .  
         .          .   .  .   .  int mymin2(int a, int b) __attribute__ ((noinline));
         .          .   .  .   .  int mymin2(int a, int b)
40,000,000          0   0  0   0  {
70,000,000          0   0  0   0    asm ("");
         .          .   .  .   .    return  b ^ ((a ^ b) & -(a < b)); // min(a, b)
20,000,000          0   0  0   0  }
         .          .   .  .   .  
         .          .   .  .   .  int main()
         8          0   0  0   0  {
         .          .   .  .   .      int a = 0;
         .          .   .  .   .      int b = 0;
         .          .   .  .   .      int c = 0;
         .          .   .  .   .      long sum = 0;
80,000,000 10,000,000   5  0   0      for(int i = 0; i < 1e7; i++) {
20,000,000          0   0  0   0          a = rand();
10,000,000          0   0  0   0          b = rand();
         .          .   .  .   .  //        c = std::min(a,b);
         .          .   .  .   .  //        c = mymin(a,b);
30,000,000          0   0  0   0          c = mymin2(a,b);
         .          .   .  .   .          sum+=c;
         .          .   .  .   .  //        cout << a << " " << b << " " << c << "\n";
         .          .   .  .   .      }
         .          .   .  .   .      return 0;
        12          0   0  0   0  }

Wie zu erwarten war gibt es keine fünf Millionen falsch vorhergesagten Sprünge. Wir sind so gut wie die Compiler Optimierung. Gebracht hats also nix ;)
Man bräuchte mal ein realen Anwendungsfall.
Ach ein Nachteil hat die Methode zur Berechnung der kleinsten Zahl: Man kann keine Reference auf die kleinste Zahl zurück geben. Kein Plan wie der Compiler das macht. It's magic.

[1] http://gcc.gnu.org/onlinedocs/gcc/Function-Attributes.html#index-g_t_0040code_007bnoinline_007d-function-attribute-2561

Comments (0)

06.04.2012

Faster Code – Part 6 – Sprungvorhersage

Filed under: Allgemein — Tags: C, Cpp, Faster Code, Linux — Thomas @ 19:04

Es ist ja so, dass ein Befehl auf der CPU nicht nur ausgeführt wird, er muss auch aus dem Speicher geladen und dekodiert werden. Heutige CPUs dekodieren schonmal den nächsten Befehl, wärend der aktuelle noch ausgeführt wird. Und der übernächste wird zeitgleich aus dem Speicher geholt. Das nennt man Prozessor-Pipeline [1] und das ist cool.

Uncool wird es allerdings, wenn der CPU Befehle vorbereitet hat, die dann doch garnicht ausgeführt werden. Das passiert zum Beispiel bei Sprüngen, wenn auf einmal der Code woanders weiter geht als die Pipeline es erwartet hat. Da gibt es auch wieder eine Menge Techniken um die Sprungvorhersage gut zu machen. Aber das will ich nicht weiter vertiefen.

Betrachten wir lieber folgendes Beispiel:


int min(int a, int b) {
  if (b < a)
    return b;
  return a;
}

Hier kann die Sprungvorhersage nichts tun. Was ist wahrscheinlicher, dass a kleiner ist als b oder doch nicht? Die Wahrscheinlichkeit liegt bei 50%. Wäre es nicht cool, wenn man die kleinere Zahl ausrechnen könnte? Dann braucht man keine Verzweigung im Programmpath und die Pipeline kann wunderschön arbeiten.

Man kann. Es gibt eine Seite mit lauter Bit Twiddling Hacks [2]. Und da gibt es noch viel mehr:

Compute the sign of an integer

Detect if two integers have opposite signs

Compute the integer absolute value (abs) without branching

Compute the minimum (min) or maximum (max) of two integers without branching

Determining if an integer is a power of 2

Um das Minimum zweier Interger Zahlen zu berechnen, kann man also folgende Formel verwenden:


int x;  // we want to find the minimum of x and y
int y;   
int r;  // the result goes here 

r = y ^ ((x ^ y) & -(x < y)); // min(x, y)

Um das ganze mal zu testen habe ich mir ein kleines Programm geschrieben, welches die kleinere von zwei Zufallszahlen bestimmt. Leider, oder zum Glück, wird die Funktion std::min() weg optimiert, so dass man keine Aussage mehr treffen kann, ob die Sprungvorhersage greift oder nicht. Also habe ich meine eigne min() Funktion geschrieben. Einmal mit einer if() und einmal mit der Rechnung.
Valgrind [3] bringt ein branch-prediction Profiler mit. Die Bedienung ist einfach und das Ergebnis eindeutig. Da ich euch nicht langweilen will, hier gleich das Ergebnis:

Ja, wenn man Zufallszahlen benutzt, stimmt die Sprungvorhersage zu 50% nicht.

Ja, obrige Formel funktioniert und es gibt keine falsche Sprungvorhersage mehr

Nein, das Programm wurde nicht schneller. Der Test ist einfach zu simpel. Das berechnen der Zufallszahlen wird wohl der Flaschenhals sein.

Nein, obrige Formel bringt eigentlich nix. Der Compiler hat die std::min() wohl so gut optimiert, dass es keine Sprünge gab. Der erkennt das irgendwie und macht irgendwelche Tricks.

Die Details meines Tests werde ich das nächste Mal posten. Muss das erst etwas aufarbeiten.

[1] http://de.wikipedia.org/wiki/Pipeline_%28Prozessor%29
[2] http://www-graphics.stanford.edu/~seander/bithacks.html
[3] http://valgrind.org/docs/manual/cg-manual.html

Comments (0)

30.03.2012

Faster Code – Part 5 - huge pages

Filed under: Allgemein — Tags: C, Cpp, Faster Code, Linux — Thomas @ 21:03

Tach und Willkommen beim fünften Teil von Faster Code. Heute geht es um huge page. Eine Page ist normal 4kb groß. Eine hugepage hat 2MB, 4MB oder nocht viel mehr. Hoch zu 1GB. Je nach System, CPU u.s.w.
Die Größe ermittelt man so:

$ grep Huge /proc/meminfo 
HugePages_Total:      46
HugePages_Free:       46
HugePages_Rsvd:        0
HugePages_Surp:        0
Hugepagesize:       4096 kB

Wir haben also 4MB hugepage und es wurde 46 pages schon erstellt. Man kann sie so vom System anfordern:

# echo 46 > /sys/kernel/mm/hugepages/hugepages-4096kB/nr_hugepages

Es kann sein, dass man danach doch nicht 46 freie hugepages hat, da das System durch RAM Fragmentierung den angeforderten Speicher nicht am Stück liefern kann. Hier hilft es den Befehl mehrmals auszuführen oder neu zu starten.

Und wozu brauch man das nun?
Na um Translation Lookaside Buffer (TLB) misses zu verringern. Der TLB mappt eine virtuelle Adresse in eine physikalische Adresse um. Also so eine Art Cache der aber nur sehr sehr wenige Einträge halten kann (dafür ist er aber sehr schnell). Wenn man nun auf viele Adresse zugreift, die in Pages liegen die nah beinander liegen, dann läuft der TLB schnell zu und bereits vorhandenen Einträge werden überschrieben. Fehlende Einträge aus einem anderen Cache holen kostet Zeit und das wollen wir nicht.
Wenn wir nun die Page größer machen, liegen mehr Variablen in einer Page und der TLB muss sich weniger merken. Einleuchtend, nicht wahr? ;)

Und wie nutzt man huge pages?
Es gibt verschiedene Methoden. Über das hugepagefs was ich aber umständlich finde, weil man von Hand ein Filesystem noch mountern muss. Dann gibt es seit Kernel 2.6.38 die Transparent Huge Pages (THP). Hier wird der ganze Aufwand im Hintergrund gehalten und man bekommt als User garnichts mehr mit. Man muss auch nicht sein Code änderen.
Ob das System THP benutzt kann man kann man so erfahren

$ cat /sys/kernel/mm/transparent_hugepage/enabled 
always madvise [never]

In meinem Fall also nie. Wenn man sein Speicher normal über malloc/new anfordert, sollte man die Variable auf always stellen. Bei madvise muss noch irgendwo ein Flag übergeben werden. Hab vergessen wo.

Die dritte Möglichkeit ist seinen Speicher per mmap() zu bestellen. Das find ich am besten. Man hat dann mehr Kontrolle was in hugepages landet und was nicht. Hier ein Beispiel:


  #include < sys/mman.h >

  /* Only ia64 requires this */ 
  #ifdef __ia64__
  #define ADDR (void *)(0x8000000000000000UL)
  #define FLAGS (MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB | MAP_FIXED)
  #else
  #define ADDR (void *)(0x0UL)
  #define FLAGS (MAP_PRIVATE | MAP_ANONYMOUS | MAP_HUGETLB)
  #endif

  // versuche speicher per mmap zu holen. wenn das fehlschlaegt nimm new oder valloc
  void *addr = mmap(ADDR, anzKnoten * sizeof(t_knoten_minimal), PROT_READ | PROT_WRITE, FLAGS, 0, 0);
  if (addr == MAP_FAILED) {
    perror("mmap");
    knoten_minimal = new t_knoten_minimal[anzKnoten];
  } else {
    knoten_minimal = new (addr) t_knoten_minimal[anzKnoten];
  }

Und hats was gebracht?
Jein, ehr nein. Ich hatte kein Testfall wo der TLB der Flaschenhals ist. Ich hab immer recht schnell neue Daten aus dem RAM geholt und wenig mit ihnen gerechnet. Die Leitung zum RAM ist natürlich sehr viel langsamer als der TLB seine neuen Adressen bekommt. Darum gab es so gut wie kein Speedup.
Aber ich werde in meinem nächsten Code die Möglichkeit bereitstellen hugepages einfach zu nutzen.

Comments (0)

28.03.2012

Faster Code – Part 4 – align memory again

Filed under: Allgemein — Tags: C, Cpp, Faster Code, Linux — Thomas @ 09:03

Wie ich im letzten Post erwähnt habe, ist es gut wenn Variablen im RAM ausgerichtet vorliegen. Nun muss man aber
noch bedenken, dass nicht einzelne Variablen aus dem RAM geladen werden, sondern ganze Cache-Zeilen. Nun wäre es doch auch cool, wenn Arrays auf eine Seitenbreite ausgerichtet sind.
Man stelle sich nur mal vor, zwei Threads die auf zwei CPU Kerne laufen, schreiben in Variablen die in der selben Seite/Cache-Zeile liegt. Nun muss doch die Seite/Zeile gegenseitig ausgetauscht werden. Das macht die Sache langsamer.

Um die Seitengröße in Byte festzustellen, gibt es die Funktion int getpagesize (void). Sie beträgt nochmal 4096Byte.
Um eine Adresse die auf eine Seitenbreite ausgerichtet ist zu bekommen, kann man einfach valloc nutzen [1].


  int *a = (int*)valloc(sizeof(int) *1);
  multipleOf(a);

21e0000 multiple of 2  4  8  16  32  4096

Natürlich ist die Adresse auch auf 64 128 u.s.w. ausgerichtet, aber ich habe mir nicht die Mühe gemacht das rauszuschreiben.

Vielleich denken sich jetzt einige: "Schade, dass new von C++ sowas nicht kann". Aber keine Sorge. Es gibt ein Trick, der nennt sich "placement new" [2]
Man kann new einfach einen schon allokierten Speicher übergeben und es wird wie gewohnt ctors etc. ausgerufen.


  class narf {
    public:
      narf() {cout << "narf()\n";}
      ~narf() {cout << "~narf()\n";}
  };

  narf* a = (narf*)valloc(sizeof(narf) *1);
  multipleOf(a);
  a = new (a) narf();
  a->~narf();
  free(a);

$ valgrind  ./a.out 

223c000 multiple of 2  4  8  16  32  4096 
narf()
~narf()

==5788== HEAP SUMMARY:
==5788==     in use at exit: 0 bytes in 0 blocks
==5788==   total heap usage: 1 allocs, 1 frees, 1 bytes allocated
==5788== 
==5788== All heap blocks were freed -- no leaks are possible

Nicht vergessen den dtor von Hand aufzurufen!

[1] http://www.gnu.org/software/libc/manual/html_node/Aligned-Memory-Blocks.html#Aligned-Memory-Blocks
[2] http://www.parashift.com/c++-faq-lite/dtors.html#faq-11.10

Comments (0)

27.03.2012

Faster Code - Part 3 - align memory

Filed under: Allgemein — Tags: C, Cpp, Faster Code, Linux — Thomas @ 18:03

Variablen deren Adressen ein vielfaches von 4Byte (oder 8Byte auf 64Bit???) sind, können schneller aus dem RAM geladen werden. Man sollte also bei oft benutzen Variablen darauf achten und nicht nur blind der Compiler Optimierung vertrauen. Gerade bei Sachen wie SSE ist es gut, wenn die Array Elemente auf 16Byte ausgerichtet sind, da ein SSE Register 128Bit breit ist.

Der GNU Compiler hat ein spezielles Attribut für Variablen [1].

Hier die Funktion die anzeigt, auf wieviel Byte eine Variable ausgerichtet ist:


void multipleOf(void* p) {
  cout << (size_t)p << " multiple of";
  if((size_t)p % 2 == 0)
    cout << " 2 ";
  if((size_t)p % 4 == 0)
    cout << " 4 ";
  if((size_t)p % 8 == 0)
    cout << " 8 ";
  if((size_t)p % 16 == 0)
    cout << " 16 ";
  if((size_t)p % 32 == 0)
    cout << " 32 ";
  cout << endl;
}

Und hier ein paar Beispiele.


  char unalign;
  char __attribute__ ((aligned (4))) align;
  multipleOf(&unalign);
  multipleOf(&align);

140736773522255 multiple of
140736773522252 multiple of 2  4

Die erste Zahl ist immer die Adresse der Variable in Dezimal, damit man besser Kopfrechnen kann. Wie man sieht hat die Variable unalign eine ungerade Adresse -> nicht gut. Aber mit dem aligned Attribut kann man das schnell ändern :).

Soweit ich weiß haben int, long, float, double u.s.w. immer mindestens ein align von 4.

Aber wie sieht das mit den Adressen einzelner Arrayelemente aus?


  struct  Point {
  float x, y, z;
  };

  cout << "sizeof Point " << sizeof(Point) << endl;
  Point p[4];
  multipleOf(p);
  multipleOf(p+1);
  multipleOf(p+2);
  multipleOf(p+3);

sizeof Point 12
140733340474464 multiple of 2  4  8  16  32 
140733340474476 multiple of 2  4 
140733340474488 multiple of 2  4  8 
140733340474500 multiple of 2  4

Das nächste Array Element ist immer 12Byte weiter. So ist die Sache zwar noch auf 4Byte ausgerichtet, aber nicht auf 16Byte wie das für SSE schön wäre. Hier die Lösung:


  struct  __attribute__ ((aligned (32))) Point {
  float x, y, z;
  };

sizeof Point 16
140736307878992 multiple of 2  4  8  16 
140736307879008 multiple of 2  4  8  16  32 
140736307879024 multiple of 2  4  8  16 
140736307879040 multiple of 2  4  8  16  32

In diesem Fall hätte man auch einfach eine vierte Variable "w" in das Strukt einfügen können. Aber ich denke die Ausrichtung in Bytes manuell angeben ist besser. Es steht nämlich niergends geschrieben, dass ein float auch 4Byte hat. Zum Beispiel hat ein int auf einer 64Bit Maschine unter Linux noch 32Bit aber unter Windows 64Bit. Das gibt böse Fehler.

[1] http://gcc.gnu.org/onlinedocs/gcc/Type-Attributes.html

Comments (0)

Faster Code - Part 2

Filed under: Allgemein — Tags: C, Cpp, Faster Code, Linux — Thomas @ 10:03

Es geht um std::vector

Das i-te Element von vector<> a kann statt mit a[i] e?zienter mit
T::iterator ai = a.begin();
T element = *(ai + i);
dereferenziert werden. Dies entspricht der internen Arbeitsweise des Indexoperators, jedoch
erzeugt dieser bei jedem Elementzugri? einen Iterator auf den Anfang des Containers. Gerade
in Schleifen, in denen große Datenströme Element für Element durchlaufen werden, emp?ehlt
es sich, einen Iterator einmalig vor der Schleife anzulegen und als Basisadresse zu verwenden.
Dadurch verdoppelt sich die Performance im Cache und im Speicher können etwa 20 %
Geschwindigkeitszuwachs gemessen werden.

Aus http://www.rrze.uni-erlangen.de/dienste/arbeiten-rechnen/hpc/Projekte/DA_Stengel_cppnuma.pdf Seite 34

Das geht aber wieder gegen die Compiler Optimierung. Leider habe ich mir nicht notiert, wo ich das gelesen habe. Aber wenn man den operator[] benutzt, dann weiß der Compiler, dass man nur durch das Array laufen will. Und nicht irgendwelche Pointerarithmetik.
// edit
Gilt das aber auch für den operator[] einer Klasse und nicht nur für ein RAW Array? Mist, wo hab ich das blos nur gelesen...

Ich habe mal etwas geforscht und folgendes gefunden: in der libstdc++-v3 die mit dem GNU C++ Compiler kommt, wird KEIN Iterator beim Aufruf vom operator[] erzeugt.
gcc-4.7-20120225/libstdc++-v3/include/bits/stl_vector Zeile 755


   // element access
      /**
       *  @brief  Subscript access to the data contained in the %vector.
       *  @param __n The index of the element for which data should be
       *  accessed.
       *  @return  Read/write reference to data.
       *
       *  This operator allows for easy, array-style, data access.
       *  Note that data access with this operator is unchecked and
       *  out_of_range lookups are not defined. (For checked lookups
       *  see at().)
       */
      reference
      operator[](size_type __n)
      { return *(this->_M_impl._M_start + __n); }

_M_start ist also nur ein Pointer der um __n Element weiter gezählt wird. Kein Iterator zu sehen. Das ist aber Pointer Arithmetik und das ärgert den Compiler. Kann man das nicht auch so machen?


 { return _M_impl._M_start[__n]); }

Das wäre dann der [] operator auf ein RAW Array.

Der benutze Compiler im obrigen Pdf ist der 64Bit Intel C/C++-Compiler Version 9.1.049. Und damit wäre der Gnu Compiler schneller. Zumindest in diesem Fall ;) GNU Rockt ;)

Ich habe auch noch ein Codestück von SGI gefunden wo ein Iterator benutzt wird.
http://www.sgi.com/tech/stl/download.html Datei stl_vector.h Zeile 224.


iterator begin() { return _M_start; }
reference operator[](size_type __n) { return *(begin() + __n); }

Der Iterator ist hier nur ein Funktion die ein Pointer zurück gibt. Dieser Funktionsaufruf wird bestimmt weg optimiert.

Micht interessiert wie Intel das implementiert hat.

Comments (0)

Older Posts »

C++Guns – RoboBlog blogging the bot

29.01.2015

02.01.2015

07.10.2014

28.03.2013

09.04.2012

06.04.2012

30.03.2012

28.03.2012

27.03.2012