C++Guns – RoboBlog blogging the bot

24.01.2019

Installing gcc, g++ and gfortran 8 from source

Filed under: Allgemein — Tags: , , , — Thomas @ 22:01

The procedure is quite the same as for gcc 4.8 as you can see in my older post Installing gcc, g++ and gfortran 4.8 from source

Read the manual.
Download, unpack, switch dir, download, unpack, link.

$ wget ftp://ftp.gwdg.de/pub/misc/gcc/snapshots/LATEST-8/gcc-8-20190118.tar.xz
$ xz -d gcc-8-20190118.tar.xz
$ tar xf gcc-8-20190118.tar
$ gcc-8-20190118/
$ wget ftp://ftp.gmplib.org/pub/gmp-6.1.2/gmp-6.1.2.tar.bz2
$ tar xjf gmp-6.1.2.tar.bz2
$ ln -s gmp-6.1.2 gmp
$ wget https://www.mpfr.org/mpfr-current/mpfr-4.0.1.tar.bz2
$ tar xjf mpfr-4.0.1.tar.bz2
$ ln -s mpfr-4.0.1 mpfr
$ wget https://ftp.gnu.org/gnu/mpc/mpc-1.1.0.tar.gz
$ tar xzf mpc-1.1.0.tar.gz
$ ln -s mpc-1.1.0 mpc

Make a build directory, start configure, start make, wait
$ cd ..
$ mkdir build-gcc-8-20190118
$ cd build-gcc-8-20190118/
$ ../gcc-8-20190118/configure --prefix=/opt/gcc-8 --enable-threads --enable-languages=c,c++,fortran
$ make -j 32
# make install

20.04.2018

C++ Guns: Levenshtein-Distanz - Teil 1

Filed under: Allgemein — Tags: — Thomas @ 07:04

Die Levenshtein-Distanz (auch Editierdistanz) zwischen zwei Zeichenketten ist die minimale Anzahl von Einfüge-, Lösch- und Ersetz-Operationen, um die erste Zeichenkette in die zweite umzuwandeln. Die Laufzeit Komplexität liegt bei quadratisch. Wie schnell ist das? Getestet werden 1000 Sequencen mit 200 Zeichen Länge.

Die erste Implementierung von Wikipedia lasse ich im Debug Modus laufen und komme auf eine Laufzeit von 1700sec! Ein erster Blick in den Profiler zeigt, dass kein Speicher dynamisch allokiert wird, und 40% der Rechenzeit in der innersten doppelten Schleife auftritt. Sowohl von der Anzahl der Instruktionen als auch von den Branch Misses tritt diese Zeile hervor:

v1[j+1] = std::min(v1[j]+1, std::min(v0[j+1]+1, v0[j]+cost));

Die min() Funktion ist natürlich der Hauptgrund für die Branch Misses. So kann die CPU schlecht vorhersagen, wie die Sequenz editiert werden muss. Da hier nur mit Integer gearbeitet wird, kann std::min() durch eine andere Funktion ersetzt werden, welche keine Verzweigung beinhaltet. Dafür kostet sie mehr Rechenpower. Ob sich der Wechsel lohnt, sehen wir später.

Erstmal schalte ich auf Release Modus um, damit die std Funktionen geinlint werden und der Flaschenhals besser hervortritt. Jetzt beträgt die Laufzeit 97.2sec. Mehr als 10mal schneller als im Debug Modus. Und dabei ist nur mit O2 compiliert worden. Ich schalte erst später auf O3 um, wenn ich den Code gut kenne und paar Sachen schon verbessert habe.

Die fragliche Zeile wird jetzt mit 42% Instruktionen und 50% Branch Mispredict angezeigt. Die anderen 50% kommen von der Simplen Kopie von v1 nach v0. Diese Zeile wird in Wikipedia sogar als einfache swap Operation angezeigt. Das kann also besser Implementiert werden. Mit std::swap lassen sich zwei std::vectoren schnell swappen. Die Laufzeit beträgt jetzt 73.6sec ein deutlicher Gewinn!

Die innerste SChleife wird mit nahezu 100% Instruktionen und 96% Branch Mispredict angezeigt. Klar hier passiert ja die meiste Arbeit. Interessanterweise wird bei std::min kein einziger Branch Mispredict mehr angezeigt. Sondern nur beim Schleifenkopf. Nun die innerste Schleife wurde bisher 46901*200=9380200 mal ausgeführt. Und es gab 9380069 Mispredicts. Ist ja klar. Es wird angenommen, dass die Schleife immer läuft. Aber einmal ist sie zu Ende, dann gibt es den Mispredict. Da wir mit festen Sequencelängen rechnen, könnte man die Schleife komplett ausschreiben. Aber das ist in der Praxis wahrscheinlich dann nicht der Fall.

Von den Instruktionen fallen 12% auf den Schleifenkopf. Also die Variable j Vergleichen und Inkrementieren. Der Rest fällt auf den Schleifenkörper. Wenn man genau hinschaut, erkennt man 5 Additionen, 6 Array Zugriffe, 1 Vergleich und 2 mal die min() Funktionen. Plus ein paar Kopieraktionen. Macht zusammen mindestens 14 Operationen. Ob Valgrind pro Operation nun auch eine Instrktion zählt weiss ich nicht, aber man kann ja mal abschätzen. Valgrind hat knapp 26 Milliarden Instruktionen gezählt. Geschätzt komm ich auf 9380200*14= 131 Millionen. Also wird Valgrind wohl wirklich CPU Instruktionen zählen. Na, wär ja auch schlimm wenn nicht ;)

Außer eine Parallelisierung sehe ich jetzt keine großartiges Optimierungspotential. Man kann noch von Hand Richtung SSE arbeiten und auch die Compiler Optimierung O3 versuchen. Aber dynamik Programming Algorithmen sind nunmal von Natur aus langsam. Nur durch eine Sortierung der Sequenzen könnte man noch etwas reißen. Aber das kommt dann im dritten Teil.

Im Anhang der Code.
LevenshteinTerror1.zip

11.05.2017

C++ Guns - Why isn't there a swap function in Fortran and C?

Filed under: Allgemein — Tags: , , — Thomas @ 09:05

Because Fortran and C sucks.
To implement a generic swap function which works for any type and any custom type, one needs templates. Think about usually variables which store a value. Templates are variables which store types. But Fortran and C do not have template techniques. So one must implement a swap function for every type and any future custom type by himself. And pay the cost of a not-inline function call.

With C++ you don't even have to think about it.


template<class T>
inline void std::swap(T& a, T& b) noexcept;

26.01.2016

Evaluation of logical operations

Filed under: Allgemein — Tags: , , — Thomas @ 21:01

Spass mit dem Standard.
Aus dem Fortran 90/95 Standard [1] Kapitel 7.1.7.6.

Evaluation of logical intrinsic operations
The rules given in 7.2.4 specify the interpretation of logical intrinsic operations. Once the
interpretation of an expression has been established in accordance with those rules, the processor
may evaluate any other expression that is logically equivalent, provided that the integrity of
parentheses in any expression is not violated.
NOTE 7.29
For example, for the variables L1, L2, and L3 of type logical, the processor may choose to
evaluate the expression
L1 .AND. L2 .AND. L3
as
L1 .AND. (L2 .AND. L3)
Two expressions of type logical are logically equivalent if their values are equal for all possible
values of their primaries.

Aus dem c++11 Standard [2] Kapitel 5.14

logical-and-expression
The && operator groups left-to-right.

Und die andern Operatoren auch left-to-right.

Aus dem C89 Standard [3] Kapitel 3.3

Except as indicated by the syntax27 or otherwise specified later (for the function-call operator () , && , || , ?: , and comma operators), the order of evaluation of subexpressions and the order in which side effects take place are both unspecified.

hf

[1] http://j3-fortran.org/doc/standing/archive/007/97-007r2/pdf/97-007r2.pdf
[2] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf
[3] https://web.archive.org/web/20050207005628/http://dev.unicals.com/papers/c89-draft.html#3.3

29.05.2015

warning: conversion to 'float' from 'int' may alter its value [-Wconversion] (Bug of the day 7)

Filed under: Allgemein — Tags: , , — Thomas @ 22:05

Another bug of the day :D

You can do the following

float var = float(vari); // yes I know I'm loosing precision
int var = int(std::floor(varf)) // yes I know interger can overflow
int var = qFloor(varf) // Qt version

Same for double.

warning: comparison between signed and unsigned integer expressions [-Wsign-compare]

Tricky one. Usually don't use unsigned types. The world is full of negative value. Use signed types.
Except for..
Array index. To access the full 32/64bit address space, one must use unsigned type.

Let variable data be a pointer/array.
data[i] is the same as data+i
Now variable i should have the same wide as data. Which is size_t. Type size_t is 32bit wide on 32bit system and 64bit otherwise.
New rule: Always use size_t for index variable while accessing data. Don't use int.

Type size_t is an unsiged type.
New rule: Never count backwards in for loops while accessing data.

Consider this endless loop
for(size_t i=data.size(); i >= 0; i--)

If i == 0 and i-- then i == 2^32-1 which is > 0. Damn.
There are a lot of solutions. Bad one and really bad ones. Here is my perfect one: You count forward. That is really easy and everybody understands what is going one and there are no surprises.
In the next line you subtract n-i-1 and volia. Perfect.

for(size_t ri=0; ri < data.size(); ri++) { size_t i = data.size() - ri - 1; I named the new loop variabl ri for reverse iterator. Don't forget to add -1. Arrays start by 0. You can of couse use std::reverse_iterator But hey, I love for loops!

20.05.2015

-1 (Bug of the day 5)

Filed under: Allgemein — Tags: , — Thomas @ 19:05

vector vecB;
vecB.resize(vecA.size()-1);

for(size_t i = 0; i < vecA.size(); ++i) {  
  ...
  vecB[i] = value
  ...
}

Na, wer findet ihn?

Bei so etwas findet ich QT's QVector wieder besser als den Standard c++ vector. Qt macht zumindest bei Debug Einstellung eine Bereichsüberprüfung.

Ausser es wird die at() Funktion statt den operator() benutzt. Dann machen beide eine Bereichsüberprüfung. Aber auch hier zeigen sich kleine Unterschiede welche die Philosophie von Qt und cpp Standardlib zeigen.
Qt bietet nur eine cost Version der Funktion at() an. Der Grund liegt wahrscheinlich im intuitiven Verständnis des Codes.
Ein normaler Vector zugriff wie man das seit Jahrzehnten macht geht so:

vec[i] = value;

Das sieht sieht "komisch" aus:

vec.at(i) = value;

Qt für normale Programmierer mit wenig Schmerzen. c++ std für Profis mit viel Schmerzen :D

16.05.2015

integer overflow debugger trap

Filed under: Allgemein — Tags: , — Thomas @ 08:05

Benutzt man 16bit Integer statt 32bit um Speicher zu sparen und seine cache misses zu optimieren, läuft man Gefahr den Zahlenbereich von -32768 bis +32767 zu verlassen. So wie es für Floatingpoint Zahlen Überprüfungen auf over/underflow etc gibt, die ein Signal werfen bzw den Compiler anspringen lassen, so gibt es das auch für Integer. Ist wohl nur nicht so bekannt.

Für den GNU Compiler gibt es die Option -ftrapv [1]

This option generates traps for signed overflow on addition, subtraction, multiplication operations.

Leider wird nicht erwähnt, dass das Programm nun furchtbar langsamer läuft. Weiterhin scheinen sich noch im Geheimen Fehler zu verbergen die ich nicht ganz verstehe. [2]

When -ftrapv is in effect, libcalls are "necessary" so that the results of an operation can be propagated without making the call to the libgcc functions dead.

Im Prinzip funktioniert das Überprüfen auf Overflows aber ohne große Einbüßen wie dieser Artikel zeigt [3]

How much overhead should we expect from enabling integer overflow checks? Using a compiler flag or built-in intrinsics, we should be able to do the check with a conditional branch that branches based on the overflow flag that add and sub set. Assuming that branch is always correctly predicted (which should be the case for most code), the costs of the branch are the cost of executing that correctly predicted not-taken branch, the pollution the branch causes in the branch history table, and the cost of decoding the branch.
...
result in 3% penalty.
...
John Regehr, who’s done serious analysis on integer overflow checks estimates that the penalty should be about 5%, which is in the same ballpark as our napkin sketch estimate.

Der Artikel "Catching Integer Overflows in C" [4] gibt eine schöne Übersicht über die Techniken der Overflow detections und jener FAQ Eintrag "comp.lang.c FAQ list · Question 20.6b" [5] gibt eine Beispiel Implementierung. Mit dieser Einschränkung:

(Note: these functions all share one bug: they may fail if invoked on the largest negative integer, INT_MI

#include < stdio.h >
#include < limits.h >

int chkadd(int a, int b) {
	if(b < 0)
		return chksub(a, -b);
	if(INT_MAX - b < a) {
		fputs("int overflow\n", stderr);
		return INT_MAX;
	}
	return a + b;
}

int chksub(int a, int b) {
	if(b < 0)
		return chkadd(a, -b);
	if(INT_MIN + b > a) {
		fputs("int underflow\n", stderr);
		return INT_MIN;
	}
	return a - b;
}

int chkmul(int a, int b) {
	int sign = 1;
	if(a == 0 || b == 0) return 0;
	if(a < 0) { a = -a; sign = -sign; }
	if(b < 0) { b = -b; sign = -sign; }
	if(INT_MAX / b < a) {
		fputs("int overflow\n", stderr);
		return (sign > 0) ? INT_MAX : INT_MIN;
	}
	return sign * a * b;
}

Nun möchte man nicht für das komplette Programm die Überprüfung einschalten, sondern z.B. nur für 16bit Integer. Vielleicht implementiere ich einen eigenen Type mit überladenen Funktionen dafür. Irgendwann..

[1] https://gcc.gnu.org/onlinedocs/gcc/Code-Gen-Options.html
[2] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35412
[3] http://danluu.com/integer-overflow/
[4] http://www.fefe.de/intof.html
[5] http://c-faq.com/misc/intovf.html

18.02.2015

rosettacode - Simple moving average

Filed under: Allgemein — Tags: , , — Thomas @ 12:02

http://rosettacode.org/wiki/Averages/Simple_moving_average#C.2B.2B

The original rosetta C example shows the usage of variable function arguments. The C++ example shows how to implement a circular buffer. They are confusing and inefficient. My Version shows how to implement a simple moving average using modern c++ techniques.


#include < iostream >
#include < vector >

class SMA {
public:
    SMA(int period) : values(period), sum(0.0), idx(0), size(0) {
    }

    void add(double value) {
        const size_t period = values.size();
        // here is the magic. Update sum and vector in place
        sum = sum - values[idx] + value;
        values[idx] = value;

        // this implements the circular buffer
        idx = (idx+1)%period;
        if(size+1 <= period) {
            ++size;
        }
    }

    double avg() const {
        return sum/size;
    }

private:
    // store the last seen values
    std::vector values;
    // store the sum. so we dont have to recalculate it every time
    double sum;
    // the next element in the buffer we can override
    int idx;
    // ho many values was allready inserted. This is usually the same as the given periodb
    size_t size;
};

int main() {
    SMA foo(3);
    SMA bar(5);

    std::vector data = { 1, 2, 3, 4, 5, 5, 4, 3, 2, 1 };

    for(auto &val : data) {
        foo.add(val);
        std::cout << "Added " << val << " avg: " << foo.avg() << std::endl;
    }
    std::cout << std::endl;

    for(auto &val : data) {
        bar.add(val);
        std::cout << "Added " << val << " avg: " << bar.avg() << std::endl;
    }

    return 0;
}


02.02.2015

more crazy C

Filed under: Allgemein — Tags: — Thomas @ 09:02

#include

#define CACHE 256
enum { h_unknown = 0, h_yes, h_no };
unsigned char buf[CACHE] = {0, h_yes, 0};

int happy(int n)
{
int sum = 0, x, nn;
if (n < CACHE) { if (buf[n]) return 2 - buf[n]; buf[n] = h_no; } for (nn = n; nn; nn /= 10) x = nn % 10, sum += x * x; x = happy(sum); if (n < CACHE) buf[n] = 2 - x; return x; } int main() { int i, cnt = 8; for (i = 1; cnt || !printf("\n"); i++) if (happy(i)) --cnt, printf("%d ", i); printf("The %dth happy number: ", cnt = 1000000); for (i = 1; cnt; i++) if (happy(i)) --cnt || printf("%d\n", i); return 0; } from http://rosettacode.org/wiki/Happy_numbers#C

02.01.2015

raw speed of C using OO with C++

Filed under: Allgemein — Tags: , , — 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

    Older Posts »

    Powered by WordPress