Rounding of Money Amounts

Deutsch

Many numerical calculations deal with amounts of money. It is always nice if these calculations are somewhat correct or if we can at least rest assured that we do not loose money due to such inaccuracies. Off course there are calculations that may legitimately deal with approximations, for example when calculating profits as percentages of the investment (return on investment). For this kind of calculations floating point numbers (double, Float or something like that) come in handy, but off course dealing with the numeric subtleties can be quite a challenge and rounding errors can grow huge if not dealt with properly.

It is often necessary to do calculations with exact amounts. It is quite easy to write something like 3.23 as floating point number, but unfortunately these are internally expressed in binary format (base 2), so the fraction with a power of 10 in the denominator needs to be expressed as a fraction with a power of two in the denominator. We can just give it a try and divide x=323_{10}=101000011_{2} by y=100_{10}=1100100_2, doing the math in base 2 arithmetic. We get something like z=x/y=11.0011101011100001010001111010111000010100011110101\ldots_{2}, more precisely z=11.00\overline{11101011100001010001} or as fraction z=11_2+\frac{11101011100001010001_2}{100_2*(100000000000000000000_2-1_2)} or in base 10 z=3_{10}+\frac{964689_{10}}{4_{10}\cdot1048575_{10}}.

It can be seen that such a harmless number with only two digits after the decimal point ends up having an infinite number of digits after the decimal point. Our usual Double and Float types are usually limited to 64 Bits, so some digits have to be discarded, causing a rounding error. Fortunately this usually works well and the stored number is still shown as 3.23. But working a little bit with these floating point numbers sooner or later results like 3.299999999999 or 3.2300000001 will appear instead of 3.23, even when doing only addition and subtraction. When doing larger sums it might even end up as 3.22 or 3.24. For many applications that is unacceptable.

A simple and often useful solution is to use integral numbers and storing the amounts in cents instead of dollars. Then the rounding problem of pure additions and subtractions is under control and for other operations it might at least become easier to deal with the issue. A common mistake that absolutely needs to be avoided is mixing amountInDollar and amountInCent. In Scala it would be a good idea to use different types to make this distinction, so that such errors can be avoided at compile time. In any case it is very important to avoid such numeric types as int of Java that have a weird and hardly controllable overflow behavior where adding positive numbers can end up negative. How absurd, modular arithmetic is for sure not what we want for our money, it is a little bit too socialistic. 😉 Estimations about the upper bound of money amounts of persons and companies and other organizations are problematic, because there can be inflation and there can be some accumulation of money in somebody’s accounts… Even though databases tend to force us to such assumption, but we can make them really huge. So some languages might end up using something like BigInteger or BigNum or BigInt. Unfortunately Java shows one of its insufficiencies here, which makes quite ugly to use for financial applications, because calculations like a = b + c * d for BigInteger appear like this: a = b.{\rm add}(c.{\rm multiply}(d)). The disadvantage is that the formula cannot be seen at one glance, which leads to errors. In principal this problem can be solved using a preprocessor for Java. Maybe a library doing some kind of RPN-notation would possible, writing code like this:

Calculation calc = new Calculation();
calc.push(b)
calc.push(c)
calc.push(d)
calc.add()
calc.multiply()
a = calc.top()

Those who still know old HP calculators (like HP 25 and HP 67 😉 in the good old days) or Forth might like this, but for most of us this is not really cutting it.

Common and useful is actually the usage of some decimal fixed point type. In Java this is BigDecimal, in Ruby it is LongDecimal.
And example in Ruby:

> sudo gem install long-decimal
Successfully installed long-decimal-1.00.01
1 gem installed
....
> irb
irb(main):001:0> require "long-decimal"
=> true
irb(main):002:0> x = LongDecimal("3.23")
=> LongDecimal(323, 2)
irb(main):003:0> y = LongDecimal("7.68")
=> LongDecimal(768, 2)
irb(main):004:0> z = LongDecimal("3.9291")
=> LongDecimal(39291, 4)
irb(main):005:0> x+y
=> LongDecimal(1091, 2)
irb(main):006:0> (x+y).to_s
=> "10.91"
irb(main):007:0> x+y*z
=> LongDecimal(33405488, 6)
irb(main):008:0> (x+y*z).to_s
=> "33.405488"
irb(main):009:0> 

It is interesting to see that the number of digits remains the same under addition and subtraction if both sides have the same number of digits. But the longer number of digits wins otherwise. During multiplication, division and off course during more complex operations many decimal places can become necessary. It becomes important to do rounding and to do it right and in a controlled way. LongDecimal supports the following rounding modes:

ROUND_UP
Round away from 0.
ROUND_DOWN
Round towards 0.
ROUND_CEILING
Round to more positive, less negative numbers.
ROUND_FLOOR
Round to more negative, less positive numbers.
ROUND_HALF_UP
Round the middle and from above up (away from 0), everything below down (towards 0).
ROUND_HALF_DOWN
Round the middle and from above down (towards 0), everything below up (away from 0).
ROUND_HALF_CEILING
Round from the middle onward towards infinity, otherwise towards negative infinity.
ROUND_HALF_FLOOR
Round up to and including the middle towards negative infinity, otherwise towards infinity.
ROUND_HALF_EVEN
Round the middle in such a way that the last digit becomes even.
ROUND_HALF_ODD
Round the middle in such a way that the last digit becomes odd (will be added to long-decimal in next release).
ROUND_UNNECESSARY
Do not round, just discard trailing 0. If that does not work, raise an exception.

Which of these to use should be decided with domain knowledge in mind. The above example could be continued as follows:

irb(main):035:0> t=(x+y*z)
=> LongDecimal(33405488, 6)
irb(main):036:0> 
irb(main):037:0* t.round_to_scale(2, LongDecimal::ROUND_UP).to_s
=> "33.41"
irb(main):038:0> t.round_to_scale(2, LongDecimal::ROUND_DOWN).to_s
=> "33.40"
irb(main):039:0> t.round_to_scale(2, LongDecimal::ROUND_CEILING).to_s
=> "33.41"
irb(main):040:0> t.round_to_scale(2, LongDecimal::ROUND_FLOOR).to_s
=> "33.40"
irb(main):041:0> t.round_to_scale(2, LongDecimal::ROUND_HALF_UP).to_s
=> "33.41"
irb(main):042:0> t.round_to_scale(2, LongDecimal::ROUND_HALF_DOWN).to_s
=> "33.41"
irb(main):043:0> t.round_to_scale(2, LongDecimal::ROUND_HALF_CEILING).to_s
=> "33.41"
irb(main):044:0> t.round_to_scale(2, LongDecimal::ROUND_HALF_FLOOR).to_s
=> "33.41"
irb(main):045:0> t.round_to_scale(2, LongDecimal::ROUND_HALF_EVEN).to_s
=> "33.41"
irb(main):046:0> t.round_to_scale(2, LongDecimal::ROUND_UNNECESSARY).to_s
ArgumentError: mode ROUND_UNNECESSARY not applicable, remainder 5488 is not zero
        from /usr/local/lib/ruby/gems/1.9.1/gems/long-decimal-1.00.01/lib/long-decimal.rb:507:in `round_to_scale_helper'
        from /usr/local/lib/ruby/gems/1.9.1/gems/long-decimal-1.00.01/lib/long-decimal.rb:858:in `round_to_scale'
        from (irb):46
        from /usr/local/bin/irb:12:in `
' irb(main):047:0>

A specialty is that some countries do not use the coins with one of the smallest unit, like 1 cent in the US. In Switzerland the smallest common coin is 5 Rp (5 cent=0.05 CHF). It might be possible to make the bank do a transfer for amounts not ending in 0 or 5, but usually invoices apply this kind of rounding and avoid such exact amounts that could not possibly be paid in cash. This can be dealt with by multiplying the amount by 20, rounding it to 0 digits after the decimal point and divide it by 20 and round the result to 2 digits after the point. In Ruby there is a better way using an advanced feature of LongDecimal called remainder rounding (using the method round_to_allowed_remainders(…) ). Assuming we want to round a number x with n decimal places in such a way that, 10^n\cdot x belongs to one of the residue classes \overline{0} \mod 10 or \overline{5} \mod 10. In this case we are just talking about the last digit, but the mechanism has been implemented in a more general way allowing any set of allowed residues and even a base other than 10. If 0 is not in the set of allowed residues, it may be unclear how 0 should be rounded and this needs to be actually defined with a parameter. For common practical uses the last digit of 0 is allowed, so things work out of the box:


irb(main):003:0> t.round_to_allowed_remainders(2, [0, 5], 10, LongDecimal::ROUND_UP).to_s
=> "33.45"
irb(main):005:0> t.round_to_allowed_remainders(2, [0, 5], 10, LongDecimal::ROUND_DOWN).to_s
=> "33.40"
irb(main):006:0> t.round_to_allowed_remainders(2, [0, 5], 10, LongDecimal::ROUND_CEILING).to_s
=> "33.45"
irb(main):007:0> t.round_to_allowed_remainders(2, [0, 5], 10, LongDecimal::ROUND_FLOOR).to_s
=> "33.40"
irb(main):008:0> t.round_to_allowed_remainders(2, [0, 5], 10, LongDecimal::ROUND_HALF_UP).to_s
=> "33.40"
irb(main):009:0> t.round_to_allowed_remainders(2, [0, 5], 10, LongDecimal::ROUND_HALF_DOWN).to_s
=> "33.40"
irb(main):010:0> t.round_to_allowed_remainders(2, [0, 5], 10, LongDecimal::ROUND_HALF_CEILING).to_s
=> "33.40"
irb(main):011:0> t.round_to_allowed_remainders(2, [0, 5], 10, LongDecimal::ROUND_HALF_FLOOR).to_s
=> "33.40"

In an finance application the rounding methods should probably be defined for each currency, possible using one formula and some currency specific parameters.

LongDecimal can do even more than that. It is possible to calculate logarithms, exponential functions, square root, cube root all to a desired number of decimal places. The algorithms have been tuned for speed without sacrificing precision.

Share Button

RISC und CISC

Vor 20 Jahren gab es einen starken Trend, Mikroprossoren mit RISC-Technologie (reduced instruction set computer), zu bauen. Jeder größere Hersteller wollte so etwas bauen, Sun mit Sparc, Silicon Graphics mit MIPS, HP mit PA-Risc, IBM schon sehr früh mit RS6000, was später, als man auf die Idee kam, das zu vermarkten, als PowerPC rebranded wurde, DEC mit Alpha u.s.w. Zu einer Zeit, als man zumindest in Gedanken noch für möglich hielt Assembler zu programmieren (auch wenn man es kaum noch tat), tat das noch richtig weh. Und Software war doch sehr CPU-abhängig, weil plattformunabhägige Sprache, die es damals selbstverständlich schon lange vor Java gab, einfach wegen des Overheads der Interpretation für viele Zwecke zu langsam waren. So behalf man sich mit C-Programmen mit wahren Orgien an ifdfefs und konnte die mit etwas Glück für die jeweilige Plattform aus CPU und einem UNIX-Derivat kompilieren. Der Wechsel der CPU-Architektur eines Herstellers war damals eine große Sache, z.B. bei Sun von Motorola 680×0 zu Sparc. Und die Assemblerprogrammierung der RISC-CPUs war ein Albtraum, an den sich auch erfahrene Assemblerprogrammierer kaum herangewagt haben. Zum Glück gab es damals schon sehr gut optimierende Compiler für C und Fortran und so konnte man das Thema einem ganz kleinen Personenkreis für die Entwicklung von kleinen Teilen des Betriebssytemkerns und kleinen hochperformanten Teilen großer Libraries überlassen.

Eigentlich sollte RISC ermöglichen, mit derselben Menge an Silizium mehr Rechenleistung zu erzielen, insgesamt also Geld und vielleicht sogar Strom zu sparen. Vor allem wollte man für die richtig coole Server-Applikation, die leider immer etwas zu ressourchenhungrig für reale Hardware war, endlich die richtige Maschine kaufen können. RISC war der richtige Weg, denn so hat man einen Optmierungsschritt beim Compiler, der alles optimal auf die Maschinensprache abbildet, die optimiert dafür ist, schnell zu laufen. Ich wüsste nicht, was daran falsch ist, wenn auch diese Theorie vorübergehend nicht zum Zuge kam. Intel konnte das Problem mit so viel Geld bewerfen, dass sie trotz der ungünstigeren CISC-Architektur immer noch schneller waren. Natürlich wurde dann intern RISC benutzt und das irgendwie transparent zur Laufzeit übersetzt, statt zur Compilezeit, wie es eigentlich besser wäre. Tatsache ist aber, dass die CISC-CPUs von Intel, AMD und Co. letztlich den RISC-CPUs überlegen waren und so haben sie sich weitgehend durchgesetzt.

Dabei hat sich die CPU-Abhängigkeit inzwischen stark abgemildert. Man braucht heute kaum noch Assembler. Die Plattformen haben sich zumindest auf OS-Ebene zwischen den Unix-Varianten angeglichen, so dass C-Programme leichter überall kompilierbar sind als vor 20 Jahren, mit cygwin sogar oft unter MS-Windows, wenn man darauf Wert legt. Applikationsentwicklung findet heute tatsächlich weitgehend mit Programmiersprachen wie Java, C#, Scala, F#, Ruby, Perl, Python u.ä. statt, die plattformunabhängig sind, mittels Mono sogar F# und C#. Und ein Wechsel der CPU-Architektur für eine Hardware-Hersteller ist heute keine große Sache mehr, wie man beim Wechsel eines Herstellers von PowerPC zur Intel-Architektur sehen konnte. Man kann sogar mit Linux dasselbe Betriebssystem auf einer unglaublichen Vielfalt von Hardware haben. Die große Mehrheit der schnellsten Supercomputer, die allermeisten neu vekrauften Smartphones und alle möglichen CPU-Architekturen laufen mit demselben Betriebssystemkern, kompiliert für die jeweilige Hardware. Sogar Microsoft scheint langsam fähig zu sein, verschiedene CPU-Architekturen gleichzeitig zu unterstützen, was lange Zeit außerhalb der Fähigkeiten dieser Firma zu liegen schien, wie man an NT für Alpha sehen konnte, was ohne große finanzielle Zuwendungen seitens DEC nicht aufrechterhalten werden konnte.

Aber nun, in einer Zeit, in der die CPU-Architektur eigentlich keine Rolle mehr spielen sollte, scheint alles auf Intel zu setzen, zum Glück nicht nur auf Intel, sondern auch auf einige konkurrierende Anbieter derselben Architektur wie z.B. AMD. Ein genauerer Blick zeigt aber, das RISC nicht tot ist, sonder klammheimlich als ARM-CPU seinen Siegeszug feiert. Mobiltelefone habe häufig ARM-CPUs, wobei das aus den oben genannten Gründen heute fast niemanden interessiert, weil die Apps ja darauf laufen. Tablet-Computer und Netbooks und Laptops sieht man auch vermehrt mit ARM-CPUs. Der Vorteil der RISC-Architektur manifestiert sich dort nicht in höherer Rechenleistung, sondern in niedrigerem Stromverbrauch.

Ist die Zeit reif und CISC wird in den nächsten zehn Jahren wirklich durch RISC verdrängt?

Oder bleibt RISC in der Nische der portablen stromsparendenen Geräte stark, während CISC auf Server und leistungsfähigen Arbeitsplatzrechnern dominierend bleibt? Wir werden es sehen. Ich denke, dass früher oder später der Vorteil der RISC-Architektur an Relevanz auf leistungsfähigen Servern und Arbeitsplatzrechnern gewinnen wird, weil die Möglichkeiten der Leistungssteigerung von CPUs durch mehr elektronischen Elementen pro Quadratmeter Chipfläche und pro Chip an physikalische Grenzen stoßen werden. Dann die bestmögliche Hardwarearchitektur mit guten Compilern zu kombinieren scheint ein vielversprechender Ansatz.

Die weniger technisch interessierten Nutzer wird diese Entwicklung aber kaum tangieren, denn wie Mobiltelefone mit Android werden Arbeitsplatzrechner mit welcher CPU-Architektur auch immer funktionieren und die Applikationen ausführen, die man dort installiert. Ob das nun plattformunabhängig ist, ob man bei kompilierten Programmen ein Binärformat hat, das mehrere CPUs unterstützt, indem einfach mehrere Varianten enthalten sind oder ob der Installer das richtige installiert, interessiert die meisten Benutzer nicht, solange es funktioniert.

Share Button

PDF mit Ruby erzeugen

Es gibt viele Libraries, die mit Ruby, Perl, Java oder was auch immer man so verwendet, PDF-Dateien erzeugen. Das Prinzip ist oft so, dass man eine Art Formular erstellt, in dem dann Platzhalter mit Daten aus dem Programm gefüllt werden. Im Prinzip sehr ähnlich wie das Generieren von HTML-Seiten in vielen Web-Applikationen.

Heute verwendet man für Webapplikationen mit Ruby on Rails HAML. Die älteren Rails-Entwickler erinnern sich aber noch teilweise daran, dass man früher einmal erb verwendet hat. Man hat also das HTML so hingeschrieben, wie es halt aussieht und die Platzhalter dann mit so etwas wie <%= some_ruby_code => ausgefüllt. Es war sogar möglich, Schleifen und Bedingte Codeteile zu haben, dafür hat man dann so etwas wie

<% number.times do |x| %>
...
<%= function(x) %>
...
<% end %>

geschrieben. In HAML ist das alles viel schöner, weil man eine Syntax hat, die den Ruby und den HTML-Code viel eleganter miteinander integriert. Aber HAML ist für HTML gemacht.

Um nun PDF-Dateien zu generieren, lohnt es sich, Text-Formate anzusehen, die zu PDF konvertiert werden können. Möglich wäre zum Beispiel PostScript, aber auch die Formate heutiger Office-Systeme wie MS-Office und LibreOffice und OpenOffice sind grundsätzlich dokumentiertes XML, also durchaus zugänglich, wenn man viel Zeit hat. Ob nun XML wirklich als Textformat zählt oder doch eher als Binärformat mit einzelnen Merkmalen eines Textformats, muss die Praxis zeigen. Viele XML-Formate sind fast so unzugänglich wie Binärdateien. Wer sich mit diesen Office-Systemen auskennt, kann auch Libraries verwenden, die diese direkt generieren oder die die APIs der entsprechenden Software ansprechen, wenn man eine entsprechende Installation erreichen kann. Auf typischen Serversystemen ist das schon eine gewisse Hürde.

Ein schönes Textformat ist LaTeX oder TeX. Das sind Satzsysteme, die das Layout in einer textbasierten Sprache, man kann sagen einer Programmiersprache, beschreiben. Text wird einfach so geschrieben, für mathematische und chemische Formeln gibt es sehr leistungsfähige Funktionen, die ich hier in diesem Blog auch regelmäßig für Formeln verwende, wenn es nötig ist. Und ansonsten gibt es Macros, die mit „\“ anfangen. Diese Macros machen TeX zu einer vollwertigen, aber nicht sehr zugänglichen Programmiersprache, aber für einfache Layouts kann man sich Muster im Internet oder von Kollegen oder aus Büchern holen und anpassen und das Lernen der Macrosprache weitgehend der Zukunft oder anderen überlassen. Weil das nun wirklich „plain“-Text ist, lässt sich sehr gut mit erb arbeiten und ein LaTeX-Template erstellen, in dem dann die Daten aus der Software eingefüllt werden, einschließlich Dingen wie Tabellen, bei denen z.B. die Anzahl der Zeilen dynamisch ist.

Mit diesem Ansatz generiere ich seit dem Bestehen der Firma IT Sky Consulting GmbH alle Rechnungen, die an Kunden verschickt werden. Es muss wohl funktioniert haben, denn ohne lesbare Rechnungen kann kaum eine Firma mehrere Jahre überleben. 😉

Share Button

Integration numerischer Typen in Programmiersprachen

Rechnen ist ja das, was wir mit den Computern so machen, deshalb heißen sie ja auch Rechner.
Und zum Rechnen brauchen wir die numerischen Typen andauernd, also kann das wohl kein Problem sein, oder?

Es hängt ein bisschen davon ab, was man sich unter numerischen Typen vorstellt. Fließkommazahlen oder irgendeine Art von Ganzzahlen können fast alle, manche sogar beides. Gute Ganzzahlentypen sind aber leider nur selten verfügbar, da die Frage des Überlaufs oft schlecht gelöst ist. Weitere interessante numerische Datentypen sind rationale Zahlen, komplexe Zahlen und Festkomma-Dezimalzahlen.

Doch wie sieht es mit der Integration in die Sprache aus? Man möchte gerne so etwas wie
a = b*c + d*e
schreiben und meint damit, dass eine Zuweisung an a erfolgen soll, die den Wert (b*c) + (d*e) beinhaltet. Wegen „Punktrechnung vor Strichrechnung“ sollte man die Klammern aber weglassen können. Im Fall von Sprachen wie Lisp oder Forth, die eine völlig andere Syntax verwenden, passt diese Infix-Schreibweise natürlich nicht ins Bild und man kann diese Anforderung nicht sinnvoll stellen. In Lisp mit der Präfix-Schreibweise wäre es so etwas wie:
(setq a (+ (* b c) (* d e)))
und in Forth mit seiner Postfix-Schreibweise wäre es etwa so etwas:
b @ c @ * d @ e @ * + a ! .
C, Perl, Ruby, C++, Java, C#, JavaScript, Lua und vielen anderen funktioniert das mit den eingebauten Datentypen recht gut, aber sobald man eigene numerische Datentypen einführt, braucht man so etwas wie „Operator überladen“, was z.B. Lua, Perl, Ruby, C++ und C# können, aber Java und JavaScript nicht. Deshalb fängt man in Java an, für BigDecimal, BigInteger oder eigene Datentypen so etwas wie
a = b.multiply(c).add(d.multiply(e))
zu schreiben, was praktisch unlesbar und damit fehleranfällig ist. Vielleicht kann man sich mit einem Präprozessor behelfen, aber es bleibt ein Gebastel.

Ein anderer Aspekt ist am Beispiel von Java ganz gut zu sehen. Dort soll ja „alles“ ein Objekt sein. Man kann schön Interfaces, Klassen und Methoden schreiben und Verwenden, die sich auf Objekte verlassen, wie z.B. Map. Nun sind diese „primitiven“ Typen leider keine Objekte und man muss diese Wrapper-Klassen wie Integer, Double, Long, Boolean u.s.w. verwenden, was leider umständlich ist, zumal man mit den Wrappern die numerischen Fähigkeiten nicht mehr zur Verfügung hat. Scheinbar wurde das durch Autoboxing und Autounboxing gelöst, aber ich glaube, dass diese Erweiterung mehr Probleme geschaffen als gelöst hat. Nur als Beispiel, was bedeutet
x==y
wenn x und y long oder Long sind? Mal wird die Objekt-Identität und mal der Wert verglichen und ich vergesse immer, ob unboxing oder boxing zum Zuge kommt, wenn man dabei long und Long zusammenkommen lässt. Man kann aber einige spezielle Collection-Klassen finden, die auf Primitive zugeschnitten sind und dadurch ohne Boxing und Autoboxing auskommen, schneller laufen und weniger Speicher verbrauchen. In erster Linie bleibt es aber umständlich, weil man immer wieder diese Sonderfälle für Primitive und zum Teil auch Arrays berücksichtigen muss.

Share Button

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.

Share Button