Joel on Software

Joel on Software   Joel über Software

 

Andere auf Deutsch verfügbare "Joel on Software"-Artikel

Andere auf Englisch verfügbare "Joel on Software"-Artikel

Email an den Verfasser (nur auf Englisch)

 

Zurück zu den Wurzeln


Von Joel Spolsky
Aus dem Englischen von Heinz Kessler
Redigiert von Veronika Caslavsky
11. Dezember 2001

Wir haben eine Menge Zeit auf dieser Site damit verbracht, über so aufregende große Dinge zu sprechen wie .NET versus Java, XML-Strategie, Kundenbindung, Wettbewerbsstrategie, Software-Design, Architektur undsoweiter. All das zusammen kann man sich wie Schichten einer Lasagne vorstellen: Ganz oben haben wir die Software-Strategie, darunter sprechen wir über Architekturen wie .NET, und darunter wiederum, individuelle Produkte: Entwicklungswerkzeuge wie Java oder Plattformen wie Windows.

Gehen wir mal noch tiefer in die Lasagne. DLLs? Objekte? Funktionen? Nein, tiefer! Irgendwann geht es um Codezeilen, die in Programmiersprachen geschrieben sind.

Immer noch nicht tief genug. Heute will ich über CPUs nachdenken. Kleine Siliziumplättchen, die Bytes umherschieben. Stellen Sie sich vor, dass Sie ein Programmier-Anfänger sind. Vergessen Sie all das Wissen, das Sie über Programmieren, Software, Management angesammelt haben und gehen Sie zurück auf die tiefste Ebene des "Von-Neumann"-Zeugs. Streichen Sie J2EE aus Ihrem Gedächtnis für einen Moment, Denken Sie in Bytes.

Vancouver BCWarum tun wir das? Ich glaube, dass die größten Fehler, die bis hin zu den höchsten architektonischen Ebenen gemacht werden davon stammen, dass die Verantwortlichen ein schwaches oder falsches Verständnis von den ganz unteren Ebenen haben. Wir haben einen wundervollen Palast gebaut, aber das Fundament ist eine Katastrophe. Statt aus festem Beton besteht es aus Schutt. Und so sieht der Palast zwar toll aus, nur die Badewanne schliddert ab und an quer durch's Badezimmer und keiner weiß warum.

Also: Atmen Sie tief durch, lassen Sie uns eine kleine Übung machen, die wir mit der Programmiersprache "C" durchexerzieren möchten.

Erinnern Sie sich daran, wie Strings (Zeichenketten) in C funktionieren: sie bestehen aus einem Haufen Bytes, gefolgt von einem "Null"-Zeichen, das den Wert 0 hat. Das hat zwei Auswirkungen:

Man kann nicht wissen, wann der String endet (also wie lang er ist) ohne ihn zu durchlaufen.

Ein String kann keine Nullen enthalten. Infolgedessen kann man kein beliebiges binäres Objekt (blob) darin speichern, zum Beispiel eine JPEG-Grafik.

Warum arbeiten C-Strings so? Weil der PDP-7-Mikroprozessor, auf dem Unix und die C-Programmiersprache entwickelt wurden, einen ASCIZ Datentyp hatte. ASCIZ hieß "ASCII mit einer Null (Zero) am Ende"

Ist das die einzige Art, wie man Strings speichern kann? Nein, tatsächlich ist es die schlechteste Art, es zu tun. Für nicht-triviale Programme, Programmierschnittstellen, Betriebssysteme, Klassenbibliotheken, sollten Sie ASCIZ meiden wie die Pest. Warum?

Beginnen wir, indem wir den Code für strcat schreiben, die Funktion, die einen String an einen anderen anfügt.

void strcat( char* ziel, char* quelle )
{
     while (*ziel) ziel++;
     while (*ziel++ = *quelle++);
}

Studieren Sie den Code ein bisschen und beachten Sie, was hier getan wird. Zuerst durchlaufen wir den ersten String, um sein Null-Endezeichen zu finden. Danach durchlaufen wir den zweiten String und kopieren ein Zeichen nach dem anderen an den Ersten.

Diese Art von String Handling und -Aneinanderreihung war gut genug für Kernighan and Ritchie, aber sie hat ihre Probleme. Hier ist eines davon: Stellen Sie sich vor, sie haben eine ganze Anzahl von Namen, die Sie alle aneinanderreihen und zu einem großen String verbinden möchten:

char grosserString[1000];     /* Ich weiß nie, wieviel ich da nehmen soll... */
grosserString[0] = '\0';
strcat(grosserString,"John, ");
strcat(grosserString,"Paul, ");
strcat(grosserString,"George, ");
strcat(grosserString,"Joel ");

Das funktioniert, stimmt's? Ja, und es sieht nett und sauber aus.

Wie sieht's mit der Performance aus? Ist der Code so schnell wie möglich? Ist es gut skalierbar? Wenn wir eine Million Strings zum Aneinanderfügen hätten, wäre das die richtige Art, es zu tun?

Nein. Dieser Code benutzt den Schlemiel-der-Maler-Algorithmus. Dies ist der Witz über Schlemiel:

Schlemiel bekommt einen Job als Straßenmaler und muss die gestrichelten Linien in der Mitte der Straße malen. Am ersten Tag nimmt er einen Eimer Farbe und schafft bis zum Abend 300 Meter. "Das ist wirklich gut", sagt sein Chef, "du arbeitest schnell" und zahlt ihm eine Kopeke.

Am nächsten Tag schafft Schlemiel nur 150 Meter. "Naja, das ist lange nicht so viel wie gestern, aber du bist immer noch schnell, 150 Meter ist respektabel", und zahlt ihm wieder eine Kopeke.

Am Tag darauf malt Schlemiel 30 Meter. "Was, nur 30?", schimpft sein Boss, "das ist inakzeptabel! Am ersten Tag hast Du zehnmal so viel geschafft! Was ist los?"

"Ich kann nix dafür", sagt Schlemiel. "Jeden Tag bin ich weiter und weiter weg vom Farbeimer!"

kansas(Als Bonus-runde: was sind die richtigen Zahlen?) Dieser lahme Witz illustriert genau was passiert, wenn man strcat so einsetzt, wie ich es oben getan habe. Der erste Teil von strcat muss den Zielstring immer wieder von vorne durchlaufen, um immer und immer wieder das blöde Null-Zeichen zu suchen und deshalb ist die Funktion viel langsamer als sie müsste und skaliert überhaupt nicht gut. Viele Programmteile, die Sie täglich nutzen, haben dieses Problem. Viele Dateisysteme sind so implementiert, dass man bloß nicht zu viele Dateien in ein Verzeichnis packen sollte, weil die Performance dramatisch nachlässt, wenn man Tausende von Elementen in einem Verzeichnis hat. Versuchen Sie einen überfüllten Windows-Papierkorb zu öffnen - es braucht Stunden bis er sich öffnet, was nicht proportional mit der Zahl der Dateien anwächst, die er enthält. Da muss irgendwo der Schlemiel-der-Maler-Algorithmus am Werke sein. Immer wenn sich etwas linear proportional verhalten sollte, aber in Wirklichkeit zeigt sich ein n-Quadrat-Verhalten der Performance, dann suchen Sie nach versteckten Schlemiels. Die sind oft in Bibliotheksfunktionen versteckt. Wenn man eine Reihe von strcats in einer Schleife sieht, dann schreit niemand gleich "n-Quadrat", aber genau das passiert.

Wie lösen wir das? Einige schlaue C-Entwickler haben ihr eigenes mein_strcat implementiert, das so aussieht:

char* mein_strcat( char* ziel, char* quelle )
{
     while (*ziel) ziel++;
     while (*ziel++ = *quelle++);
     return --ziel;
}

Was wurde hier getan? Mit sehr wenig Aufwand geben wir hier einen Zeiger auf das Ende des neuen, längeren Strings zurück. Der Code, der die Funktion nutzt, kann damit Strings aneinanderhängen, ohne immer wieder von vorne zu scannen:

char grosserString[1000];     /* Ich weiß nie, wieviel ich da nehmen soll...*/
char *p = grosserString;
grosserString[0] = '\0';
p = mein_strcat(p,"John, ");
p = mein_strcat(p,"Paul, ");
p = mein_strcat(p,"George, ");
p = mein_strcat(p,"Joel ");

Dies verhält sich natürlich linear in der Performance, nicht quadratisch, so vermeiden wir Performanceverluste, wenn wir eine Menge Strings zu verbinden haben.

Den Erfindern von Pascal war dieses Problem bewusst und sie "lösten" es, indem sie die Anzahl Bytes im ersten Byte des Strings ablegten. Diese Strings heißen Pascal Strings. Sie können Nullen enthalten und sind nicht mit einer 0 abgeschlossen. Weil ein Byte nur die Werte 0-255 enthalten kann, sind Pascal Strings auf die Maximallänge von 255 Zeichen beschränkt, aber da sie kein Nullzeichen am Ende brauchen, benötigen sie genauso viel Speicher wie ASCIZ Strings. Das Tolle an Pascal-Strings ist, dass man nie eine Schleife braucht, um ihre Länge zu ermitteln. Dazu genügt eine Assember-Anweisung statt einer kompletten Schleife. Das ist extrem viel schneller.

Das alte Macintosh-Betriebssytem benutzte Pascal Strings überall. Viele C-Entwickler auf anderen Plattformen nutzen Pascal Strings wegen ihrer Geschwindigkeit. Excel benutzt Pascal Strings intern, weshalb Strings an vielen Stellen in Excel auf 255 ZEichen beschränkt sind, und es ist ein Grund, wieso Excel so enorm schnell ist.

Wenn man einen Pascal-String in C unterbringen wollte, musste man lange Zeit so schreiben:

char* str = "\006Hallo!";

Ja, man musste die Zeichen von Hand zählen und sie in das erste Byte des Strings hart kodieren. Faule Programmierer würden dies hier tun und bekommen langsame Programme:

char* str = "*Hallo!";
str[0] = strlen(str) - 1;

Beachten Sie, dass Sie in diesem Fall einen String bekommen, der sowohl ein Null-Zeichen am Ende hat (Der Compiler sorgt dafür) als auch einen Pascal String. Ich nannte die Scheiß-Strings, weil es einfacher ist, als "Mit Nullzeichen abgeschlossene Pascal Strings" zu sagen. Aber dieses Programm ist jugendfrei, somit müssen Sie den langen Namen benutzen.

Ich habe einen wichtigen Aspekt vorher ausgelassen. Erinnern Sie sich an diese Zeile?

char grosserString[1000];     /* Ich weiß nie, wieviel ich da nehmen soll...*/

Weil wir heute genau auf die Bits schauen, sollte ich dies nicht ignorieren. Ich hätte es richtig machen sollen: Herausfinden, wie viele Bytes ich wirklich brauche und die richtige Menge Speicher reservieren.

Oder nicht?

Denn anderenfalls, sehen Sie mal, könnte ein cleverer Hacker meinen Code lesen und merken dass ich nur 1000 Bytes zuweise in der Hoffnung, das wäre genug und er würde einen cleveren Weg finden, wie er mich dazu bekommt, 1100 Bytes in meinen 1000 Bytes Puffer zu strcatten wodurch der Stapelrahmen (Stack Frame) zu überschrieben wird und die Rückkehradresse geändert wird, dadurch wird Code ausgeführt, den der Hacker selbst geschrieben hat. Das ist was gemeint wird, wenn man sagt, ein bestimmtes Programm hätte irgendwo ein Sicherheitsleck wegen eines Pufferüberlaufs. Das war die häufigste Art von Hackerangriffen damals in der guten alten Zeit, bevor Microsoft Outlook Hacking so einfach gemacht hatte, dass jeder Teenager es kann.

OK, also sind alle Entwickler Blödmänner. Sie sollen halt rausfinden, wieviel Puffer sie reservieren müssen.

Aber mit C ist das wirklich nicht einfach zu machen. Gehen wir zurück zu unserem Beatles-Beispiel:

char grosserString[1000];     /* Ich weiß nie, wieviel ich da nehmen soll...*/
char *p = grosserString;
grosserString[0] = '\0';
p = mein_strcat(p,"John, ");
p = mein_strcat(p,"Paul, ");
p = mein_strcat(p,"George, ");
p = mein_strcat(p,"Joel ");

Wieviel sollen wir reservieren? Machen wir's mal ganz richtig:

char* grosserString;
int i = 0;
i = strlen("John, ")
     + strlen("Paul, ")
     + strlen("George, ")
     + strlen("Joel ");
grosserString = (char*) malloc (i + 1);
/* Platz für Null-Zeichen nicht vergessen! */
...

Meine Augen werden feucht. Sie sind sicher schon kurz davor, zu einem anderen Sender zu zappen und ich nehm's Ihnen nicht übel. Aber bleiben Sie bei uns, denn jetzt wird's richtig interessant.

Wir müssen alle Strings einmal durchlaufen, nur um herauszufinden, wie groß sie sind, dann müssen wir sie nochmal durchlaufen, um sie miteinander zu verbinden. Wenn Sie Pascal strings verwenden, dann ist wenigstens das strlen eine schnelle Operation. Vielleicht können wir auch eine Version von strcat schreiben, die das Speicherzuordnen für uns erledigt.

Da kommen wir gleich zu einem weiteren zum Problemfeld: Speicherzuordnung. Wissen Sie, wie malloc arbeitet? malloc hat eine lange verkettete Liste von freien Speicherblöcken namens "freie Kette". Wenn malloc aufgerufen wird, dann durchläuft es die Kette und sucht nach einem Block, der groß genug ist für die angeforderte Menge Bytes. Dann wird der Block in zwei Stücke geteilt: einer in der Größe, die angefordert wurde und einer mit den restlichen Bytes, gibt Ihnen den geforderten Block zurück und stellt den Restblock -wenn es einen gibt- zurück in die Kette. Wenn Sie free aufrufen, dann wird der Block, den Sie freigeben, in die "freie Kette" eingefügt. Es kommt vor, dass die "freie Kette" in viele kleine Blöcke zersplittert ist und Sie per malloc einen großen Block anfordern. Dann fängt malloc an, die freie Kette zu reorganisieren, Dinge auszusortieren und kleine Blöcke zu größeren zusammen zu legen. Dies dauert dreieinhalb Tage. Die Folge ist, dass malloc nie besonders schnell ist (es durchläuft immer die freie Kette) und manchmal ist es -unvorhersehbar- erschreckend langsam, wenn es intern aufräumt. (Überraschung! Das ist teilweise die gleiche Performance-Charakteristik wie so genannte "Garbage Collection"-Systeme. So sind die ganzen Vorbehalte gegen Garbage Collection-Systeme nicht ganz richtig, weil typische malloc-Implementationen sich auch nicht viel anders verhalten, wenn auch nicht so extrem.)

Schlaue Entwickler verringern die potenzielle Speicher-Zerstückelung durch malloc, indem sie immer Blöcke anfordern, deren Größe eine Potenz von 2 ist. Sie wissen schon: 4 Bytes, 8 Bytes, 16 Bytes, 18446744073709551616 Bytes usw. Für jeden, der schon mal mit Lego-Klötzen gespielt hat ist es verständlich, dass dies die wirre Fragmentierung des Speichers auf ein Minimum reduziert. Wenn es auch so aussieht, als ob damit Platz verschenkt würde, so kann man leicht erkennen, dass es nie mehr als 50% sind. Somit braucht Ihr Programm nie mehr als doppelt so viel Speicher als nötig wäre, was erträglich ist.

Angenommen, Sie hätten eine clevere strcat Funktion geschrieben, die den Zielpuffer automatisch vergrößert und neu zuordnet. Sollte sie den Puffer immer exakt auf die gerade nötige Größe erweitern? Mein Lehrer und Mentor Stan Eisenstat schlägt vor, bei Benutzung von malloc die Blöcke immer mindestens auf die doppelte Länge zu vergrößern. Das bedeutet, dass Sie realloc nie mehr als lg n mal aufrufen müssen, was eine große Auswirkung auf die Performance hat und Sie werden dabei nie mehr als 50% Platz verschwenden.

Wie auch immer. Das Leben wird immer verworrener hier im Land der Bytes. Sind Sie nicht auch froh, dass Sie nicht mehr in C schreiben müssen? Wir haben jetzt all diese Sprachen, wie Perl und Java und VB und XSLT, bei denen Sie nie an all diese Dinge denken müssen, diese Sprachen kümmern sich da irgendwie drum.

Aber manchmal verknotet sich die Verkabelung genau unter den Wohnzimmerdielen und wir müssen entscheiden, ob wir jetzt eine String oder eine StringBuilder-Klasse nehmen sollen, oder eine Spitzfindigkeit in der Art, weil der Compiler immer noch nicht schlau genug ist zu wissen, was wir genau erreichen wollen, und will uns helfen, (hilft aber nicht) "Schlemiel-der-Maler"-Algorithmen zu vermeiden.

[Image]Letzte Woche schrieb ich darüber, dass Sie die SQL-Anweisung SELECT Autor FROM buecher nicht effizient implementieren könne, wenn Ihre Daten in XML gespeichert sind. Für den Fall, dass nicht jeder mitbekam, was ich meinte - und da wir uns ja gerade sowieso in der CPU tummeln - wird diese Anmerkung hier klarer.

Wie führt eine relationale Datenbank SELECT Autor FROM buecher durch? In einer relationalen Datenbank hat jeder Datensatz in einer Tabelle (z.B. in der Tabelle "bucher") genau die gleiche Länge und jedes Feld ist immer an der gleichen Stelle innerhalb des Datensatzes. Wenn also jeder Datensatz in der Tabelle buecher 100 Bytes lang ist und das Feld autor bei Byte 23 beginnt, dann folgen die weiteren Autoren an Position 123, 223, 323 usw. Wie sieht für diese Abfrage der Code aus, um zum nächsten Datensatz zu kommen? Im Grunde so:

zeiger += 100;

Eine CPU-Operation. Superschnell!!!!

Schauen wir mal auf die buecher -Tabelle in XML:

<?xml bla bla>
<buecher>
     <buch>
          <titel>Oberflaechendesign für Entwickler</titel>
          <autor>Joel Spolsky</autor>
     </buch>
     <buch>
          <titel>Der Chop Suey Club</titel>
          <autor>Bruce Weber</autor>
     </buch>
</buecher>

Schnell eine  Frage: Wie sieht der Code aus, um zum nächsten Datensatz zu kommen?

Äähm...

An dieser Stelle würde ein guter Entwickler sagen: "Also, da parsen wir mal das XML in einen Baum im Speicher, damit wir darin schnell operieren können". Die Menge an Arbeit, die die CPU hier für ein SELECT Autor FROM buecher aufbringen muss, würde Sie zu Tränen rühren. Wie jeder, der Compiler schreibt weiß, sind das sogenannte lexing und parsing die langsamsten Teile des Compiliervorgangs.

Unnötig zu sagen, dass dies eine Menge String-Arbeit erfordert – von deren wir jetzt wissen, dass sie langsam ist – und eine Menge Speicherzuordnung, was ebenfalls langsam ist. All das, um den abstrakten Baum im Speicher zu erzeugen. Das setzt voraus, dass wir genug Speicher haben, um das ganze Ding auf einmal in den Speicher zu laden. Bei relationalen Datenbanken ist der Aufwand, um von einem Datensatz zum Anderen zu kommen, ein fester Wert und tatsächlich eine CPU-Operation. Das kommt hauptsächlich durch das Design. Und dank sogenannter Speicherabbild-Dateien müssen Sie nur diejenigen Seiten in den Speicher laden, mit denen Sie gerade wirklich arbeiten. Wenn Sie bei XML den Baum zuerst in den Speicher laden, dann ist der Aufwand, um von Datensatz zu Datenssatz zu kommen, konstant, aber Sie brauchen eine enorme einmalige Vorbereitungszeit und wenn Sie den Baum nicht in den Speicher lesen, dann hängt der Aufwand, um von Datensatz zu Datensatz zu gelangen, von der Länge des nächsten Datensatzes ab. Auf jeden Fall werden Hunderte von CPU-Zyklen gebraucht.

Das heißt in meinen Augen, dass man kein XML verwenden kann, wenn man gute Performance braucht und große Datenmengen hat. Bei kleinen Datenmengen oder wenn's auf Geschwindigkeit nicht so ankommt, dann ist XML ein nettes Format. Und wenn Sie beides wollen, XML und gute Performance, dann müssen Sie einen Weg finden, mit dem Sie Metadaten neben Ihren Strings speichern, ähnlich wie der Bytezähler bei den Pascal-String. Dies gibt Ihnen dann Hinweise darauf, wo Sie was in der XML-Zeichenkette finden können, damit Sie sie nicht danach absuchen müssen. Dann können Sie aber keine Texteditoren mehr zum Bearbeiten des XML nehmen, weil dies die Metadaten durcheinander bringen würde. Denn was Sie jetzt haben, ist kein "echtes" XML mehr.

Für die drei treuen Leser, die mich bis hierher begleitet haben: ich hoffe, dass Sie etwas gelernt haben oder daß dies Ihnen die Anregung zu neuen Ideen gegeben hat. Ich hoffe, dass Ihnen die Beschäftigung mit langweiligem Erstsemesterstoff wie die Funktionsweise von strcat und malloc neue Einsichten bringt, wenn Sie sich mit den neuesten strategischen und architektonischen Entscheidungen zu Technologien wie XML befassen. Als Hausaufgabe, denken Sie darüber nach, warum Transmeta-Chips sich immer träge verhalten werden. Oder warum die Original-HTML-Definition für TABLES (Tabellen)  so schlecht gestaltet war, dass große Tabellen in Webseiten nicht schnell angezeigt werden können, wenn der Benutzer einen langsamen Modemzugang hat. Oder warum COM unglaublich schnell ist, aber nur, solange Sie keine Prozessgrenzen überschreiten. Oder warum die NT Leute die Grafiktreiber in den Kernbereich und nicht in den Anwenderbereich des Speichers gestellt haben.

Dies sind lauter Dinge, die es nötig machen, über Bytes nachzudenken. Sie beeinflussen die großen Entscheidungen die wir über Architektur und Strategie treffen. Deshalb meine ich, dass Informatikstudenten in den ersten Semestern bei den Anfängen beginnen sollten, mit C und bei der CPU. Es widert mich geradezu an, dass in vielen Informatikursen die Meinung vertreten wird, Java sei eine gute Anfängersprache, weil sie so "einfach" ist, weil man nicht mit all diesem string und malloc verwirrt wird und weil man statt dessen cooles objektorientiertes Zeug lernen kann, das die großen Programe so schön modular macht. Da bahnt sich ein pädagogisches Desaster an. Generationen von Abgängern werden über uns kommen, die überall Schlemiel-der-Maler-Algorithmen schreiben und es nicht mal merken werden, weil sie im Grunde keine Vorstellung davon haben, dass Strings auf der Detailebene kompliziert sind, auch wenn man es einem Perl script nicht ansieht. Wenn Sie jemandem etwas von Grund auf beibringen möchten, dann müssen Sie ganz unten anfangen. Es ist wie bei Karate Kid: Wachs drauf, Wachs runter, Wachs drauf, Wachs runter. Mach' das drei Wochen lang. Danach ist es einfach, dem anderen Kid den Kopf abzuschlagen.

Emacs

 



Titel der Originalausgabe: Back to Basics  

Joel Spolsky ist der Gründer von Fog Creek Software, einer kleinen Software Firma in New York City. Nachdem er auf der Yale University graduierte arbeitete er als Programmierer und Manager bei Microsoft, Viacom und Juno.


Der Inhalt dieser Seiten stellt die persönliche Ansicht des Autors dar.
Copyright ©1999-2005  Joel Spolsky. Die Publikation ist urheberrechtlich geschützt. Alle Rechte vorbehalten.

FogBUGZ | CityDesk | Fog Creek Software | Joel Spolsky