Karl Brodowsky's IT-Blog – Seite 43 – IT Sky Consulting GmbH

Carry-Bit: Wie funktioniert das?

Alle, die in der Grundschule noch das handschriftliche Addieren gelernt haben, kennen das Verfahren eigentlich. Es ist nichts anderes als das, nur nicht im Zehnersystem, auch nicht im Zweiersystem, sondern im 256er-System (8 Bit), 65536er-System (16 Bit), 4294967296er-System (32 Bit), 18446744073709551616er-System (64 Bit) oder was auch immer die Wortbreite der CPU ist. Dass man immer mit Zweierpotenzen arbeitet, ist heute üblich, aber es kann durchaus sein, dass man von unseren zweiwertigen Bits einmal auf dreiwertige „Trits“ wechselt, wenn sich die Hardware-Technologie weiterentwickelt. Wir werde es sehen.

Ich finde es zwar nicht sinnvoll, dass man sich bei der Applikationsentwicklung mit solchen Details auf Bit-Ebene herumschlagen muss, aber da man ja mit Java, C, C++, C# und ähnlichen Sprachen heute einen großen Teil der Applikationsentwicklung durchführt, kommt man daran nicht vorbei. Diese Sprachen zwingen den Entwickler, sich mit diesen Fragen zu einem gewissen Maße auseinanderzusetzen, um deren Darstellungen ganzer Zahlen zu verstehen. Aber das „Carry“-Bit sieht man leider in diesen Sprachen nicht, obwohl es für das Verständnis wichtig ist.

Ich habe mich seit etwa Anfang der 80er Jahre damit beschäftigt, Software zu erstellen. Die damals für mich zugänglichen Rechner waren 8-Bit-Rechner mit 6502 oder 6510 als CPU und 1 MHz Taktfrequenz. Man konnte sie in einem Basic-Dialekt programmieren, aber das war für viele Zwecke unbrauchbar, weil es zu langsam war. So kam Assemblersprache zum Einsatz. Ich habe dann später noch 680×0-Assembler und 80×86-Assembler verwendet, aber ab Mitte der 90er Jahre kam das eigentlich nicht mehr vor. Eine 8-Bit-CPU kann zwei 8-Bit-Zahlen miteinander addieren und dabei ein 8-Bit-Ergebnis liefern. Dabei gibt es zwei Varianten zu unterschieden, nämlich signierte Ganzzahlen, die meistens im Zweierkomplement dargestellt werden. Das bedeutet, dass das erste Bit das Vorzeichen codiert. Somit sind die Werte von 0 bis 127 postive Ganzzahlen, wie man es erwartet. Die 127 hat das Bit-Muster 01111111. Nun könnte man meinen, dass das Bitmuster 10000000 die direkt darauffolgende Zahl, also 128 ist, aber in Wirklichkeit ist das die -128, weil ja das erste Bit das Vorzeichen codiert und die „1“ für negatives Vorzeichen steht. Erhöht man die -128 weiter, erhöht sich der Zahlwert, weiter, wird also weniger negativ. Man hat dann am Schluss 11111111, um die -1 auszudrücken. Dieses etwas obskure Verhalten ist plausibel, wenn man sich vorstellt, nicht mit ganzen Zahlen zu rechnen, sondern mit Restklassen modulo 256. Dabei werden zwei Zahlen also kongruent, also zusammengehörig, angesehen, wenn sie sich nur um ein Vielfaches von 256 unterscheiden. Um alle 256 möglichen Restklassen abzudecken, kann man als Vertreter die Zahlen von 0 bis 255 (unsigned byte) oder von -128 bis 127 (signed byte, Zweierkomplement) verwenden. Beides kommt in unseren heutigen Programmiersprachen vor.

Für das Carry-Bit nehme ich zunächst der Einfachheit einmal an, dass wir nur mit nicht-negativen Zahlen rechnen. Die möglichen Werte eines Speicherworts sind also von $0$ bis $2^n-1$ , wobei $n$ die Wortbreite ist, also in unserem Beispiel 8. Heutige CPUs haben normalerweise 64bit Wortbreite, was nichts an der prinzipiellen Funktionisweise ändert, aber mit 8Bit ist das Beispiel übersichtlicher. Jeder kann sich vorstellen, wie sich das Prinzip auf 32 oder 64 oder 36 oder auch 96 Bit übertragen ließe.

Es steht also die Bitfolge 11111111 für 255. Nun kann man mit einem Assemblerbefehl, der oft ADD oder so ähnlich heißt, zwei solche Zahlen addieren. Das heißt, dass die Addition innerhalb der CPU als eine einzige Operation innerhalb von einem oder einigen wenigen Taktzyklen durchgeführt werden kann. Nun ergibt die Addition von zwei unsignierten 8-Bit-Zahlen eine Zahl zwischen 0 und 510 (111111110 binär), leider zu viel für ein Byte. Mit einem Bit mehr ließe sich das aber ausdrücken. So behilft man sich, indem man die niedrigen 8 Bit des Ergebnisses als Resultat akzeptiert, aber das neunte, oberste Bit, das nun 0 oder 1 sein kann, in einem sogenannten Carry-Bit oder Carry-Flag oder Übertragsbit in der CPU speichert. Dieses kann man nun abfragen und davon abhängig einen anderen Pfad einschlagen, zum Beispiel eine Fehlerbehandlung wegen eines Überlaufs auslösen, wenn die weiteren Verarbeitungsschritte nicht in der Lage sind, mehr als 8-Bit zu verwenden. Aber es gibt auch eine sehr elegante Lösung, die zum Zuge kommt, wenn man Zahlen addiert, die mehrere Bytes (oder CPU-Worte) breit sind. Ab der zweiten Addition verwendet man so etwas wie ADC („Add with Carry“). Dabei wird das Carrybit, das 0 oder 1 ist, als dritter Summand einbezogen. Damit ist das Ergebnis diesmal sogar zwischen 0 und 511 (111111111 binär). Wieder erhält man ein Carry-Bit. Man kann diese Addition nun fortfahren, bis man alle Bytes der Summanden verarbeitet hat. Wenn sie verschieden lang sind, kann man die oberen Bytes des kürzeren Summanden durch 0 ersetzen, solange das Carry-Bit noch 1 ist, oder ansonsten die Bytes des längeren Summanden einfach übernehmen. Um das Gesamtergebnis auszudrücken braucht man in diesem Fall eventuell ein Byte (oder CPU-Wort) mehr als der längere der beiden Summanden hat.

So lässt sich relativ einfach eine Langzahladdition in Assemblersprache schreiben. Es ist einer der größten Design-Fehler vieler heutiger Programmiersprachen, insbesondere von C, dass sie einerseits mit Low-Level-Ganzzahltypen ausgestattet sind, aber andererseits uns das Carry-Bit vorenthalten, so dass man dieses mit viel Gebastel ermitteln muss.

Die Subtraktion von Langzahlen funktioniert sehr ähnlich, dafür gibt es meist ein SBC („subtract with carry“) oder SBB („subtract with borrow“), je nachdem, wie das Carry-Bit bei der Subtraktion interpretiert wird.

Für die vorzeichenbehafteten Ganzzahlen muss man beim jeweils höchsten Byte der beiden Summanden aufpassen und hier das Vorzeichenbit berücksichtigen. Häufig gibt es ein sogenanntes Overflow-Bit, das in diesem Fall zumindest erkennen lässt, wann man ein weiteres Speicherwort benötigt.

Die 64-Bit-Addition heutiger CPUs könnte prinzipiell so funktionieren, dass sie bitweise nacheinander oder byteweise nacheinander mit Carry addiert. Mir sind die Implementierungsdetails von ARM, Intel und AMD zwar nicht bekannt, aber ich gehe davon aus, dass man dort eine größere Parallelisierung der Operation verwendet. Es gibt Algorithmen, die es so ermöglichen, eine Langzahladdition unter Verwendung von Parallelisierung wesentlich schneller auszuführen als mit dem hier beschriebenen Verfahren. Vielleicht schreibe ich dazu auch irgendwann einmal etwas, wenn es jemanden interessiert.

Interessant ist es auch, Multiplikation, Division, Quadratwurzel, Kubikwurzel und ähnliches zu berechnen. Auch damit habe ich Erfahrung, kann das also bei Interesse gerne beschreiben. Kurz gesagt sind diese Operationen auf heutigen CPUs sehr einfach in Assemblersprache zu implementieren, weil dort Multiplikation und Division bereits vorhanden sind, aber es geht auch mit 8-Bit-CPUs ohne Multiplikationsbefehl, falls das jemanden aus Nostalgiegründen interessieren sollte. Gerade für die Multiplikation gibt es aber wesentlich bessere Algorithmen, wenn die Faktoren sehr lang sind.

Ich möchte einen Artikel über die mögliche Ermittlung des Carrybits in C verfassen. Dieser wird auf Englisch erscheinen und unter der englischen Übersetzung dieses Artikels als Ping-Back verlinkt sein.

2013

Frohes neues Jahr — Happy New Year — Gott nytt år — ¡Próspero año nuevo! — FELIX SIT ANNUS NOVUS — bonne année — Felice Anno Nuovo — Godt nytt år — Весёлого нового года — السنة الجديدة المبتهجة — Bloavezh mat — 新年好 — Godt nytår — Prosperan novjaron — うれしい新しい年 — Feliç Any Nou — Mwaka Mpya wenye Furaha — Een gelukkig nieuwjaar — Szczęśliwego nowego roku — Hyvää Uutta Vuotta — Próspero ano novo — Bun di bun an

Security: physikalische Trennung

Für viele Aktivitäten im Internet ist die schwächste Stelle der Weg durchs Internet, da dieser oft unverschlüsselt erfogt, zum Beispiel über http oder über EMail. Auch ein verschlüsselter Kommunikationspfad (z.B. https oder skype) hilft natürlich nur so weit, wie man dem Betreiber des Servers traut, auf den man dabei zugreift. Durch Umstellung der Kommunikation auf sicherer Mechanismen (z.B. https) wird der Kommunikationspfad sicherer. Dabei finden solche Zugriffe über das Web heute nicht nur sichtbar über die mit dem Browser angesurften Seiten und deren Ergänzungen (Bilder, CSS, JavaScript) statt, sondern auch durch Programme, insbesondere JavaScript-Programme, die im Browser laufen und sich einzelne Informationsstücke vom Server holen und diese in die Seite einbauen.
Das heißt u.a.:

Ein Angreifer im Netz kann nur mit sehr großem Aufwand oder gar nicht abhören, was der Inhalt der Kommunikation ist. Das betrifft beide Richtungen, also auch die Frage, welche URLs man auf dem betreffenden Server anspricht. Sehr nützlich ist das auch beim Einloggen für die Übermittlung des Passwords.
Ein Angreifer kann die Nachricht nur mit sehr großem Aufwand oder gar nicht ändern oder verfälschen. Da ist man gerade beim e-Banking froh, wenn das nicht so einfach ist.

Eine Schwachstelle bleibt aber der Rechner des Benutzers selbst. Den hat man ja bei sich im Haus stehen und da kommt kein Einbrecher durch die Tür und macht damit was Ungewünschstes, außer es ist ein Laptop oder ein Rechner im Großraumbüro. Aber wir wissen ja, daß der Einbrecher unsichtbar durch das Netz kommt. Sobald man einen Rechner direkt ins Netz hängt, kann man beobachten, daß Angreifer ihn nach kurzer Zeit entdecken und alle möglichen Attacken probieren, die auf häufige Schwachstellen aufsetzen. Das geht heute natürlich alles vollautomatisch. Auch sonst gibt es viele Wege für Schadsoftware auf den Rechner und Al Capones heutige Berufskollegen haben ganze Botnetze aus Rechnern anderer Leute aufgebaut, die ihnen zwar nicht gehören, aber gehorchen. Solange diese kriminelle Nutzung des Rechners im Hintergrund bleibt, merken das viele Benutzer gar nicht, weil das, was sie selber machen, ja noch funktioniert, nur vielleicht etwas langsamer. Wenn es zu langsam läuft, hilft bei MS-Windows-Anwendern oft das „Windows neu installieren“, dann ist nebenbei die Schadsoftware auch wieder weg, wenn man Glück hat. Anscheinend sind auch staatliche Stellen mancher Staaten in diesem Bereich unterwegs. Heutige Mobiltelefone sind natürlich auch fast vollwertige Rechner, also von solchen Überlegungen auch betroffen. Nun ist schon an sich ärgerlich, Teil eines Botnetzes zu sein, weil man dadurch letztlich ungewollt daran beteiligt ist, wieder andere Rechner anzugreifen oder andere kriminelle Aktivititäten des Botnetzbetreibers zu alimentieren. Interessant ist aber auch der Gedanke, daß der Botnetzbetreiber den vollen Zugriff auf den Rechner hat, also zum Beispiel beim e-Banking im Browser die unverschlüsselten Daten sehen und ändern kann. Das ist schwierig, aber prinzipiell möglich.

Ein recht drastischer Ansatz wäre nun, in einem Laptopgehäuse oder sogar in einem Mobiltelefongehäuse physikalisch mehrere Rechner unterzubringen. Der Raspberry Pi zeigt, daß es möglich ist, kostengünstig sehr kleine (Linux-)Rechner zu bauen. Wenn das Gehäuse eines neuen Laptops nur etwas größer ist, bringt man zusätzlich noch so einen kleinen Rechner darin unter, der keine oder nur sehr wenige lokale Benutzerdaten speichert und nur für e-Banking und andere sicherheitskritische Aktivitäten benutzt wird. In Desktoprechner wird der zusätzliche Platzbedarf im Gehäuse kaum auffallen. Ich stelle mir ein speziell schlankes Linux vor, das als einzige Applikation einen Browser hat, der für diesen Zweck optimiert ist. Mit einem Schalter wird physikalisch umgeschaltet, welcher Rechner Display, Tastatur und Maus hat.

Ein ähnlicher Effekt ließe sich natürlich auch erreichen, wenn man seinen Rechner voll virtualisiert, so daß das direkt auf dem Rechner laufende System nur dazu dient, virtuelle Umgebungen für die Systeme bereitzustellen, in denen man dann arbeitet. Wenn das gut gemacht ist, hat man auch eine recht gute Trennung zwischen dem e-Banking-System und den anderen virtuellen Sytemen auf dem Rechner, aber man hat in diesem Fall immmer die Performance-Einbuße durch die Virtualisierung hinzunehmen. Das läßt sich alles auch für Mobiltelefone umsetzen, nur muß man dann natürlich ein paar Gramm mehr und ein dickeres oder größeres Telefon mit sich herumschleppen, weil diese ja schon recht vollgepackt sind.

Ich habe mal eine Startup-Firma gesehen, die Desktoprechner nach diesem Prinzip gebaut hat, sogar mit mechanischen Schaltern und drei separaten Rechnern in einem Gehäuse. So etwas kann man aber trotzdem heute noch kaum kaufen, aber ich denke, daß es vielleicht eine gute Idee ist, die sich in ein paar Jahren etablieren könnte.

Linux wird meistgenutztes OS

Wenn man Mobiltelefone und andere Mobilgeräte als Computer mitzählt, hat Linux inzwischen mehr als doppelt so viel Marktanteil wie MS-Weindows:
Tagesanzeiger 2012-12-26

Development of Hardware: Parallelism

Deutsch

Until recently we could just rely on the fact that the CPU frequencies doubled at least every year, which has stopped a couple of years ago. So we can no longer compensate the inefficiencies of our software by just waiting for the next hardware release, which was no big deal, because software was often delayed anyway by a couple of months. Off course the power of hardware depends on many factors, even on the number of instructions that can be done within one clock cycle or the number of clock cycles needed for instructions. Everyone who has dealt with performance issues knows that providing enough physical memory is usually a good idea and certain optimizations in the circuits and the design of the chips can help to make the computer run faster, even though we usually do not care. But the power of the single CPU core has almost stagnated now for some years, but it is easy to get chips that provide multiple cores. An interesting link: The Free Lunch is Over.

Now we have the challenge of making use of these multiple CPU cores for building resource hungry applications, which is basically achieved by having multiple threads or processes running simultaneously. Unfortunately we encounter some issues. The most obvious problem is that it is easy to find developers who say that they are capable of developing such applications, but there are only very few who can really do it well enough to build reliable and stable software. So the software might work well under ideal circumstances, for example when testing it on the developer’s machine, but it will eventually fail in the productive environment, when run under load, creating errors that are very hard to pin down. Or the threads and processes spend so much time waiting for each other that the system does not actually make use of the parallel capabilities of the hardware. Or we even get dead locks. What do we learn from this?

For this kind of architecture excellent developers are needed, who can imagine the parallel computations and who have enough experience with this kind of development. And it is usually better to do development that uses the parallelism to a reasonable extent, without loosing robustness. Obviously it is important to test with reasonable data and load on test systems that are like the productive systems.

Another approach is the use of frameworks. There are some good lightweight frameworks, but common frameworks like JEE (earlier called J2EE) are using so many resources for themselves and restrict the developer so much that the advantage of easier multithreading gets lost by this, because the framework itself uses most of the CPU power and the main memory. There are many cases where using frameworks with JEE applications servers is a good idea, but high performance applications should done differently.

The problem is always that data structures that need to be manipulated by multiple threads or processes cause problems. These may be handled, but create a lot of difficulties in practice.

Some radical approaches are:

avoid commonly used data structures
usage of immutable data structures

The first approach is quite logical for development with C or Ruby or Perl, where the processes need relatively little memory, so that it is possible to run multiple processes simultaneously. Using POSIX-IPC (or whatever your OS offers instead) or TCP/IP the processes can communicate with each other. That works well, if there are several relatively independent processes that do not need to communicate very much. But it needs excellent developers as well, because they really need to know the IPC mechanisms, unless the sub tasks are so independent that they do not need to communicate with each other at all. Maybe Erlang has implemented this idea in a practicable way, allowing a huge number of parallel processes with totally separate data stores that communicate with each other through some message passing mechanism.

The other idea, to have all shared data structures immutable, is followed by Scala and Clojure. The disadvantage of having to create a copy with some changes applied instead of modifying the object itself can be reduced by internal optimizations within the standard libraries that use references to the original and just store the changes instead of really copying huge data structures for each change. Even Java uses such mechanisms when creating a substring of an immutable String.

In any case it is necessary to deal with dependencies between processes in order to avoid deadlocks. In the Scala and Clojure world it is reasonable to build lightweight frameworks that help dealing with multiple parallel threads because the promise of immutability eliminates many of the problems of shared objects. Twitter uses Scala internally and has been able to cope with the load even during events that cause a heavy communications load.

A principal problem remains whenever heavy communication between processes is required. In a huge system it is impossible to optimize all communication paths. Assuming n parallel processors we have ${n(n-1)\over2}$ communication pairs, which is growing $O(n^2)$ . So we need to compromise as soon as $n$ gets really huge. A bus architecture with one common channel get congested and for separate point to point connections it will be necessary to provide these only for immediate neighbors instead of all possible connections. To really imagine huge, think of an application that is running on several locations, each having several racks, each containing several machines, each containing several CPU chips, each containing several CPU cores, possibly even with hyper-threading. Using sophisticated hardware architecture it is possible that CPU cores communicate with other CPU cores in their vicinity through very fast mechanisms, but it is only possible to place a limited number of CPU cores in this vicinity.

An interesting idea was to put a large number of boards containing this number of CPUs and cores that can communicate with each other efficiently into a topological hypercube. Having $2^m$ boards, each board has $m$ neighbors that can be reached directly through a relatively short communication channel. The boards represent the vertices of an $m$ -dimensional hypercube. This architecture allows reaching another board in $m$ steps and even to aggregate a result from all or a subset of all boards in $m$ steps. Having a wired-or for synchronization is very helpful for enhancing the performance for many typical types of tasks. Does anybody know how current super computers are built?

In any case it is good to be able to run sub tasks with as little communication with other sub tasks as possible, because the overhead of communication can eat up the gain of parallelism.

Weihnachten – Christmas – Jul

Fröhliche Weihnachten − Merry Christmas − God Jul − Feliz Navidad − Joyeux Noël − Natale hilare − С Рождеством − ميلاد مجيد − Buon Natale − God Jul! − Gëzuar Krishtlindjet − Честита Коледа − 圣诞快乐 − Sretan božić − Veselé Vánoce − Glædelig Jul − Prettige Kerstdagen − Feliĉan Kristnaskon − Häid jõule − Gledhilig jól − Hyvää Joulua − Zalig Kerstfeest − καλά Χριστούγεννα − क्रिसमस मंगलमय हो − Kellemes Karácsonyi Ünnepeket − Gleðileg jól − Selamat Hari Natal − Nollaig Shona Dhuit! − クリスマスおめでとう ; メリークリスマス − Bon nadal − 즐거운 성탄, 성탄 축하 − Priecîgus Ziemassvçtkus − Su Šventom Kalėdom − کريسمس مبارک − Wesołych Świąt Bożego Narodzenia − Feliz Natal − Crăciun fericit − Bella Festas daz Nadal − Срећан Божић − Vesele Vianoce − Vesele bozicne praznike − Mutlu Noeller − З Рiздвом Христовим

Weihnachtsbaum Römerberg / Quelle Wikimedia Thomas Wolf / http://www.foto-tw.de

Entwicklung der Hardware: Parallelisierung

English

Bis etwa einigen Jahren konnte man davon ausgehen, dass sich die Taktfrequenz von gängigen Mikroprozessoren regelmäßig erhöht und bei der Entwicklung neuer Software darauf vertrauen, dass die Hardware zumindest in naher Zukunft leistungsfähig genug sein würde, um gewisse Ineffizienzen zu kompensieren. Nun ist die Leistungsfähigkeit eines Rechners von sehr viel mehr Faktoren als der Taktfrequenz abhängig, vor allem auch davon, wie viele Operationen in einem Takt bzw. wieviele Takte für eine Operation benötigt werden. Wichtig ist erfahrungsgemäß aber auch ein genügend großer Hauptspeicher und natürlich gewisse Optimierungen auf der Platine und auf dem Chip, die man gar nicht so explizit wahrnimmt und auch nicht so leicht ändern kann. Grundsätzlich ist aber die Leistung einzelner CPU-Kerne nur noch langsam gestiegen, man bekommt aber ohne weiteres einen Chip, auf dem mehrere CPU-Kerne implementiert sind. Dualcore, Quadcore u.s.w. sind ja gut bekannt. Ein Link dazu: The Free Lunch is Over

Nun kann man diese mehrfachen Prozessoren mit einer einzelnen Ressourcen-hungrigen Applikation nutzen, wenn diese mehrere parallel verlaufende Threads oder Prozesse verwendet. Leider gibt es dabei ein paar Probleme. Das ärgerlichste ist, dass man zwar viele Entwickler findet, die sagen, das zu können, aber dass die Sache nachher tatsächlich stabil funktioniert, ist leider seltener. Häufig erlebt man Schönwetter-Software. Auf dem Rechner des Entwicklers funktioniert sie prima, vielleicht auch auf dem Testsystem. Aber im produktiven Einsatz treten dann obskure Fehler auf, die niemand nachvollziehen kann. Oder die verschiedenen Threads und Prozesse warten so oft gegenseitig aufeinander, daß in Wirklichkeit im Durchschnitt doch nur eine CPU genutzt wird. Oder das System blockiert sich selbst („Verklemmung“ oder engl. „dead-lock“). Natürlich nicht auf dem Rechner des Entwicklers, weil die spezielle Situation, die dazu führt, nur unter Last im produktiven Einsatz zum ersten Mal auftritt. Was lernt man daraus? Für diese Art von Architektur braucht man sehr gute Entwickler, die sich die parallelen Abläufe vorstellen können und die genug Erfahrung damit haben. Und man sollte sich nicht zu weit aus dem Fenster lehnen, sondern Dinge entwickeln, die zwar die Parallelität ausnutzen, aber doch robust genug sind, um nicht nur knapp zu funktionieren. Außerdem ist es wichtig, mir sehr realitätsnahen Daten und Datenmengen zu testen und auch Lasttests durchzuführen. Auf Testsystemen, die den späteren Produktivsystemen ähneln.

Ein anderer Ansatz löst das ganze Problem durch Frameworks. Es gibt sicher gute und leichtgewichtige Frameworks, aber bei gängigen Frameworks wie JEE (früher J2EE) brauchen diese schon selbst so viele Ressourcen und sie schränken die Möglichkeiten bei der Entwicklung so stark ein, dass man zumindest den Vorteil des einfacheren Multithreadings sofort wieder verliert, weil das Framework selber jetzt einen großen Teil der Rechenleistung und des Hauptspeichers in Anspruch nimmt. Es mag andere gute Gründe geben, solche Frameworks mit JEE-Applikationsservern einzusetzen, aber der Performance-Gewinn durch Parallelisierung hält sich normalerweise in Grenzen.

Das Problem ist immer wieder, daß man Datenstrukturen hat, die von mehreren Threads oder Prozessen manipuliert werden können und dass dadurch Probleme auftreten, die sich zwar handhaben lassen, die aber in der Praxis große Schwierigkeiten bereiten.

Zwei radikale Ansätze sind:

Verzicht auf gemeinsam genutzte Datenstrukturen
Verwendung von unveränderbaren Datenstrukturen

Der erste Ansatz ist zum Beispiel bei Entwicklung mit Ruby oder mit C gut möglich, weil die einzelnen Prozesse relativ wenig Hauptspeicher verbrauchen und man sich so leisten kann, mehr Prozesse gleichzeitig laufen zu lassen. Nun kann man mit verschiedenen Mechanismen Interprozeßkommunikation durchführen, z.B. unter Linux und Unix mit Posix-IPC oder mit TCP/IP. Das funktioniert vor allem dann gut, wenn man relativ unabhängige Prozesse hat, die nur wenig miteinander kommunizieren müssen. Und auch dafür braucht man ähnlich gute Entwickler wie beim Multithreading, die IPC gut beherrschen, außer man hat das Glück, dass die Prozesse so unabhängig voneinander laufen, daß sie gar nicht miteinander kommunizieren müssen. Vielleicht hat Erlang diese Idee in praktikabler Form umgesetzt. Dort kann man mit einer großen Anzahl von Prozessen arbeiten, die völlig voneinander getrennte Speicherbereiche für ihre Daten haben, während es ein Messaging-System für die Kommunikation zwischen diesen Prozessen gibt.

Die andere Idee, alle geteilten Datenstrukturen unveränderbar („immutable“) zu machen, wird z.B. von Scala und Clojure umgesetzt. Der Nachteil, daß man statt ein Objekt zu ändern, nur eine Kopie mit dieser Änderung erzeugen kann, wird durch Mechanismen abgemildert, die in gewissen Fällen intern so ein Kopieren durch teilweise Referenzierung des Eingabeobjekts ersetzen. Das gibt es auch in einem einfachen Fall in Java, wo der Zeichenketten-Type (String) immutable ist und wo Teile der Zeichenkette, die mittels substring() erzeugt werden, dieselbe interne Struktur wie die ursprüngliche Zeichenkette referenzieren.

In jedem Fall muss man sich aber über Abhängigkeiten der Prozesse und Threads untereinander Gedanken machen, damit man keine „dead-locks“ baut. Mit Scala und Clojure ist es aber möglich, leichtgewichtige Frameworks zu bauen, die die Ausführung von sehr vielen Threads gleichzeitig erlauben, weil das Versprechen der Unveränderbarkeit der geteilten Objekte viele Probleme eliminiert. Twitter benutzt zum Beispiel intern Scala und ist damit in der Lage, auch bei Ereignissen, die sehr viel Kommunikationsbedarf auslösen, mit der Last fertigzuwerden.

Ein Problem prinzipieller Natur bleibt natürlich, wenn der Kommunikationsbedarf zwischen den Prozessen sehr groß ist. In einem großen System können nicht alle Kommunikationspfade optimal schnell sein, denn bei n parallelen Prozessoren gibt es ${n(n-1)\over2}$ Kommunikationspaare, was für große n mit dem Quadrat der Anzahl der Prozessoren wächst, also zu Kompromissen zwingt. Man bekommt entweder bei einem gemeinsamen Kanal Kapazitätsprobleme oder man muss bei getrennten Kanälen neben Pfaden zu den direkten Nachbarn auch auf zusammengesetzte Verbindungen setzen. Um es plastisch zu beschreiben: Eine wirklich große Applikation läuft verteilt über mehrere Rechenzentren, in denen es jeweils mehrere Racks gibt. Die Racks haben jeweils mehrere Rechner, die Rechner mehrere CPUs und die CPUs mehrere Kerne. Mit viel Geld kann man raffiniertere Hardware bauen, wo eine größere Anzahl von CPU-Kernen schnell miteinander kommunizieren kann, aber in unmittelbarer Nachbarschaft eines CPU-Kerns mit maximal schneller Kommunikation lassen sich nur begrenzt viele andere CPU-Kerne unterbringen.

Eine Idee war, eine große Anzahl von Rechnern topologisch in einem Hyperwürfel anzuordnen. Man hat also $2^n$ Teilrechner in Positionen, die den gedachten Ecken eines $n$ -dimensionalen Würfels entsprechen und die Kanten dieses Hyperwürfels sind die leistungsfähigen Verbindungen dazwischen. So kommt man mit maximal $n$ Schritten zu jeder anderen Teilrechner und kann auch in $n$ Schritten ein Zwischenergebnis von allen Teilrechnern aggregieren und danach wieder verteilen. Weiß jemand, welche Ansätze man in heutigen Hochleistungsrechnern mit sehr vielen CPUs wählt?

Grundsätzlich kann eine Berechnung mit wenig Kommunikationsbedarf der Teilprozesse sehr gut parallel ablaufen, aber ein hoher Kommunikationsbedarf kann den Gewinn durch die Parallelisierung zunichte machen.

Apps or HTML5

Deutsch

The idea of having apps for cell phones is not so new. Quite simple phones offered this and the apps were often developed using Java ME, a „reduced“ Java. This may not have been the best possible solution, but at least development could be made for a variety of cell phones with the same source code, but some additional testing effort.
Then Nokia smartphones added the option to use Qt together with C++ for the development of apps. The promise to be device-independent could still be maintained , because Qt is open source and has been ported to several popular desktop operating systems as well as Symbian, Maemo and Meego for cell phones. Qt is now developed by Digia and will become available even for Android in the future.
With the introduction of Apple’s iPhone and Android based cell phones two more variants for developing apps appeared: Objective-C for Apple’s cell phones and Java running on Dalvik for Android. Microsoft also tries to spread their cell phone OS, whose apps are, of course, to be developed differently again, maybe with C #?

Thus app developers should really think twice if it is really a good idea to develop the same app in about 6-8 almost completely independent implementations (for Android, Qt/Symbian, Qt/Maemo/Meego, Objective-C/ios, MS-WinPhone, Blackberry, JavaME,…) in order to support a large part of the potential user base. For very important apps that may well be a reasonable investment, but it turns quickly but the question of whether the cost is justifiable. Leaving out many potential users by just doing one or two or three implementations is not a good idea for an app that is important. And we know exactly which systems will become common in a few years or at least relevant occupy niches. Possibly new systems will at least have an Android Dalvik compatibility, so they will be able to run Android apps even if they are not Android. Sailfish from Jolla promises that they will do this. But it can very well happen that a new mobile OS becomes popular that requires one more implementation for its apps. So native apps installed on the mobile device will become available with a significant delay, while mobile web applications will be available on then new smart phone that we do not even know today from the first day. Noone is going to provide a mobile device without a decent web browser.

The idea of making money by getting some percentage from the sales of apps via the preferred app stores was great a few years ago. But now there are so many apps around that it is becoming harder to achieve significant download figures in order to make more than a few cents. Until recently apps were justified by functionality that was not readily available in web applications. However this is now changing rapidly. With HTML5, JavaScript, Ajax, WebSockets, and some other new features added to the web technology stack, almost everything that could be done by apps can now be done by web applications as well. And the web application can be developed once and used on a multitude of devices. I therefore assume that these apps will survive only for a few applications that are so important that multiple development does not hurt and that need more interaction than usual applications or access to special device hardware. It is increasingly difficult to find such cases. Just some examples:

users should pay for using the functionality. It is possible online as well. Many sites have paywalls.
games should also work offline, for example in railroad tunnels. HTML5 promises to have a local storage that can be used for this purpose.
Appearance: HTML5 is quite powerful for that.
interactivity with JavaScript, Ajax and HTML5 is quite powerful.

In short, the business of running app stores might very well become obsolete or at least a niche business for a small number of apps very soon.

Update 2019-03-23: https://en.wikipedia.org/wiki/Digia is no longer referring to the company „Digia“ mentioned above. Qt is now developed by the Qt Company.

Boolean in Datenbanken

Gemäß SQL-Standard SQL:1999 ist ein Boolean-Typ in Datenbanken vorgesehen, aber dieses Feature ist optional und auch im Jahr 2012 von vielen vorhandenen Datenbanken nicht implementiert. PostgreSQL ist wohl eine Ausnahme.

Nun ist dieser Boolean-Typ sehr trivial nachzubilden. Ich habe zum Beispiel die folgenden Varianten gesehen:

VARCHAR(1) oder VARCHAR2(1) oder CHAR(1) mit ‚0‘ und ‚1‘
VARCHAR(1) oder VARCHAR2(1) oder CHAR(1) mit ‚N‘ und ‚Y‘
VARCHAR(1) oder VARCHAR2(1) oder CHAR(1) mit ‚T‘ und ‚F‘
INTEGER oder NUMBER(1,0) mit 0 und 1

Oder so absurde Varianten wie:

VARCHAR(5) oder VARCHAR2(5) mit ‚true‘ und ‚false‘

Gerade die Tatsache, daß hier nicht eine Lösung sich durchgesetzt hat, ist schon ein Nachteil, denn in größeren Applikationen hat man dann oft noch verschiedene Varianten gleichzeitig. In SQL muß man immer noch die Extra-Runde drehen und den Boolean-Wert konvertieren, vor allem in den WHERE-Bedingungen.

Letztlich kann man mit dieser Einschränkung leben, solange man sich auf eine Variante einigt. Vielleicht kann mir auch jemand sagen, welches die „richtige“ Lösung ist, auf die sich die meisten DBAs geeinigt haben.

Apps oder HTML5

English

Die Idee mit den Apps für Mobiltelefone ist nicht sehr neu. Schon recht einfache Telefone konnten so etwas und man entwickelte die Apps oft mit Java ME, einem verkleinerten Java. Das ist vielleicht nicht die beste Lösung, aber hatte immerhin den Vorteil, daß man eine Entwicklung für eine Vielzahl von Mobiltelefonen machen konnte und nur beim Testen dann alle möglichen Geräte durchprobieren mußte.
Dann kam bei den Nokia-Smartphones Qt mit C++ als Basis für die Entwicklung von Apps auf. Das versprach immer noch geräteunabhängig zu sein, weil Qt OpenSource ist und auf verschiedene gängige Desktop-Betriebssysteme sowie Symbian und Maemo/Meego portiert worden ist. Wirklich verbreitet waren die Qt-Apps auf Symbian und Maemo/Meego. Heute wird Qt von Digia entwickelt und soll in Zukunft unter anderem auch für Android verfügbar sein.
Nun kamen mit der Verbreitung von Apple-iphone und Android neue Varianten auf, deren Apps man mit Objective-C bzw. Java für Dalvik schreiben soll. Microsoft versucht auch noch ein Mobiltelefon-OS zu verbreiten, das dessen Apps wieder anders, vielleicht mit C#, entwickelt werden sollen.
So stellt sich für App-Entwickler heute das Problem, daß man Apps mit einer bestimmten Funktionalität wirklich ca. 6-8 Mal komplett neu entwickeln muß, wenn man einen großen Teil der Anwender erreichen will. Für sehr wichtige Apps mag das schon eine vertretbare Investition sein, aber es stellt sich doch schnell die Frage, ob der Aufwand vertretbar ist. Außerdem wissen wir nicht genau, welche Systeme außer Android in ein paar Jahren verbreitet sein werden oder zumindest relevante Nischen besetzen. Vielleicht wird sich bei neuen Systemen zumindest eine Android-Kompatibilität durch eine angepaßte Dalvik-Umgebung für diese Systeme etablieren, aber sicher ist auch das nicht. Mit Web-Applikationen ist man aber schon ab dem ersten Tag auf dem neuen Smartphone, von dem man heute noch nichts weiß. Den Browser wird niemand weglassen wollen.

Die Idee, mit den Prozenten aus dem Verkauf von Apps über die jeweiligen App-Stores Geld zu verdienen war sicher vor ein paar Jahren mal Gold wert. Heute gibt es aber für viele Systeme eine riesige Vielfalt von Apps und wenn da noch eine dazustellt, ist es schon ungewöhnlich, noch auf so hohe Download-Zahlen zu kommen, daß die paar Cent pro Download alleine schon den Aufwand finanzieren könnten.
Bis vor gar nicht so langer Zeit hatten die Apps noch eine Existenzberechtigung alleine schon wegen der Möglichkeiten Client-seitig, also auf dem Mobiltelefon, bessere interaktive Funktionalität aufzubauen als dies mit HTML und einer Webapplikation möglich wäre.
Das hat sich aber inzwischen sehr relativiert. Mit HTML5, JavaScript, Ajax, Websockets und einigen anderen Neuerungen der klassischen Web-Applikations-Technologie kann man heute praktisch alles machen, was diese Apps konnten. Und man muß es nur einmal entwickeln. Ich gehe daher davon aus, daß sich diese Apps nur für einige wenige spezielle Anwendungen halten werden, die so bedeutend sind, daß die Mehrfachentwicklung nicht weh tut und die mehr Interaktion brauchen als mit Web-Applikationen üblich ist. Es wird immer schwieriger, solche Fälle zu finden. Was einem spontan einfällt:

Anwender soll für Verwendung der Funktionalität bezahlen. Das gibt es im Internet an viele Stellen. Die Bezahlmechanismen sind noch nicht optimal, aber weit verbreitet und etabliert, wenn es um Einkaufen im Web geht. Sogenannte „Paywalls“ für Bereiche einer Webseite oder -applikation, die nur zahlenden Kunden zugänglich sind, gibt es. Vorteil: Kein app-Store zieht seine Prozente ab.
Spiele sollten doch auch offline funktionieren, zum Beispiel im Ausland (solange Dataroaming teuer ist) oder im Tunnel. Das verspricht HTML5 mit dem lokalen Speicher („local storage“) aber zu lösen
Aussehen: Kann man mit HTML5 ziemlich beliebig schaffen.
Interaktivität: Mit JavaScript, Ajax und HTML5 kann man sehr gute Applikationen bauen.

Kurz gesagt, das Geschäft mit den App-Stores dürfte in ein paar Jahren zum Auslaufmodell werden oder als Nische für eine kleine Anzahl von Apps überleben.