Langsamer ist besser!

Die Programmiersprache C gilt als super schnell und optimal geeignet für Hardware-nahe Aufgaben. Im Internet gibt es reichlich Verweise darauf, wie viel schneller C ist und wie viel langsamer im Gegensatz dazu interpretierte Sprachen sind. Das Problem an solchen Vergleichen ist, dass sie Äpfel mit Birnen vergleichen. Das wird deutlich, wenn man sich das folgende Beispiel ansieht.

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

int main (int argc, char **argv)
{
  int8_t a, b, c;

  a = atoi (argv[1]);
  b = atoi (argv[2]);

  c = a + b;

  printf ("%d\n", c);

  return 0;
}

Das Programm erwartet zwei Zahlen als Argument, addiert sie und gibt das Ergebnis aus. Es lässt sich ohne Fehler und Warnungen übersetzen.

cc -Wall -c -o c-speed.o c-speed.c
cc c-speed.o -o c-speed

Und auf den ersten Blick scheint es ganz gut zu funktionieren.

$ ./c-speed 1 2
3

Auf den zweiten Blick auch noch.

$ ./c-speed 10 20
30

Nur auf den dritten leider nicht mehr.

$ ./c-speed 100 200
44

Das Problem ist, dass für die Speicherung der Zahl 8 Bit verwendet wurden. Integer-Zahlen werden von heutzutage üblichen Architekturen als Zweierkomplement gespeichert. Das bedeutet, dass ein Bit für das Vorzeichen reserviert wird und die restlichen für die Zahl. Der Wertebereich ist somit -128 bis 127. Darin lässt sich eine 100 speichern aber keine 200 und erst recht keine 300.

Die binäre Darstellung der drei Zahlen sieht folgendermaßen aus.

100 ⇒	0 1 1 0 0 1 0 0
200 ⇒	0 1 1 0 0 1 0 0 0
300 ⇒	0 1 0 0 1 0 1 1 0 0

Auf der rechten Seite ist das niedrigstwertige Bit und auf der linken das höchstwertige Bit. Die führende Null gibt an, dass es sich um eine positive Zahl handelt. Für die 200 reichen somit 8 Bit nicht mehr aus, es werden 9 benötigt. Und für die 300 werden schon 10 benötigt.

C ist dieser Sachverhalt völlig egal. Statt den Überlauf zu erkennen wird einfach mit dem weiter gerechnet, was übrig bleibt nachdem die übergelaufenen Bits weggeschmissen wurden. Dafür gibt es auch eine hochtrabende Bezeichnung: rechnen in Restklassenringen. Und das ist etwas völlig anderes als das, was Schülern in Unter- und Mittelstufe als "Rechnen" beigebracht wird.

In diesem konkreten Fall bedeutet es, dass das neunte Bit der 200 und das neunte und zehnte Bit der 300 über Bord gehen. Allerdings kommt es bei der 300 dazu gar nicht erst, weil durch den Wegfall des neunten Bits die 200 negativ wird, weil jetzt das höchste Bit nicht mehr eine Null sondern eine Eins ist.

200 ⇒	0 1 1 0 0 1 0 0 0
	1 1 0 0 1 0 0 0	⇒ -56

Somit entsteht bei der Addition gar kein Überlauf, da C aus der Addition eine Subtraktion macht: 100 + (-56) = 44. Somit wäre erklärt wie C bei der Addition von 100 und 200 auf 44 kommt. Und da C keine Addition sondern eine Restklassen-Addition durchgeführt hat, hat es auch alles richtig gemacht. Dass weder das Restklassen-Ergebnis noch die Erklärung, was genau es denn ist, einem normal sterblichen Anwender irgend etwas bringen, der auf seinem Kontoauszug eine 44 liest, obwohl er gerade 200€ eingezahlt hat und zuvor noch 100€ auf dem Konto waren, dürfte offensichtlich sein.

Ein typischer C-Programmierer wird nun darauf hinweisen, dass man ja auch mehr Bits für die Speicherung von Zahlen verwenden kann. Die Zeiten, dass man mit Prozessoren auskommen musste, die nur 8 Bit verarbeiten konnten sind lange vorbei und somit könnte man zur Speicherung der Zahl int16_t oder int32_t oder int64_t verwenden. Schon int16_t würde für die Speicherung von 100, 200 und 300 völlig ausreichen, da für die 300 nur 10 Bit nötig waren.

Auf den ersten Blick erscheint das einleuchtend aber das ist nicht wirklich eine Lösung für das Problem. Das Problem ist lediglich aufgeschoben und aufgeschoben ist bekannter Weise nicht aufgehoben. Die Aufschiebung besteht darin, dass der Überlauf bei der Verwendung von int16_t nicht mehr bei Zahlen größer als 127 auftritt sondern bei Zahlen größer als 32767. Das Spielchen kann man jetzt weiter treiben und immer größere Wortbreiten verwenden.

8 Bit:	127
16 Bit:	32767
32 Bit:	2147483647
64 Bit:	9223372036854775807
128 Bit:	170141183460469231731687303715884105727
256 Bit:	57896044618658097711785492504343953926634992332820282019728792003956564819967

Die 256 Bit erscheinen auf den ersten Blick recht groß und man könnte auf die Idee kommen, die Wahrscheinlichkeit, dass es in einem Programm, das mit 256 Bit Zahlen arbeitet, zu einem Überlauf kommt, könne man jetzt wirklich vernachlässigen.

Allerdings sollte man sich klar machen, dass es durchaus Anwendungen gibt, bei denen längere Zahlen benötigt werden. Eine RSA-Verschlüsselung mit 256 Bit Zahlen ist heutzutage als lächerlich zu betrachten, da zur Zeit mindestens 2048 Bits benötigt werden, um einigermaßen sicher zu sein. Und ebenso wichtig dürfte der Sachverhalt sein, dass man nicht davon ausgehen darf, dass ein Programm in dem vom Programmierer vorgesehenen Zahlenbereich arbeitet. Jemand, der eine Sicherheitslücke in einer Software aufspüren will, wird selbstverständlich ein Programm gerade mit solchen Eingaben füttern, die außerhalb dessen liegen, was der Programmierer der Software ursprünglich bei der Planung und Entwicklung als normal angesehen hatte.

Das bedeutet, dass das typische Verhalten eines C-Programmierers, Zahlenüberläufe zu ignorieren, ein sehr großes Sicherheitsrisiko darstellt. Die Geschwindigkeit, die man dadurch erreicht, dass man einfach ungenau arbeitet, wird durch Fehler und Sicherheitsprobleme erkauft. Und somit ist die Aussage "C sei schnell" mehr ein Fluch als ein Segen.

Wenn man also Zahlenüberläufe wirklich vermeiden will, dann ist die logische Konsequenz, dass man eine Zahl nicht mehr in etwas speichern kann, das durch den Restklassenring der gerade zur Verfügung stehenden CPU beschränkt ist. Denn genau das macht C. Statt dessen muss man eine Zahl als eine sog. Bignum oder Big-Integer speichern. Das wiederum geht auch in C unter Verwendung der GMP-Bibliothek. Aber dadurch verliert man die sagenumwobene Geschwindigkeit von C, weil eine Zahl nicht mehr mit nur einem CPU-Befehl addiert werden kann. Statt dessen sieht die Rechnung mit Bignums folgendermaßen aus.

1. Dekodierung der Zahl von der in der Bignum-Bibliothek gewählten Kodierung in eine für die verwendete CPU verständliche Darstellung.
2. Durchführung der gewünschten Rechnung unter zu Hilfenahme von diversen von der CPU bereitgestellten Operationen.
3. Codierung der Zahl in die von der Bignum-Bibliothek benötigte Form.

Und dieser Aufwand muss für jede Addition, jede Multiplikation und jede sonstige Rechenoperation gemacht werden. Und damit ist auch sofort klar, dass das alles andere als schnell ist sonder richtig langsam. Und das ist auch gut so. Denn in diesem Fall bedeutet Langsamkeit Richtigkeit.

Wer also der Meinung ist, in C zu programmieren sei eine gute Idee, weil die Programme so schön schnell sind oder die Verwendung des Java-Typs int sei eine gute Idee, weil er so viel schneller als BigInteger ist, dem kann ich nur mein Beileid aussprechen. Die Schnelligkeit von C ist keine Eigenschaft der Sprache, sondern man bezahlt für sie in barer Münze. Heutzutage kann man Exploits wie geschnitten Brot kaufen. Wer also sicher programmieren will, sollte darauf Wert legen, dass seine Programmiersprache keine Werbung damit macht, wie schnell sie sei. Statt dessen gilt beim Programmieren wie in der 30-Zone vor dem Kindergarten:

Langsamer ist besser!