[Ben]

Wiederverwendung von Berechnungen, effektives Caching


Vorwort

Dieses Tutorial beschreibt, wie man zeitaufwendige Berechnungen in PHP so strukturiert, dass man im Endeffekt einen signifikanten Performancegewinn erhält.
In diesem Tutorial wird kurz auf Grundlagen eingegangen und danach werden wir anhand eines Beispiels kennenlernen, wie man solche Cachingmechanismen effektiv anwenden kann.

Das Tutorial basiert auf einem Kapitel aus George Schlossnagle's Buch Professionelle PHP 5-Programmierung.


Bei Fragen zu diesem Tutorial, solltet Ihr das Nachwort lesen.



Inhaltsverzeichnis

1. Grundlegendes zum Thema Caching (von Berechnungen)
2. Beispiel: Berechnung von Fibonacci-Folgen
3. Wo wendet man diese Technik an?
4. Nachwort

[Ben]

1. Grundlegendes zum Thema Caching (von Berechnungen)

Die Wiederverwendung von bestimmten Daten ist nichts Besonderes. Es gibt sie in vielen Bereichen, nicht nur speziell in PHP. So wird z.B. gerade in der Bildverarbeitung und bei aufwendingen mathematischen Berechnungen auf diese Technik zurückgegriffen.

Prinzipiell heißt "Wiederverwendung/Caching von Berechnungen", dass Daten in Methoden/Funktionen, die nicht als Rückgabewert dienen, zwischengespeichert und für die Berechnung weitere Daten genutzt werden.

Im Gegensatz zu z.B. Cachingverfahren, die ganze Webseiten in Caches ablegen, handelt es sich hier nur um die Zwischenspeicherung von kleinen Codeblöcken bzw. kleinen Datenmengen.
Das Prinzip ist, dass eine komplexe Anwendung nur eine Zusammensetzung vieler kleiner simpler Operationen ist, welche immer wieder aufgerufen und ausgeführt werden.
Speichert man nun die Resultate dieser Operationen zwischen, erspart man dem Compiler Rechenarbeit und erhält somit einen Performancegewinn.

Gerade bei großen Anwendungen, die komplexe Abfragen und Berechnungen durchführen müssen, ist diese Technik oftmals sehr effektiv bzw. sie kann es bei richtiger Anwendung sein.

[Ben]

2. Beispiel: Berechnung von Fibonacci-Folgen

Sehen wir uns einfach mal ein Beispiel an, welches uns am Ende ein Ergebnis liefert. Im Voraus: Ich gebe zu, ich war erstaunt!

Wir werden anhand der rekursiven Berechnung einer Fibonacci-Folge sehen, welch starken Einfluss Caching doch auf die Performance eines Skriptes haben kann. Ich gehe an dieser Stelle nicht näher auf die Definition einer Fibonacci-Folge ein, da der Wikipedia-Artikel in meinen Augen für den Einstieg absolut ausreicht .. und bei Interesse auch etwas weiter in die Tiefe geht.

Machen wir uns klar, wie eine Fibonacci-Folge berechnet wird.
fibo(0) ist definiert als 0.
fibo(1) ist definiert als 1.

Diese Definition ist notwendig, da fibo(2) als die Summe von fibo(1) und fibo(0) angesehen wird bzw. allgemein gilt

fibo(n) = fibo(n - 1) + fibo(n - 2)

Wir sehen also, dass wir das Ergebnis einer Fibonacci-Folge mittels Rekursion leicht berechnen können.

Eine Funktion, die dies macht könnte so aussehen:

PHP-Code:

/**
 * Diese Funktion berechnet das Ergebnis der Fibonacci-Folge zur Zahl n.
 * Die beiden vordefinierten Werte für n = 0, n = 1 werden separat 
 * zurückgegeben, da hier keine rekursive Berechnung nötig/möglich ist.
 */
function fibo_no_cache($n)
{
    if($n <= 0 or !is_int($n))
    {
        return 0;
    }
    elseif($n == 1)
    {
        return 1;
    }

    return fibo_no_cache($n - 1) + fibo_no_cache($n - 2);
} 


Die Funktion sollte selbsterkärend sein.

Was können wir nun an dieser Funktion verbessern? Was können wir wiederverwenden?
Nun, schauen wir uns doch einmal den Fall von n = 4 an.

Was ist fibo(4)?

fibo(4) = fibo(3) + fibo(2)

Und was ist fibo(3)?

fibo(3) = fibo(2) + fibo(1)

Und was ist fibo(2)?
Ich denke, dass das klargeworden ist.

fibo(2) = fibo(1) + fibo(0)

Letztlich gilt also

fibo(4) = [(fibo(1) + fibo(0)] + [fibo(1))] + [fibo(1) + fibo(0)] 
fibo(4) = [(1 + 0) + 1] + (1 + 0) = 3

Wir haben also das "komplexe" System in viele kleine Operationen zerlegt, welche leicht zu berechnen sind.

Wie kann man diese nun in PHP-Code umsetzen?
Schauen wir uns die Funktion fibo_cache() an

PHP-Code:

/**
 * Diese Funktion berechnet das Ergebnis der Fibonacci-Folge zur Zahl n.
 * Dieses Mal werden allerdings Zwischenergebnisse gespeichert, um in den
 * darauffolgenden rekursiven Durchläufen verwendet zu werden.
 * Wir nutzen ein statisches Array, um die Daten dauerhaft nutzen zu können.
 */
function fibo_cache($n)
{
    static $fiboValues = array(0 => 1, 1 => 1);
    
    if($n <= 0 or !is_int($n))
    {
        return 0;
    }
    elseif(!array_key_exists($n, $fiboValues))
    {
        $fiboValues[$n] = fibo_cache($n - 1) + fibo_cache($n - 2);
    }
    
    return $fiboValues[$n];
} 


Die Funktion geht nun also anders an die Berechnung heran, als die oben stehen Funktion ohne Caching.

Es wird überprüft, ob ein, zur Berechnung benötigter, Fibonacci-Wert schon berechnet wurde. Ist dies nicht der Fall, so wird die Berechnung eingeleitet.

PHP-Code:

elseif(!array_key_exists($n, $fiboValues))
{
    $fiboValues[$n] = fibo_cache($n - 1) + fibo_cache($n - 2);
} 


anderfalls wird der zuvor bestimmte (also gecachte) Wert zurückgegeben.
Die bereits berechneten Werte werden in einem statischen Array gespeichert, so dass sie in jedem Rekursionsdurchlauf verfügbar sind.

Das war es.
Wie das war es? Das kann doch nicht alles gewesen sein!?
Doch!

Diese kleine Änderung hat einen signifikanten Unterschied zur Folge.
Ich verwende dieses Skript, um die Performance der beiden Aufrufe zu vergleichen.

PHP-Code:

$step = start_timer("fibo_no_cache(8)");
echo fibo_no_cache(8) . '<br />';

$step = next_timer($step, "fibo_cache(8)");
echo fibo_cache(8) . '<br /><br />';

$step = next_timer($step, "finish"); 


Schon bei sehr kleinen Zahlen n man den Unterschied.

mit Cache: 0.0005 Sekunden
ohne Cache: 0.0077 Sekunden

Diese Zahlen sind natürlich nicht komplett richtig, weil nebenher auf meinem Testsystem noch einige weitere Prozesse laufen, aber ich denke, dass die Tendenz doch sehr gut zu erkennen ist.

Messen wir noch etwas, nämlich die Berechnung von fibo(30)

mit Cache: 0.0016 Sekunden
ohne Cache: 23.9333 Sekunden

Noch Fragen?

Ich denke, dass dieses Beispiel sehr gut andeutet, was es bedeuten kann, auch kleine Datenmengen vor allem in rekursiven Abläufen wiederverwendbar zwischenzuspeichern.

[Ben]

3. Wo wendet man diese Technik an?

Sehr gute Frage.
Wir haben innerhalb des Tutorialteams einige Möglichkeiten diskutiert und versucht ein praktisches Beispiel ins Tutorial einzubinden, allerdings haben wir keinen Anwendungsbereich gefunden, der diese Technik sinnvoll nutzen könnte.

Das liegt z.B. daran, dass viele rekursive Programmabläufe keinerlei cachebare Daten erstellen, die im nächsten Rekursionsablauf verwendet werden könnten.
Oftmals werden die benötigten Daten einfach per Parameter an die Funktion/Methode übergeben.

Da wir das Thema als Solches - auch wenn es derzeit nur theoretischen Nutzen zu haben scheint - aber doch interessant finden, haben wir uns dazu entschlossen dieses Tutorial zu veröffentlichen und an dieser Stelle um Eure Mithilfe zu bitten.
Wenn Ihr Ideen habt, wie man die oben beschriebene Cachingtechnik sinnvoll in der Praxis anwenden könnte, so wäre es sehr nett und hilfreich, wenn Ihr mir eine PN schicken würdet.

Gerade die signifikanten Performanceunterschiede lassen uns nicht in Ruhe. Diese Technik ist zu genial, um sie einfach so in den Tiefen der Theorie verfallen zu lassen.

Wir danken Euch als im Voraus für Eure Mithilfe.

[Ben]

4. Nachwort

Nachdem Ihr nun dieses, bislang leider nur theoretisch nutzbare, Tutorial durchgearbeitet habt hoffe ich, dass Ihr dennoch die Prinzipien dieses Cachingverfahrens verstanden habt.

Ich habe versucht so wenig Vorkenntnisse wie möglich vorauszusetzen und die benötigten Schritte bei der Implementierung bestmöglich zu erläutern.

Sollte es dennoch zu Fragen kommen, so könnt Ihr diese selbstverständlich in unserem PHP-Forum stellen, sofern Ihr ein registriertes Mitglied unseres Hilfeforums seid. Ist dies nicht der Fall, so könnt Ihr Euch hier, natürlich völlig kostenfrei, registrieren.

Solltet Ihr über die Suche keine Lösung für eventuell auftretende Probleme finden und einen Thread erstellen, so bitten wir Euch folgende Passage per Copy & Paste zu kopieren und im erstellten Thema in quote-Tags einzufügen.

Diese Frage bezieht sich auf das Tutorial Wiederverwendung von Berechnungen, effektives Caching

Solltet Ihr Verbesserungsvorschläge haben oder einen Fehler finden, so freue ich mich selbstverständlich über eine private Nachricht.

Bitte beachtet, dass es keine Problemhilfe per ICQ, PN, Mail etc. gibt. Genau für diese Fragen gibt es unser Hilfeforum.

Ich danke Euch für Euer Interesse an diesem Tutorial und würde mich freuen, wenn Ihr es weiterempfehlen würdet.
Bitte lest dazu: Weiterverwendung der Tutorials

In diesem Sinne, viel Spaß beim Programmieren.
Grüße Ben.