C++Guns – RoboBlog blogging the bot

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

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