Martin Boßlet 23. Mai 2017

Memoisation in Ruby [Teil 2]: Fortgeschrittene Memoisierung

Metaprogramming mit Memoisation ermöglicht oft erstaunliche und elegante Lösungen. © Gnel Karapetyan / Fotolia.com — © Gnel Karapetyan / Fotolia.com

Bis hierhin [Teil 1] haben wir die "klassische Form" der Memoisation in Ruby kennengelernt. Zwar gewöhnt man sich schnell an die entsprechenden Idiome, doch den Puristen stört es, dass man in vielen Fällen bei der Memoisation Instanzvariablen "verschwendet", deren Existenz rein technisch begründet ist.

Vermeiden von Instanzvariablen

Wie auch in den Beispielen hier praktiziert, behilft man sich oft mit syntaktischen Gedächtnisstützen. Etwa damit, dass man solche Memoisationsvariablen mit einem Unterstrich versieht, um klar zu machen, dass es sich hier um eine interne Variable handelt, die mit der eigentlichen Businesslogik nichts zu tun hat. Dank der mächtigen Hilfsmittel, die uns Rubys Metaprogramming an die Hand gibt, können wir diesen Makel umgehen. Sehen Sie sich dieses Beispiel an:

def expensive_computation
  puts "Computing..."
  sleep 1
  42
end

def memoized_method
  expensive_computation.tap do |value|
    define_method :memoized_method do
      value
    end
  end
end

10.times { puts memoized_method }

Wenn Sie das Beispiel ausführen, sehen Sie, dass Computing... nur einmal erscheint, und nach anfänglichem Warten von einer Sekunde werden die folgenden Ergebnisse umgehend geliefert. Wir haben expensive_computation also effektiv memoisiert – und das ganz ohne zusätzliche Instanzvariable!

Wie geht das? Wir nutzen einen Trick: wir führen erst die aufwändige Berechnung ganz normal durch, so wie wir es ohne Memoisation auch getan hätten. Sobald wir den Wert value aber einmalig berechnet haben, schreiben wir dynamisch die ursprüngliche Methode einfach neu und geben in der neuen Variante direkt den Wert value als Rückgabewert zurück. Das Ganze funktioniert, weil wir explizit define_method mit einem Block benutzen. Dieser Block bildet eine Closure [1] und daher ist die Variable value weiterhin auch innerhalb des Blocks verfügbar, obwohl sie außerhalb definiert wurde.

Deklarative Memoisation mittels Annotation

Wer Memoisation bereits in anderen Sprachen genutzt hat, schaut manchmal neidisch auf diejenigen, bei denen Memoisation noch eleganter gelöst ist als das mit Ruby-Bordmitteln der Fall ist. In Groovy z. B. ist Memoisation fester Bestandteil der Sprache. Alles was man tun muss, ist eine entsprechende Methode mit einer Annotation zu versehen, etwa:

@Memoized
def expensiveComputation() {
  //perform expensive computation
}

Oder Python, wo man mit Hilfe eines Decorators ähnlich elegant memoisiert:

def memoized(f):
    memo = {}
    def helper(n):
        if n not in memo:
            memo[n] = f(x)
        return memo[n]
    return helper

@memoized
def expensive_computation(n):
    # do something expensive

Und auch hier bietet uns Metaprogramming wieder die nötigen Werkzeuge, um auch in Ruby ähnlich elegante Lösungen für Memoisation zu realisieren. Seit Ruby 2.1.0 [2] haben Methodendeklarationen einen Rückgabewert, nämlich ein Symbol des Methodennamens:

result = def my_method
  ...
end

puts result.inspect # => :my_method

Dieses Feature werden wir in der Folge nutzen, um ein Modul zur Memoisation zu entwickeln, welches sich in Sachen Komfort nicht vor den Konstrukten in Groovy oder Python zu verstecken braucht. Zuvor führen wir noch ein Hilfsmittel ein, das wir nutzen werden, um berechnete Funktionswerte zu memoisieren:

class Memory

  def initialize
    @values = {}
  end

  def fetch(args)
    unless @values.has_key?(args)
      @values[args] = yield
    end

    @values[args]
  end

end

Dabei stellt Memory einen einfachen Speicher dar, der im Wesentlichen aus einem Hash besteht. Die Gründe, nicht direkt einen Hash zu verwenden, sind zum Einen, den Dingen zwecks Verständlichkeit einen Namen zu geben. Zum Anderen gibt uns die fetch-Methode eine komfortable Lösung, den Speicher einmalig mit einem Wert zu versehen, falls dieser noch nicht gesetzt wurde. Dies geschieht analog zu Concurrency::Map#compute_if_absent im Beispiel aus Teil I:

m = Memory.new

10.times do
  puts (m.fetch(:key) do
    puts "Executing"
    42
  end)
end

Der Block wird einmalig ausgeführt. Danach wird sofort der Wert des Blocks zurückgegeben, ohne dass der Block dazu erneut ausgeführt wird.

Unser Memoisationsmodul wird es erlauben, gezielt Methoden von Objekten zu
memoisieren. Mit Hilfe von Memory erweist sich die Implementierung von unserem Modul Memoizable sehr übersichtlich und kurz:

require_relative 'memoizable/memory'

module Memoizable

  def memoized(name)
    memory = Memory.new

    prepend (Module.new do
      define_method(name) do |*args, &blk|
        return super(*args, &blk) if blk # do not memoize method calls with blocks

        memory.fetch(args) do
          super(*args)
        end
      end
    end)
  end

end

Das Schöne an Memoizable ist, dass im Grunde Methoden mit beliebigen Argumenten memoisiert werden können. Dazu gleich mehr. Vorweg sei jedoch erwähnt, dass Methoden mit Block-Argument generell bei der Memoisation nicht berücksichtig werden. Es ist nicht ohne Weiteres möglich, Gleichheit von Blöcken zu definieren, was sie als Hash-Keys unbrauchbar macht. Daher delegieren wir bei Blöcken kategorisch an die ursprüngliche Methode, ohne diese Ergebnisse dabei zu memoisieren.

Um ein Gefühl dafür zu bekommen, wie man Memoizable nutzt, sehen wir uns am besten ein Beispiel an. Wir nutzen hier das klassische Beispiel der Fibonacci-Zahlen und demonstrieren, wie wir mittels Memoisation die rekursive Definition mit exponentieller Laufzeit auf lineare Laufzeit reduzieren können:

require_relative 'memoizable'

class Fibonacci
  extend Memoizable

  attr_reader :counter

  def initialize
    @counter = 0
  end

  memoized def call(n)
    @counter += 1
    return n if n < 2
    call(n - 1) + call(n - 2)
  end

end

fib = Fibonacci.new
puts fib.call(30) # => 832040
puts fib.counter # => 31 instead of 2692537

Wie wir am Beispiel memoized def call(n) sehen können, erlaubt uns das Modul eine deklarative Syntax für Memoisierung, die sehr nahe an den Beispielen von Groovy und Python ist. Dadurch, dass die Methodendeklaration ein Symbol als Rückgabewert hat, wird dieses Symbol der Klassenmethode memoized übergeben. Diese ist nun ihrerseits in der Klasse Fibonacci vorhanden, da wir das Modul Memoizable via Object#extend [3] eingebunden haben: Object#extend übernimmt die im Modul definierten Methoden als Klassenmethoden der Klasse, die mittels extend das Modul einbindet.

Die Implementierung von memoized selbst bedient sich nun des Tricks von oben, indem memory = Memory.new im Scope der Closure deklariert wird. Die Closure wird definiert durch den Block Module.new do, wo ein anonymes Modul erzeugt wird, das letzen Endes an prepend übergeben wird. Der Block, der das Modul erzeugt – Module.new do – definiert erneut eine weitere Closure im define_method-Block. Dieser deklariert im neu erzeugten Modul dynamisch eine Methode, die den gleichen Namen trägt wie die Methode, die wir mit memoized ursprünglich annotiert haben – in unserem Falle ist es die Methode Fibonacci#call. Das anonym erzeugte Modul ist also äquivalent zu diesem:

module Anonymous

  def call(n)
    memory.fetch(n) do
      super(n)
    end
  end

end

Der Trick an der Sache ist, dass durch die ausschließliche Verwendung von Blöcken (zum Einen mit Module.new do und zum Anderen mit define_method(name) do |*args,&blk|), memory nach wie vor im Kontext der Methode vorhanden ist, weil es sich im Scope der Closures befindet.

Das so erzeugte anonyme Modul wird nun via Module#prepend[4] in die aufrufende Klasse – hier Fibonacci – eingebunden. Module#prepend wurde in Ruby 2.0.0 eingeführt und funktioniert ähnlich wie Module#include[5], jedoch mit dem entscheidenden Unterschied, dass prepend das Modul in der Klassenhierarchie vor die inkludierende Klasse setzt, während bei include das Modul hinter die Klasse gesetzt wird. Ein Beispiel:

module Mod; end

module A; include Mod; end

module B; prepend Mod; end

puts A.ancestors # => [A, Mod]

puts B.ancestors # => [Mod, B]

Das Faszinierende an prepend ist nun, dass wir innerhalb des per prepend eingebundenen Moduls Methoden deklarieren können, die den gleichen Namen tragen wie Methoden der Klasse, die das Modul ihrerseits einbindet. Dabei überschreiben wir diese Methoden aber nicht gänzlich, sondern haben weiterhin Zugriff auf die Originalimplementierung, indem wir einfach vom Modul aus an super delegieren. Bei prepend verhält es sich so, als ob das Modul von der Klasse erbt und somit die Methode überschreibt, aber noch mittels super an die ursprüngliche Implementation delegieren kann. Dagegen ist es bei include eher umgekehrt: Es sieht so aus, als ob die Klasse vom Modul erbt. Ein Aufruf von super im Modul ergibt somit keinen Sinn mehr, da das Modul in der Klassenhierarchie weiter oben steht und ein Aufruf von super somit ins Leere läuft. Genau diese Eigenschaften von prepend nutzen wir auch bei der Implementierung von Memoizable, wo wir via super an die ursprüngliche Implementierung der Methode in der Klasse delegieren, falls wir das Ergebnis noch nicht in unserem Memory vorliegen haben.

Memoisation von Methoden mit Argumenten

Wie Sie sicher bemerkt haben, nutzen wir in Memoizable die Methodenargumente args direkt als Hash-Key, ohne die Argumente vorher in irgendeiner Weise bearbeiten zu müssen. Dadurch, dass wir mittels define_method(name) do |*args, &blk| forcieren, dass wir beliebig viele Argumente erlauben und diese in einem Array zusammenfassen, liegt args immer als Array vor. Falls eine Methode keine Argumente hat, ist args == [nil], bei einer Methode mit einem Argument gilt args == [arg]. Wir können diese Arrays unmittelbar als Hash-Keys verwenden, da Ruby beim Hashen von Arrays nur die Inhalte berücksichtigt, d. h. zwei unterschiedliche Arrays mit gleichem Inhalt erzeugen den gleichen Hash-Wert:

a = 1
b = "abc"
c = Object.new

array1 = [a, b, c]
array2 = [a, b, c]

puts array1.object_id == array2.object_id # => false
puts array1.equal?(array2) # => false
puts array1.eql?(array2) # => true
puts array1.hash == array2.hash # => true

Wir sehen, dass array1 und array2, obwohl unterschiedliche Objekte, dennoch dank gleichen Inhalts den gleichen #hash-Wert liefern und auch der Test mittels eql? sie als gleich ausweist. Dies sind die entscheidenden Kriterien dafür, ob ein Hash-Key als gleich betrachtet wird [7]. Da args bei Memoizable als Array vorliegt, ist also gewährleistet, dass in der Regel gleiche Argumente als der gleiche Hash-Key interpretiert werden und Memoisation so auch für Methoden mit mehreren Argumenten verlässliche Ergebnisse liefert. Vorsicht ist allerdings geboten, falls Sie beliebige Objekte als Methodenargumente memoisieren möchten:

class Person
  def initialize(name)
    @name = name
  end
end

p1 = Person.new("Martin")
p2 = Person.new("Martin")

puts p1.eql?(p2) # => false
puts p1.hash == p2.hash # => false

h = { p1 => "Found me" }
puts h[p1] # => Found me
puts h[p2] # => nil

In solchen Fällen lässt sich das Problem lösen, indem Sie für die entsprechenden Klassen die Methoden eql? und hash implementieren. Meist genügt es, an entsprechende Instanzvariablen zu delegieren, in unserem Beispiel etwa:

class Person
  attr_reader :name

  def initialize(name)
    @name = name
  end

  def eql?(other)
    self.class === other &&
      name == other.name
  end

  def hash
    name.hash
  end
end

p1 = Person.new("Martin")
p2 = Person.new("Martin")

puts p1.eql?(p2) # => true
puts p1.hash == p2.hash # => true

h = { p1 => "Found me" }
puts h[p1] # => Found me
puts h[p2] # => Found me

"Unobtrusive Memoization"

Mit den Werkzeugen, die wir bis hierhin gesehen haben, lässt sich in der Praxis schon eine Menge erreichen, um Memoisation verlässlich zu implementieren. Sie können das oben entwickelte Modul Memoizable via extend in Klassen einbinden, in denen Sie Memoisation benötigen. Einen kleinen ästhetischen Makel hat dieses Vorgehen aber: Sie müssen die ursprüngliche Klasse verändern, um Memoisation zu realisieren. Das mag kleinlich erscheinen, aber es gibt einen praktischen Anwendungsfall, wo dies unter Umständen problematisch wird. Nicht immer hat man die volle Kontrolle über die Gesamtheit der Code-Basis – beispielsweise wenn Sie auf Third-Party-Gems oder Code eines anderen Teams angewiesen sind.

Stellen Sie sich vor, Sie haben eine Stelle in Ihrem Code identifiziert, die sich als wahrer Flaschenhals erweist, und Sie stellen fest, dass Sie dieses Problem mittels Memoisation aus der Welt schaffen könnten. Das Problem an der Sache: Die schuldige Code-Stelle wurde gar nicht von Ihnen geschrieben, sondern Sie binden sie als Gem von außen ein. Hier bietet Ruby zwar schnelle Abhilfe mittels Monkey Patching, also dem erneuten Öffnen einer Klasse und Änderung der betreffenden Code-Stellen. Doch sollte dies nur als letzte Instanz dienen, wenn Sie wirklich keine andere Lösung finden. Monkey Patching kann ungeahnte Seiteneffekte mit sich bringen. Oder das Kartenhaus bricht schlicht zusammen, wenn sich in einer zukünftigen Version des Third-Party-Codes die Interna so sehr ändern, dass Ihr Monkey Patch nicht mehr greift und/oder ganz einfach zu einem Fehler führt, weil es die betreffenden Aufrufe nicht mehr gibt oder nur in abgeänderter Form.

Der Königsweg wäre in diesem Fall, Memoisation zu realisieren, ohne das zu memoisierende Objekt anfassen zu müssen – "Unobtrusive Memoization". Und auch hier lässt uns Metaprogramming nicht im Stich. Wir entwickeln nun ein generisches Proxy-Objekt [8], das sich genau so verhält wie das zu memoisierende Objekt und dabei gezielt Methoden des Ursprungsobjekts memoisiert, ohne jedoch dieses in irgendeiner Form zu verändern:

require_relative 'memoizable'

class UnobtrusiveMemoizedProxy

  def initialize(object, memoize: object.public_methods)
    @delegate = create_memoized_delegate(
      object,
      Array(memoize)
    )
  end

  def respond_to_missing?(name, include_private=false)
    @delegate.respond_to?(name, include_private)
  end

  def method_missing(name, *args, &block)
    @delegate.send(name, *args, &block)
  end

  private

  def create_memoized_delegate(object, memoized_methods)
    object.dup.tap do |clone|
      clone.singleton_class.instance_eval do
        extend Memoizable
        memoized_methods.each do |method|
          memoized(method)
        end
      end
    end
  end

end

Wir delegieren mittels respond_to_missing? und method_missing alle Methodenaufrufe an @delegate weiter. @delegate ist dabei ein Klon des ursprünglichen Objekts, der mittels dup erzeugt wird. Wir brauchen dies als Kopie von object, damit wir in der Kopie die memoisierten Methoden neu definieren können. Der Sinn und Zweck dieser Kopie ist es, die Memoisierung selbst für rekursive Methoden zu ermöglichen. Wir integrieren unser Modul Memoizable, um dann via memoized die gewünschten Methoden innerhalb von @delegate zu memoisieren. Außerdem nutzen wir clone.singleton_class, um gezielt für die einzelne Instanz @delegate Methoden zu definieren, ohne jedoch in der eigentlichen Klasse von @delegate und object "herumzupfuschen". Der Klon ermöglicht es uns nun, dass rekursive Aufrufe immer innerhalb von @delegate stattfinden. Würden wir dagegen für die Berechnung der Funktionswerte direkt an object delegieren, so würde der rekursive Aufruf einer Methode dazu führen, dass im weiteren Verlauf die rekursiven Aufrufe auch innerhalb vom Kontext von object stattfinden und sie sich so an der Memoisation "vorbeimogeln". Sehen wir uns ein Beispiel an, das UnobtrusiveMemoizedProxy nutzt.

require_relative 'unobtrusive_memoized_proxy'

class Fibonacci

  attr_reader :count

  def initialize
    @count = 0
  end

  def call(n)
    @count += 1

    return n if n < 2
    call(n - 1) + call(n - 2)
  end

end

original = Fibonacci.new
fib = UnobtrusiveMemoizedProxy.new(original)

puts fib.call(30) # => 832040
puts fib.count # => 31
puts original.count # => 0

puts original.call(30) # => 832040
puts original.count # => 2692537

Die Memoisierung greift trotz der rekursiven Definition von call – und das ganz ohne einen Eingriff in das ursprüngliche Objekt original.

MemoizationProxy inklusive Seiteneffekte

So bemerkenswert dieses Ergebnis auch ist: Es gibt einen Schönheitsfehler. Wie Sie sehen ist fib.count zwar gleich 31 nach der Ausführung, jedoch ist original.count immer noch 0. Der Grund ist schnell klar: Die Methode wird im Kontext von @delegate ausgeführt, und @delegate führt Buch über seine eigene Version von @count. Wenn Sie nun aber möchten, dass trotz der Memoisierung auch gleichzeitig noch eventuelle Seiteneffekte der Ausführung im ursprünglichen Objekt zum Tragen kommen, etwa dass in unserem Beispiel @count von object korrekt hochgezählt wird, so müssen Sie hier leider Abstriche machen. Entweder greift die Memoisation nicht mehr für rekursive Aufrufe, weil man bei der Berechnung an das ursprüngliche Objekt delegiert, oder aber man muss das ursprüngliche Objekt verändern, damit die Memoisation ab sofort im ursprünglichen Objekt greift. Generell kann es aber durchaus wünschenswert sein, dass der Zustand des Originalobjekts verändert wird, wenn der memoisierte Code ausgeführt wird. Werden z. B. bei der Ausführung Instanzvariablen gesetzt, so wäre es ziemlich verwirrend, wenn diese im Original nicht korrekt gesetzt sind, obwohl der betreffende Code ausgeführt wurde.

Es gibt aber einen guten Kompromiss, der zwar nicht ganz ohne Veränderung des zu memoisierenden Objekts auskommt, aber zumindest nicht dessen eigentliche Klasse verändert, sondern nur die einzelne Instanz. Dies eignet sich hervorragend, um auch Third-Party-Code zu memoisieren, da man nicht krude die ganze Klasse des fremden Codes überschreiben muss, sondern nur einzelne Instanzen zur Laufzeit eines Programms – der Code bleibt ansonsten unangetastet. Die Implementierung unterscheidet sich nur unwesentlich von UnobtrusiveMemoizedProxy. Statt einen Klon zu schaffen, definieren wir die memoisierten Methoden direkt in dem zu memoisierenden Objekt selbst.

require_relative 'memoizable'

class MemoizedProxy

  def initialize(object, memoize: object.public_methods)
    @object = memoize_methods(object, Array(memoize))
  end

  def respond_to_missing?(name, include_private=false)
    @object.respond_to?(name, include_private)
  end

  def method_missing(name, *args, &block)
    @object.send(name, *args, &block)
  end

  private

  def memoize_methods(object, memoized_methods)
    object.tap do
      object.singleton_class.instance_eval do
        extend Memoizable
        memoized_methods.each do |method|
          memoized(method)
        end
      end
    end
  end

end

Dies hat nun schließlich den gewünschten Effekt im vorigen Beispiel:

require_relative 'memoized_proxy'

class Fibonacci
# ...
end

original = Fibonacci.new
fib = MemoizedProxy.new(original)

puts fib.call(30) # => 832040
puts fib.count # => 31
puts original.count # => 31

original = Fibonacci.new
puts original.call(30) # => 832040
puts original.count # => 2692537

Nun ist in der Tat auch original.count gleich 31 nach der Ausführung des memoisierten Proxies. Wir sehen aber, dass die Klasse Fibonacci selbst unberührt bleibt, da ein erneutes Ausführen einer frischen Instanz zeigt, dass hier die Memoisation nicht mehr greift, was unschwer am Wert von original.count zu erkennen ist.

Fazit

Memoisation ist ein wirkungsvolles Hilfsmittel, um aufwändige Berechnungen zwischenzuspeichern, so dass sie nur ein einziges Mal ausgeführt werden müssen. Sie dient dabei als eine Art "Micro-Caching", um gezielt performancekritische Stellen im Code zu optimieren. Das Thema hat nicht nur einen wichtigen theoretischen Stellenwert, sondern ist auch in der Praxis ein äußerst wertvolles Hilfsmittel, um z. B. redundante Datenbankzugriffe in einer Rails-Anwendung zu vermeiden. Selbst wenn Sie keinen direkten Einfluss auf Third-Party-Code haben, können Sie mit einem Proxy, wie er hier dargestellt wurde, dennoch Einfluss auf die Ausführung nehmen, ohne am ursprünglichen Code etwas verändern zu müssen. Neben der praktischen Tauglichkeit fasziniert das Thema Memoisation gerade in der Umsetzung mit Ruby, da hier die mächtigen Möglichkeiten von Metaprogramming oft erstaunliche und elegante Lösungen ermöglichen.

Quellen