Devoxx 2013 Part 2

During the time from 2013-11-13 to 2013-11-15 I have been attending the Devoxx-conference in Antwerp in Belgium.
Most of the speeches I have been listening too were just great, like for example:

Share Button

Devoxx 2013 Teil 2

In der Zeit vom 13. bis zum 15. November habe ich die Devoxx-Konferenz in Antwerpen besucht.
Die meisten Vorträge waren wieder sehr gut, z.B.:

Hier ist noch ein guter Blogbeitrag zur Devoxx 2013.

Share Button

UTF-16 bei Zeichenketten in Java

English

Zeichenketten in Java und in vielen JVM-Sprachen enthalten Unicode-Zeichen und sind mit utf-16 codiert. Es war sehr weitsichtig, schon in den 90er-Jahren an Unicode zu denken und das als alleinige Möglichkeit vorzusehen. Man hat sich so erspart, das Durcheinander zu haben, welche Zeichenkette jetzt in welcher Codierung vorliegt, weil alle gleich sind, und auch zumindest für gängige europäische und westasiatische Sprachen die Handhabung vereinfacht, weil da ein Zeichen zwei Bytes sind. Der Nachteil mit dem etwas größeren Speicherverbrauch spielt fast keine Rolle, weil man mit ein paar Zeichenketten sehr selten an die Grenzen stößt. Mit 64-Bit-CPUs (und 64-Bit-JVM) kann man ja fast beliebig viel Hauptspeicher einsetzen.

Aber es gibt auch Applikationen, die trotzdem mit ihrem Speicherverbrauch an Grenzen stoßen. So könnte man auf die Idee kommen, eigene Zeichenketten zu verwenden, die utf-8 statt utf-16 verwenden. Die entsprechende Konvertierung ist nicht schwierig und sicher im Netz zu finden, sogar in der eigenen Java-Libary. Leider sind die Zeichenketten aber an so vielen Stellen vorgesehen und man kann sie nicht einfach durch eine andere Klasse ersetzen. Was bleibt sind also lästige explizite Konvertierungen. Aber allein mit diesem Ansatz kann man natürlich eine Menge Speicher sparen.

Eine andere Idee wäre es, Zeichenketten zu komprimieren. Wenn sie lang genug sind, funktionieren Algorithmen wie gzip auf einer einzelnen Zeichenkette. Das erschwert natürlich den selektiven Zugriff auf einzelne Teile der Zeichenkette, aber das Problem hat man schon mit utf-8, wo man nicht genau weiß, ab welchem Byte nun das n-te Zeichen beginnt, ohne sie von Anfang an durchzugehen. Aber wir müssen auch damit rechnen, dass es nicht einzelne lange Zeichenketten gibt, sondern sehr viele, die jeweils zu kurz sind, um für sich genommen mit einer Kompression kleiner zu werden. Wenn man nun aber die Gesamtheit der Zeichenketten ungefähr kennt, kann man eine Komprimierung generieren, die für diesen Satz von Zeichenketten gute Ergebnisse bringt. Das bedeutet, dass man ähnlich wie bei der Umstellung von utf-16 auf utf-8 einzelne Byte-Sequenzen der unkomprimierten Zeichenkette durch anderen Byte-Sequenzen für die komprimierte Zeichenkette ersetzt. Die häufig vorkommenden Sequenzen werden durch kürzere ersetzt, die selteneren durch längere. So kann man mit weniger Bytes auskommen. Die Regel, wie das Komprimieren und Dekomprimieren funktioniert, muss man nur einmal für das ganze Programm speichern und nicht wie bei der ersten Idee für den Einsatz von gzip in jeder Zeichenkette einzeln.

Es empfiehlt sich unbedingt, die folgenden Punkte zu beachten:

  1. Sind wirklich die Zeichenketten ein Problem mit ihrem Speicherverbrauch?
  2. Lässt sich dieses durch andere, einfachere Optimierungen der Software lösen?
  3. Lasst es sich durch Hardware lösen?
  4. Gibt es schon geeignete oder adaptierbare Lösungen im Netz? Oder in der eigenen Organisation?
  5. Eine neue String-Klasse ist so grundlegend, dass man sie unbedingt gut testen muss. Unit-Tests sollten wirklich ausführlich sein.
Share Button

Devoxx 2013 Teil 1

Ich besuche in dieser Woche die Devoxx-Konferenz in Antwerpen. Es gibt wieder viele interessante und auch unterhaltsame Vorträge über Software-Architektur, Entwicklungsprozesse, Security, Team-Organisation und neue Technologien. Dart 1.0 als möglicher Ersatz für Javascript ist zum Beispiel vorgestellt worden. Es ist immer gut, wenn man noch etwas dazu lernen kann, denn Leute, die schon alles wissen, bremsen früher oder später ihre Teams oder ihre Projekte aus, weil alles Neue abgelehnt wird…

Ich hoffe, dass ich nächstes Jahr wieder dort sein kann.

Mehr Details dazu kommen später.

Voriges Jahr war ich auch dort.

Share Button

Devoxx 2013 part 1

2013 I am visiting Devoxx in Antwerp again. It is quite interesting, because they have invited good speakers who know their stuff and are fun to listen to.

So I am learning a lot about software architecture, software development, team organization, security and new technologies. It is always good not to know everything and to be able to learn new stuff, because people who know everything already usually slow down their projects sooner or later. So I hope to be there again next year. 😉

I will write more in another post …

Btw. last year was great as well. 😉

Share Button

Scala, Ruby, Perl,… – wann nimmt man was?

Wer einen goldenen Hammer hat, für den sieht jede Schraube wie in Nagel aus. Aber wir haben einen riesigen Werkzeugkasten und wie man sieht, überschneiden sich tatsächlich manche Werkzeuge in ihren Einsatzbereichen, aber das Universalwerkzeug ist nicht wirklich in Sicht oder doch nicht wirklich in allen Bereichen mit den Spezialwerkzeugen konkurrenzfähig.

Oft hat man ja Altlasten, also vorhandene Applikationen, die man erweitern oder ergänzen soll oder es sollen sogar neue, „in die Landschaft passende“ Applikationen hinzugefügt werden. Dann landet man bei Cobol, Railo, Fortran, C, Java, C#, C++, PL/SQL, PL/1, (Visual)Basic u.s.w. Wobei diese zum Teil sogar ihre sehr große „Nische“ haben, in der sie noch aktuell sind. Dass C für Systemprogrammierung noch sehr aktuell und fast konkurrenzlos ist, sei unbenommen.

Wenn keine Vorgaben durch Bibliotheken, Altlasten, IT-Landschaft u.s.w. bestehen, ist es natürlich interessant, in der zur Verfügung stehenden Zeit möglichst viel machen zu können. Eine Technologie, die einen zwingt, viel Zeit mit trivialen Aufgaben zu verbringen und die eigentlich interessanten Dinge in einem Wust von trivialem Code zu verstecken, den man nun einmal schreiben muss, darf man dann auch schon einmal hinterfragen. Letztlich sind zwei Wege vielversprechend, um mit wenig Code viel auszudrücken und letzlich in wenig Zeit viel zu entwickeln: Die funktionalen Sprachen wie z.B. F#, Clojure, Erlang, Elixir und Haskell. Oder die Skriptsprachen wie Ruby, Perl, Perl6 (wenn es mal fertig wird), Python und PHP. Natürlich überschneidet sich das ein Stück weit, weil einige funktionale Sprachen auch ein bißchen wie Skriptsprachen einsetzbar sind und einige Skriptsprachen auch gewisse funktionale Konstruktionen unterstützen.

Letztlich erweisen sich die funktionalen Sprachen als vielversprechend, wenn es darum geht, sehr leistungsstarke Applikationen zu entwickeln, die einen hohen Durchsatz und eine hohe Parallelisierung der Verarbeitung verwirklichen. Twitter soll mit Scala diesen Weg gegangen sein. Grundsätzlich bieten alle ernsthaften funktionalen Sprachen hier einige Möglichkeiten. F# lässt sich übrigens auch mit Mono kombiniert unter Linux verwenden. Vielleicht hat Erlang noch einen kleinen Vorteil, weil es schon auf VM-Ebene für diesen Einsatzbereich optimiert ist. Diese VM lässt sich aber auch mit Elixir verwenden. Aber man hat die Wahl zwischen mehreren Wegen.

Für viele Web-Applikationen hat sich Ruby als gut geeignet erwiesen, man sieht aber, dass es einige sehr gute PHP-Applikationen gibt. z.B. MediaWiki, die Software, mit der Wikipedia läuft. Allerdings zeichnet sich im Moment ein Trend ab, mehr von der Logik in Javascript auf der Client-Seite zu implementieren und serverseitig (fast) nur noch Webservices mit REST anzubieten, die die eigentliche Businesslogik und die Zugriffe auf die Daten zur Verfügung stellen. Diese REST-Services kann man natürlich in Ruby entwickeln; aber da gibt es viele Wege…

Ruby und vor allem Perl sind aber auch sehr stark, wenn es darum geht, Textdateien zu verarbeiten. Man kann diese nach Mustern durchsuchen, umgruppieren und umbauen und damit schöne Auswertungen machen. Für sehr große Datenmengen sollte man sich natürlich noch etwas eingehendere Gedanken machen, weil dann der Durchsatz und die Parallelisierung plötzlich mehr Bedeutung bekommen als das eigentlich Parsen des Texts. Aber man kann noch viel mehr…

Eine große Applikation kann diese Dinge auch kombinieren. GNU-Emacs ist eine sehr altes Beispiel, dass hier einen noch heute sehr aktuellen Ansatz verfolgt. Die Grundfunktionalität ist in C entwickelt und die weitergehenden Funktionen und Erweiterungen alle in Emacs-Lisp. So läßt sich ohne viel Aufwand einen Erweiterung einbinden, was nicht so leicht geht, wenn man erst einmal neu kompliieren muss. Die Idee lässt sich auch heute noch aufgreifen, wenn man eine Applikation z.B. in Scala entwickelt und dann die Möglichkeit anbietet, diese über Ruby- oder Groovy-Scripte anzusprechen, zu erweitern und zu konfigurieren.

Wenn man einmal an Häuser denkt, ist die Idee nicht so abwegig. Das eigentliche Haus ist relativ stabil aus Beton, Stein und Holz gebaut und bleibt in der Regel jahrzehntelang unverändert. Die Möbel sind selten aus Beton gegossen und eher flexibler (auch wenn sie vielerorts jahrzehntelang gleich stehen).

Share Button

Quadrat- und Kubikwurzeln berechnen vor 30 Jahren und heute ;-)

Unsere Rechner können sehr viele Rechenoperationen schon auf der CPU erledigen, wenn es darum geht, mit den Standardtypen (z.b. double, dem gängigen 8-Byte-Fließkommaformat) zu rechnen. Das war gegen Anfang der 80er Jahre noch nicht so, da konnten typische CPUs nur gerade mit 8-Bit-Ganzzahlen addieren, subtrahieren und ein paar Bit-Operationen ausführen und doch ließ sich daraus alles aufbauen. Langzahladdition und -subtraktion waren trivial, Multiplikation und Division etwas schwieriger, aber noch gut machbar. Aber für die Quadratwurzeln musste man schon etwas genauer überlegen. Das mitgelieferte Basic konnte das für 5-Byte-Fließkommazahlen, aber das Verfahren war einfach nur dumm und langsam, den es wurde der Logarithmus genommen, halbiert und dann die Exponentialfuntion. Mathematisch völlig richtig, aber eben langsam und mit unnötigen Rundungsfehlern behaftet. Wer sich ein bisschen mit dem Thema auskennt, landet recht schnell bei dem Newton-Verfahren. Man schätzt die Quadratwurzel, z.B. von 2, dividiert 2 durch den Schätzwert und nimmt dann den Mittelwert von Schätzung und Quotient für die nächste Iteration. Zu offensichtlich, um es nicht so zu machen und in der Praxis auch ganz brauchbar. Es gibt aber ein Verfahren, wie man früher ähnlich wie die Division auch die Quadratwurzeln „handschriftlich“ berechnen konnte und dieses Verfahren lässt sich sehr gut verwenden, um eine Quadratwurzelberechnung zu schreiben. Hier ist eine Ruby-Implementierung, die von Ganzzahlen ausgeht:
Zu einer ganzen Zahl x \ge 0 werden ganze Zahlen r \ge 0 und s \ge 0 gesucht so dass x = r + s^2 und (s+1)^2 > x gilt.

  def check_is_int(x, name="x")
    raise TypeError, "#{name}=#{x.inspect} must be Integer" unless x.kind_of? Integer
  end

  #
  # helper method for internal use: checks if word_len is a reasonable
  # size for splitting a number into parts
  #
  def check_word_len(word_len, name="word_len")
    raise TypeError, "#{name} must be a positive number <= 1024" unless (word_len.kind_of? Fixnum) && word_len > 0 && word_len <= 1024
    word_len
  end

  #
  # split number (Integer) x into parts of word_len bits each such
  # that the concatenation of these parts as bit patterns is x
  # (the opposite of merge_from_words)
  #
  def split_to_words(x, word_len = 32)
    check_word_len(word_len)
    check_is_int(x, "x")
    m = x.abs
    s = (x <=> 0)
    bit_pattern = (1 << word_len) - 1
    words = []
    while (m != 0 || words.length == 0) do
      w = m & bit_pattern
      m = m >> word_len
      words.unshift(w)
    end
    if (s < 0) then
      words[0] = -words[0]
    end
    words
  end


  #
  # calculate the an integer s >= 0 and a remainder r >= 0 such that
  # x = s**2 + r and s**2 <= x < (s+1)**2
  # the wordwise algorithm is used, which works well for relatively
  # large values of x.  n defines the word size to be used for the
  # algorithm.  It is good to use half of the machine word, but the
  # algorithm would also work for other values.
  #
  def sqrtw_with_remainder(x, n = 16)
    check_is_int(x, "x")
    check_is_int(n, "n")

    n2 = n<<1
    n1 = n+1
    check_word_len(n2, "2*n")

    s = (x <=> 0)
    if (s == 0) then
      return [0, 0]
    elsif (s < 0)
      a = sqrtw_with_remainder(-x)
      return [ Complex(0, a[0]), a[1]]
    end

    xwords = split_to_words(x, n2)
    if (xwords.length == 1) then
      return sqrtb_with_remainder(xwords[0])
    end

    xi = (xwords[0] << n2) + xwords[1]
    a  = sqrtb_with_remainder(xi)
    yi = a[0]
    if (xwords.length <= 2) then
      return a
    end

    xi -= yi*yi
    2.upto(xwords.length-1) do |i|
      xi = (xi << n2) + xwords[i]
      d0 = (yi << n1)
      q  = (xi / d0).to_i
      q0 = q
      j  = 0
      was_negative = false
      while (true) do
        d = d0 + q
        r = xi - (q * d)
        break if (0 <= r && (r < d || was_negative))
        if (r < 0) then
          was_negative = true
          q = q-1
        else
          q = q+1
        end
        j += 1
        if (j > 10) then
          break
        end
      end
      xi = r
      yi = (yi << n) + q
    end
    return [ yi, xi ]
  end

  #
  # calculate an integer s >= 0 and a remainder r >= 0 such that
  # x = s**2 + r and s**2 <= x < (s+1)**2
  # the bitwise algorithm is used, which works well for relatively
  # small values of x.
  #
  def sqrtb_with_remainder(x)
    check_is_int(x, "x")

    s = (x <=> 0)
    if (s == 0) then
      return [0, 0]
    elsif (s < 0)
      a = sqrtb_with_remainder(-x)
      return [ Complex(0, a[0]), a[1]]
    end

    xwords = split_to_words(x, 2)
    xi = xwords[0] - 1
    yi = 1

    1.upto(xwords.length-1) do |i|
      xi = (xi << 2) + xwords[i]
      d0 = (yi << 2) + 1
      r  = xi - d0
      b  = 0
      if (r >= 0) then
        b  = 1
        xi = r
      end
      yi = (yi << 1) + b
    end
    return [yi, xi]
  end

Daraus lässt sich dann relativ einfach eine Quadratwurzelfunktion mit entsprechender Nachkommstellenberechnung bilden.

Witzerweise lässt sich das Verfahren auch für Kubikwurzeln sinngemäß anwenden.

Hier ein kleiner Test:

irb(main):138:0> sqrtw_with_remainder(2)
=> [1, 1]
irb(main):139:0> sqrtw_with_remainder(200)
=> [14, 4]
irb(main):140:0> sqrtw_with_remainder(20000)
=> [141, 119]
irb(main):141:0> sqrtw_with_remainder(2000000)
=> [1414, 604]
irb(main):142:0> sqrtw_with_remainder(200000000000000000000000000000000000000000000000000000000000)
=> [447213595499957939281834733746, 228299936041363866321288807484]
irb(main):143:0> sqrtw_with_remainder(2000000000000000000000000000000000000000000000000000000000000)
=> [1414213562373095048801688724209, 1974464361663955412145937324319]
irb(main):144:0> sqrtw_with_remainder(3000000000000000000000000000000000000000000000000000000000000)
=> [1732050807568877293527446341505, 3021967735564464902990914334975]
irb(main):145:0> sqrtw_with_remainder(3)
=> [1, 2]
irb(main):146:0> sqrtw_with_remainder(300)
=> [17, 11]
irb(main):147:0> sqrtw_with_remainder(30000)
=> [173, 71]
irb(main):148:0> sqrtw_with_remainder(3000000)
=> [1732, 176]
Share Button