Über unsMediaKontaktImpressum
Martin Boßlet 23. Mai 2017

Memoisation in Ruby [Teil 1]

Memoisation dient als eine Art "Micro-Caching", um performancekritische Stellen im Code zu optimieren. © Gnel Karapetyan / Fotolia.com
© Gnel Karapetyan / Fotolia.com

Memoisation ist ein willkommenes Hilfsmittel, um mit wenig Aufwand eine deutliche Leisterungssteigerung beliebigen Codes zu erreichen, indem man wiederholte Aufrufe von zeitkritischen Segmenten nur einmalig ausführt und das Ergebnis für alle folgenden Zugriffe im Speicher vorhält. Neben diesem, dem allgemeinen Caching sehr ähnlichen Anwendungsfall, spielt die Memoisation aber gerade auch bei funktionalen Sprachen eine große Rolle, um z. B. "Lazy Evaluation" zu realisieren. Im Folgenden bringe ich Ihnen die "klassische" Form von Memoisation in Ruby näher, um Ihnen darüberhinaus weitere Ansätze vorzustellen, die bestimmte Anforderungen erfüllen, welche die klassische Form nicht zu leisten vermag.

Bedingte Zuweisung mit ||=

Wer sich längere Zeit mit Ruby und/oder Rails beschäftigt, stößt früher oder später auf den Operator für bedingte Zuweisung: ||=. Was erst, falls Sie getypte Sprachen gewohnt sind, kryptisch anmutet, geht nach kurzer Eingewöhnung aber schnell in Fleisch und Blut über. Oft handelt es sich dabei um das Zuweisen eines Standardwerts zu einem Funktionsargument, welches optional ist und daher nil sein kann, z. B.

def fn(a, b=nil)
  b ||= DEFAULT_VALUE
  do_something_with(a, b)
end

Die Intention dabei ist es, zu prüfen, ob b bereits einen Wert besitzt, und nur, wenn dies nicht der Fall ist, b den Standardwert DEFAULT_VALUE zuzuweisen. Dass dies auf so elegante Weise funktioniert, verdanken wir zwei Eigenschaften:

  1. Der bedingten Evaluierung boolescher Ausdrücke [1] sowie
  2. der Tatsache, dass nil in booleschen Ausdrücken als false gewertet wird und alle Objekte außer false und nil als true.

Überraschenderweise ist es allerdings ein Trugschluss, dass a ||= b äquivalent ist zu a = a || b. Tatsächlich ist a ||= b äquivalent zu a || a = b, d. h. die eigentliche Zuweisung findet nur dann statt, wenn a zu false ausgewertet wird [2].

Memoisation durch bedingte Zuweisung

Doch zurück zum eigentlichen Thema. Früher oder später treffen Sie auf
eine Zeile ähnlich der folgenden, z. B. in einem Rails-Controller:

def current_user
  @_current_user ||= User.find(session[:id])
end

Wenn Sie dies einmal stur als bedingte Zuweisung lesen, wird der Sinn eines solchen Ausdrucks etwas klarer:

Erster Aufruf von current_user

@_current_user wurde noch nicht zugewiesen, ist also schlichtweg noch nicht definiert. Daher wird also der rechte Teil ausgeführt und der User anschließend @_current_user zugewiesen.

Zweiter und folgende Aufrufe

Für alle folgenden Aufrufe gilt, dass @_current_user der User zuvor bereits zugewiesen wurde, daher wird die Instanzvariable zu true ausgewertet und der rechte Zuweisungsteil wird nicht mehr ausgeführt.

Sie haben also erreicht, dass bei einem Aufruf von current_user der unter Umständen "teure" Zugriff User.find(session[:id]) nur einmalig ausgeführt werden muss, alle folgenden Zugriffe auf current_user liefern das User-Objekt direkt aus dem Speicher, genauer gesagt als Wert der Instanzvariablen @_current_user.

Sollte current_user z. B. aus einer View heraus mehrfach aufgerufen werden, muss ein Datenbankzugriff nur einmalig erfolgen, statt erneut für jeden einzelnen Aufruf.

Somit erschließt sich der Sinn von Memoisation als klassischer "Time/Memory Tradeoff": Man opfert Arbeitsspeicher, um die Ergebnisse zeitaufwändiger Berechnungen nur einmalig berechnen zu müssen und fortan im Speicher vorhalten zu können.

Vorsicht bei false und nil

Vielleicht haben Sie sich bereits gewundert, was passiert, wenn der Wert, der bei der initialen Zuweisung berechnet wird, sich als false ergibt? Eine berechtigte Frage, denn der Wert false macht Ihnen bei Ihrem Vorhaben zur Memoisierung einen Strich durch die Rechnung:

def payment_required?
  @_payment_required ||= expensive_calculation_resulting_in_false
end

Falls wir annehmen, dass expensive_calculation_resulting_in_false als false berechnet wird, so wird konsequenterweise auch @_payment_required mit false besetzt und bei weiteren Aufrufen von payment_required? wird der rechte Teil wieder und wieder ausgeführt, obwohl die Instanzvariable zur Memoisation längst zugewiesen wurde. Die gleichen Probleme ergeben sich natürlich, wenn die ursprüngliche Berechnung nil als Ergebnis hat.

Wie können Sie sich vor diesem Problem schützen? Die Antwort ergibt sich, wenn wir analysieren, was das eigentliche Kriterium ist, wonach wir entscheiden, ob die Zuweisung bereits durchgeführt wurde oder nicht. Es hat nämlich im Grunde genommen nichts damit zu tun, welcher Wert sich bei der Initialisierung ergibt, sondern vielmehr damit, ob die Instanzvariable, die den Wert zwischenspeichert, bereits existiert oder nicht. Im ersten Durchlauf gibt es @_payment_required nämlich noch gar nicht, sondern es wird just in diesem Moment definiert! Bei allen folgenden Aufrufen ist die Instanzvariable dann bereits definiert.

Zum Glück bietet Ruby uns die Möglichkeit, exakt diesen Fall zu überprüfen:

def payment_required?
  return @_payment_required if defined?(@_payment_required)
  @_payment_required = expensive_calculation_resulting_in_false
end

defined? ist dabei tatsächlich ein Operator und keine Methode [3], damit man z. B. auch die Existenz lokaler Variablen prüfen kann, die unter Umständen gar nicht deklariert wurden:

defined?(abc) # => nil

Wäre defined? eine Methode und kein Operator, würde dieser Aufruf zu einem Fehler bei der Ausführung führen.

Auch wenn sie nicht mehr so kurz und prägnant erscheint wie die Form mit der bedingten Zuweisung, sollte man in der Praxis doch die Variante mit defined? vorziehen, da sie Fehler bedingt durch false und nil im Voraus ausschließt.

Wann nutze ich Memoisation und wann nicht?

Es wird augenblicklich klar, dass die Vorteile von Memoisation verpuffen, wenn der Code-Teil, dessen Ergebnis es zu speichern gilt, nur einmal aufgerufen wird. Möchte man eine Methode mit Argumenten memoisieren, macht dies nur Sinn, wenn die Menge der möglichen Argumente überschaubar bleibt. Sollten diese in der Mehrheit unterschiedlich sein, kommt der Memoisationseffekt kaum zum Tragen. Ein anderer Fall, bei dem sich Memoisation nicht lohnt: Wenn der memoisierte Code-Teil so schnell ausgeführt werden kann, dass sich der Overhead der Memoisation unter Umständen sogar negativ auf die Laufzeit auswirken würde.

Im Kontext von Rails z. B. sollte man sich bewusst sein, dass die meisten Objekte nur für die Dauer eines einzelnen Requests bestehen, z. B. Controller werden pro Request jedes Mal neu erzeugt (dazu gleich mehr). Folglich lohnt sich Memoisation auch nur dann, wenn der memoisierte Teil mehrfach während ein- und desselben Requests aufgerufen wird.

Gefahr von Speicherlecks bei langlebigen Objekten

Vorsicht ist geboten, wenn ein Objekt, welches Memoisation nutzt, von weiteren Objekten referenziert wird. Sollte eines der referenzierenden Objekte z. B. über Requestgrenzen hinweg Bestand haben, läuft man Gefahr, ein Speicherleck zu schaffen. Obwohl das referenzierte Objekt, welches Memoisation implementiert, unter Umständen nicht mehr gebraucht wird, wird es dennoch nicht vom Garbage Collector erfasst, weil die Referenz innerhalb des langlebigen Objekts weiterhin Gültigkeit besitzt. Ähnliches kann auch passieren, wenn das memoisierende Objekt selbst z. B. als globale Singleton-Instanz oder Konstante Request-Grenzen überdauert. Nehmen wir als (zugegebenermaßen recht konstruiertes) Beispiel:

class MemoizedUsers

  def initialize
    @users = {}
  end

  def []=(id, user)
    @users[id] = user
  end

  def [](id)
    @users[id]
  end

end

USER_CACHE = MemoizedUsers.new

class UsersController

  def show
    id = params[:id]
    return USER_CACHE[id] if USER_CACHE[id]
    USER_CACHE[id] = User.find(id)
  end

end

Da USER_CACHE als Konstante niemals vom Garbage Collector erfasst wird, tummeln sich mit zunehmender Laufzeit immer mehr User-Objekte in USER_CACHE. Es wird immer mehr Speicher verbraucht, der nicht wieder freigegeben werden kann – irgendwann kommt es unausweichlich zum NoMemoryError.

IT-Tage 2017 - Softwareentwicklung

Thread-Safety-Probleme beim Zugriff mehrerer Threads

Wie vorhin erwähnt erzeugt Rails für jeden Request eigene Controller-Instanzen und schafft somit eine "Shared Nothing Architecture" [4]. Und dies aus gutem Grund. Denn würde man Controller-Instanzen über Requests hinweg wiederverwenden, würde sich die Anwendung schlagartig verkomplizieren: Man müsste fortan den Zugriff auf geteilte Objekte synchronisieren und darauf achten, dass Thread-lokale Zustände eigens und unabhängig verwaltet werden. Obwohl technisch möglich, vermeidet man eine solche Architektur, da sie fehleranfällig ist, schlecht skaliert (wegen der Flaschenhälse bei der Synchronisation) und letztlich nur Frust bringt. Die Nachteile überwiegen bei weitem die Vorteile, die man durch die geringere Allokation von Objekten gewinnen würde.

Und gerade weil Rails diesen Ansatz wählt, müssen wir uns bei der Entwicklung selten Gedanken über Threads und etwaige Synchronisationsprobleme machen. In Bezug auf Memoisation bilden hier allerdings Singleton-Objekte oder Konstanten, die Request-Grenzen überdauern, eine Ausnahme, auf die es zu achten gilt. In solchen Fällen können potenziell mehrere Threads gleichzeitig auf ein Objekt zugreifen, was zu Race Conditions bei der Memoisierung führen kann.

Ein Beispiel für eine Race Condition

Um die Problematik zu verdeutlichen, sehen wir uns folgendes Beispiel an:

class Shared

  attr_reader :counter

  def initialize
    @counter = 0
    @mutex = Mutex.new
  end

  def expensive_computation
    @result ||= begin
      # To force the issue, uncomment
      # sleep 0.001
      @mutex.synchronize do
        @counter +=1
      end
      42
    end
  end

end

1000.times do
  shared = Shared.new

  5.times.map do
    Thread.new do
      shared.expensive_computation
    end
  end.map(&:join)

  if shared.counter != 1
    puts "Danger: #{shared.counter}"
  end
end

Wenn Sie dieses Beispiel ausführen, tritt das Problem je nach verwendeter Ruby-Version mit entsprechend höherer oder niedrigerer Wahrscheinlichkeit auf: Mit CRuby (der Standardversion, die Sie z. B. von ruby-lang.org beziehen) ist die Wahrscheinlichkeit geringer, während bei JRuby die Wahrscheinlichkeit wesentlich höher ist. Der Grund hierfür ist das GIL (Global Interpreter Lock), was dazu führt, dass in CRuby immer nur genau ein Thread und ein CPU-Kern zu gegebener Zeit Code ausführen kann. Bei einer Implementation wie JRuby, die echte Parallelität unterstützt und diese Einschränkung nicht besitzt, tritt das Problem entsprechend öfter auf. Wenn Sie den Code aber oft genug mit CRuby ausführen, werden Sie auch dort das Problem antreffen. Dies dient gleichzeitig auch als Gegenbeweis für die falsche Annahme, dass das GIL CRuby-Code automatisch Thread-sicher macht [5,6,7].

Was genau ist das Problem mit obigem Code? Obwohl wir einen Mutex verwenden, um das Hochzählen von counter selbst gegen Race Conditions abzusichern, passiert es, dass counter nicht gleich 1 ist. Doch das war die eigentliche Intention, denn Memoisation soll uns ja genau diesen Fall garantieren, dass Shared::expensive_computation eben nur genau ein einziges Mal ausgeführt wird. Und doch wird es oft genug zweifach oder sogar noch öfter ausgeführt. Der Grund ist, dass die bedingte Zuweisung kein atomarer Ausdruck ist. Vielmehr wird @result erst ausgelesen, um zu prüfen, ob es zu true evaluiert, und falls nicht, wird der begin-Block ausgeführt, und am Ende seines Ergebnisses @result zugewiesen. Vereinfacht passiert dies:

1. Lese @result
2. Prüfe @result == true
    2.1 Falls Ja mit 3. fortfahren
    2.2 Falls Nein:
        2.2.1 Führe begin-Block aus und erhalte Ergebnis
        2.2.2 Weise Ergebnis @result zu
3. Gebe @result zurück

Die Race Condition kann nun wie folgt auftreten. Nehmen wir an, zwei Threads, T1 und T2, rufen Shared::expensive_computation auf. Nehmen wir weiter an, T1 führt 1. und 2. aus, und @result ist noch unberührt, hat also den Wert nil. T1 will nun also folgerichtig mit 2.2 weitermachen. Nehmen wir nun an, dass in genau diesem Moment der Thread-Scheduler einen Context Switch veranlässt und somit T1 angehalten wird und danach T2 angestoßen wird. T2 führt nun 1. aus, danach 2. und jetzt macht sich das Problem bemerkbar. Obwohl T1 sich bereits in dem Code-Zweig befindet, wo der begin-Block ausgeführt wird und letzten Endes dessen Ergebnis @result? zugewiesen wird, ist dies zum jetzigen Zeitpunkt noch nicht geschehen. Das bedeutet also, dass @result nach wie vor nil ist, und daher T2 genauso mit 2.2 fortsetzt, wie das T1 schon zuvor begonnen hatte. Egal, wie die weiteren Context Switches von T1 und T2 nun in der Folge verlaufen, Fakt ist, dass 2.2. von beiden Threads ausgeführt wird und somit doppelt ausgeführt wird. Wenn @result aber erst einmal gesetzt ist, tritt dieses Problem im weiteren Verlauf natürlich nicht mehr auf. Es ist also nur die Initialisierung von @result, die Probleme bereiten kann.

Race Conditions vermeiden

Was also tun, um dieses Problem zu vermeiden? Die naheliegende Lösung: Auf Memoisation in solchen Fällen verzichten. Dies ist aber natürlich keine befriedigende Antwort, da man sicher nicht ohne Grund den entsprechenden Code memoisieren will, etwa weil es aus Performancegründen einfach nicht möglich ist, die entsprechende Stelle für jeden Thread erneut auszuführen. Oft kann man aber damit leben, dass der Code zur Memoisation doppelt oder mehrfach ausgeführt wird und akzeptiert dies stillschweigend. Dennoch muss man sich des Problems bewusst sein, da es äußerst schwierig zu debuggen ist, sollte es dann doch irgendwann einmal auftreten. Leider ist es häufig der Fall, dass solche Probleme erst in Produktion auftreten, weil beim Entwickeln oder in der Testumgebung einfach noch nicht genügend Traffic vorhanden war, um das Problem zu forcieren.

Es gibt aber Fälle, wo mehrfache Ausführung absolut inakzeptabel ist, etwa weil mehrfaches Ausführen schlicht unmöglich ist. Eine Lösung in solchen Fällen ist im Code-Beispiel bereits angedeutet: Man nutzt einen Mutex, um die Zugriffe programmatisch zu synchronisieren. Wenn wir im obigen Beispiel Shared::expensive_computation entsprechend synchronisieren, indem wir den synchronize-Block nach außen ziehen, ist das Problem gelöst.

def expensive_computation
  @mutex.synchronize do
    @result ||= begin
      @counter +=1
      42
    end
  end
end

Double-Checked Locking

Allerdings bringt diese Lösung einen Nachteil mit sich. Die Synchronisation via Mutex kostet natürlich Zeit und kann sich schnell als Flaschenhals erweisen, wenn die memoisierte Ressource entsprechend häufig frequentiert wird. Wie oben bereits ausgeführt, ist dies doppelt ärgerlich, weil ja eigentlich nur die Initialisierung von @result anfällig für Race Conditions ist. Sobald einmal geschehen, ist die Synchronisation in der Folge überflüssig. Und doch wird jeder Zugriff mit obiger Lösung synchronisiert, egal ob @result bereits initialisiert wurde oder nicht.

Gibt es eine Lösung, die genau das tut, was wir uns wünschen? Also allein die Initialisierung mittels Synchronisation abzusichern und danach unsynchronisierten Zugriff zu erlauben? Es gibt sie in der Tat, jedoch ist sie komplizierter, als man zunächst annehmen möchte. Die Lösung wird allgemein als Double-Checked Locking [8] bezeichnet. In Ruby, angewandt auf unser Beispiel sähe dies so aus:

def expensive_computation
  unless defined?(@result)
    @mutex.synchronize do
      unless defined?(@result)
        @counter +=1
        @result = 42
      end
    end
  end

  @result
end

Wir prüfen erst generell, ob @result initialisiert wurde. Klären wir erst den einfachen Fall, dass dies bereits geschehen ist. Dann gibt es auch nichts mehr zu tun, wir geben @result direkt zurück – ohne Synchronisation. Interessant ist der Fall, dass @result noch nicht initialisiert wurde. Da wir in diesem Fall synchronisieren müssen, ist die synchronize-Anweisung noch keine Überraschung. Überraschend ist allerdings die folgende erneute Prüfung, ob @result initialisiert wurde. Dies erscheint erst einmal nicht intuitiv, schließlich haben wir dies doch bereits zuvor schon geprüft. Wieso ist es also nötig, erneut zu prüfen? Stellen wir uns dazu wieder zwei Threads T1 und T2 vor, die beide obigen Code ausführen. T1 prüft, ob @result initialisiert wurde, was noch nicht geschehen ist, und läuft nun auf den synchronize-Block auf. Nehmen wir erneut an, dass in genau diesem Moment der Context Switch geschieht und T2 übernimmt. T2 führt die gleichen Schritte aus und auch hier ist @result noch nicht initialisiert, also läuft auch T2 auf den synchronize-Block auf. Nehmen wir an, der Thread-Scheduler gewährt T2 Einlass in den Block, T2 führt den Block aus und initialisiert in der Folge @result. Wenn jetzt der Context Switch zurück zu T1 erfolgt und T1 Einlass in den synchronized-Block gewährt wird, dann weiß T1 an dieser Stelle erst einmal nichts davon, dass T2 @result bereits initialisiert hat. Wir erkennen also, dass Eintritt in den synchronized-Block nicht gleichbedeutend damit ist, dass die Initialisierung notwendig ist. Zwar ist ein Thread, der sich innerhalb des Blocks befindet, der einzige, der ihn gerade ausführt, jedoch ist das keine Garantie dafür, dass nicht ein anderer zuvor schon den Block ausgeführt hatte. Wir müssen also als allererstes prüfen, ob die Arbeit nicht bereits verrichtet wurde.

Das Arbeiten mit Threads wird nicht umsonst gefürchtet und passend hierzu ist die Tatsache, dass selbst Double-Checked Locking noch nicht vollkommen ausreicht, um das Problem ein für alle Mal zu lösen [9,10]. Falls die zugrundeliegende Programmiersprache kompiliert ist oder zumindest wie im Fall von Ruby nicht direkt interpretiert wird, sondern aus Programmcode eine Zwischenform von Bytecode generiert wird, hat man ohne entsprechende Garantien des Compilers oder Bytecode-Generators keine Sicherheit, dass Double-Checked Locking tatsächlich funktioniert, da der Generator Code-Sequenzen optimiert und die Reihenfolge nach Gutdünken ändern kann. In Java z. B. hat man dieses Problem ab Version 5 durch ein überarbeitetes Speichermodell gelöst [11,12,13]. Das hat zur Folge, dass z. B. für als volatile deklarierte Variablen vom Bytecode-Generator bestimmte Garantien gegeben werden. Es gibt strikte Regeln zu erlaubten sowie nicht erlaubten Umstrukturierungen bezüglich lesender bzw. schreibender Zugriffe. In Ruby gibt es zu diesem Zeitpunkt leider keine äquivalenten Garantien, jedoch wird auch hier ein entsprechendes Speichermodell diskutiert [14,15,16].

Die gute Nachricht ist, dass wir Double-Checked Locking schon jetzt nutzen können, bevor das Speichermodell umgesetzt wird. Mit Hilfe des Gems concurrent-ruby [17], ist es möglich, Double-Checked Locking verlässlich für Memoisation zu implementieren. concurrent-ruby implementiert dazu die fehlenden Bausteine mittels nativem Code für CRuby, so dass plattformübergreifend (auch in JRuby) Garantien gemacht werden können, die uns die Sprache selbst mangels Speichermodell nicht machen kann. Die finale Implementierung mit concurrent-ruby für unser Problem:

require 'concurrent'

class Shared

  attr_reader :counter

  def initialize
    @counter = 0
    @mutex = Mutex.new
    @cache = Concurrent::Map.new
  end

  def expensive_computation
    @cache[:memoized] || @mutex.synchronize do
      @cache.compute_if_absent(:memoized) do
        @counter +=1
        42
      end
    end
  end

end

Hier endet der erste Teil von Memoisation in Ruby. Im zweiten Teil steigen Sie ein in Fortgeschrittene Memoisierung.

nach Oben
Autor
botMessage_toctoc_comments_929