PHP in_array() die Performance-Bremse

Dies ist ein Gastartikel von Dominik Siebel.

Dominik ist 25 Jahre alt und arbeitet als Webentwickler und Consultant bei TWT Business Solutions GmbH in Düsseldorf. Sein Hauptaufgabenbereich ist die Entwicklung von Inter- und Intranetapplikation im Zusammenspiel mit Google Enterprise Produkten (GSA) auf Basis gängiger Technologien: MySQL, PHP, Java, jQuery, etc.

Einleitung

Ich bin kürzlich erst wieder über dieses Problem gestolpert und dachte mir ich bringe es für die Nachwelt zu Papier
PHPs in_array() Funktion ist ziemlich praktisch um auf die Schnelle zu überprüfen ob ein Eintrag bereits in einem Array enthalten ist und so z.B. doppelte Einträge zu vermeiden. So handlich diese Funktion auch ist, so offenbart sie jedoch erhebliche Schwächen, wenn wir erstmal ein paar mehr als die üblichen 500 – 1000 Datensätzen verarbeiten wollen.

Ausgangssituation

Im Zuge einer etwas komplexeren Search-as-you-type Implementierung werden in einem Ajax-Request über zwei verschiedene Mechanismen Vorschläge in einem Array vorgehalten, bevor sie per JSON an den Client zurück geliefert werden, wobei der zweite Mechanismus vor jedem Hinzufügen eines Vorschlags prüft ob dieser eventuell bereits vorhanden ist.

Der Vorzug einer solchen Search-as-you-type Geschichte ist, dass man Begriffe und Suchergebnisse vorgeschlagen bekommt, noch bevor man den kompletten Suchbegriff eingetippt hat. Was wir also brauchen ist Geschwindigkeit. Über die Laufzeit des Projektes wurden es aber irgendwann so viele Daten, dass die Suche immer langsamer wurde. Bis zur völligen Nutzlosigkeit. Wo lag das Problem?

Folgendes Beispiel zeigt in vereinfachter Form die bestehende Implementierung:

Beispiel

<?php
$result = range(1, 50000);
$iStartTime = time();
echo 'START - count: ' . count($result) . PHP_EOL;
for ($i = 0; $i < 50000; $i++) {
    $random = mt_rand(1,100000);
    if (!in_array($random, $result)) {
        $result[] = $random;
    }
}
echo 'END - count: ' . count($result) . ' duration: ' . (time() - $iStartTime) . PHP_EOL;

Auf eine bereits bestehende Menge Daten von (in diesem Beispiel) 50000 Einträgen werden über einen zweiten Mechanismus (hier durch die Generierung von weiteren 50000 Zufallswerten dargestellt) weitere Datensätze hinzugefügt ohne dabei Duplikate zu erzeugen. Dabei stellte sich nach einiger Zeit der Fehlersuche heraus, dass genau dieser Codeschnipsel bis zu 1 Minute oder länger lief. Nicht gerade die gewünschte Antwortzeit für ein schnelles “look-up”:

Ergebnis

dsiebel@note:~/public_html/test$ php in_array.php
START - count: 50000
END - count: 69625 duration: 109

Also ich weiß nicht, wie es euch geht, aber wenn ich knapp 110 Sekunden auf meine Suchvorschläge müsste… So ist dieses Stück Programm also nicht mehr wirklich nutzbar.

Lösungsansätze

Wie sollte ich dieses Problem beheben? Ich habe verschiedene Ansätze ausprobiert und konnte mich letztendlich auf die folgende Implementierung einigen:

Beispiel

<?php
$result = array();
for ($i = 0; $i < 50000; $i++) {
    $result[md5($i)] = $i;
}
$iStartTime = time();
echo 'START - count: ' . count($result) . PHP_EOL;
for ($i = 0; $i < 50000; $i++) {
    $random = mt_rand(1, 100000);
    $index = md5($random);
    if (!isset($result[$index])) {
        $result[$index] = $random;
    }
}
echo 'END - count: ' . count($result) . ' duration: ' . (time() - $iStartTime) . PHP_EOL;

Auch hier wird wieder mit einem Grundstock von 5000 Datensätzen begonnen. Unterschied ist die Art und Weise, wie die Daten im Array abgelegt werden: Im ersten Skript wurde ein “normales” Array mit numerischen Indizes verwendet. In der neuen Implementierung wird als Index die MD5-Summe des Wertes verwendet. Warum die MD5-Summe? Da es sich im realen Skript teilweise um ganze Sätze oder Beschreibungen handelt war MD5 die nächste Wahl die Strings in gleich große und einzigartige Schlüssel umzuwandeln. Außerdem besteht ein Vorschlag nicht nur aus dem eigentlichen Vorschlag sondern auch zusätzlichen Metadaten für eine Sortierung beispielsweise, die in einem späteren Schritt erfolgen könnte.

Zurück zu dem neuen Script:

Ergebnis

dsiebel@note:~/public_html/test$ php isset.php
START - count: 50000
END - count: 69719 duration: 0

Dieses Ergebnis kann sich doch schon eher sehen lassen (< 1s).
Da wir die Werte in Form der MD5-Summen als Indizes verwenden können wir das Array schnell und einfach mittels isset() überprüfen – welches um ein vielfaches performanter arbeitet als in_array() – bevor wir den neuen Vorschlag hinzufuegen und somit Duplikate vermeiden.

Ich hoffe mein kleiner Gastbeitrag hilft vielleicht dem ein oder anderen von Euch dieses Problem frühzeitig zu erkennen und zu verhindern.