schneller Algorithmus - Daten auslesen

[Andreas Korthaus]

Hallo!

Habe gerade mal ein wenig mit einer Tabelle rumgespielt, die Zuordnungen von IPs zu Ländern enthält(bitte nicht über den Sinn dessen diskutieren ;-)), und zwar diese hier: http://ip-to-country.com/database/.
Wurde auf php.net erwähnt und ich fand es mal ganz interessant.

Habe mir die Tabelle runtergeladen, enthält 16.000 Datensätze, und zwar der Form:

"IP_FROM","IP_TO","COUNTRY_CODE","COUNTRY_NAME"
    "406372352","406380543","US","UNITED STATES"
    "406388736","406437887","CA","CANADA"

Die Felder:
IP_FROM        NUMERICAL (DOUBLE)    Beginning of IP address range.
IP_TO          NUMERICAL (DOUBLE)    Ending of IP address range.
COUNTRY_CODE   CHAR(2)               Two-character country code based on ISO 3166.
COUNTRY_NAME   VARCHAR(50)           Country name based on ISO 31

Ich dachte mir, 16.000 Zeilen müsste man doch eigentlich auch recht performant aus einer Flat-File auslesen können, also habe ich das (mit PHP, ich habe alle " aus den Daten entfernt) so versucht:

while (!feof($fp)) {
    $buffer = fgets($fp , 72);
    $ips = explode(',', $buffer, 2);
    if($ips[0]<= $dec_ip && $dec_ip <= $ips[1]) {
        $result = explode(',', $buffer, 4);
        break;
    }
}

Aber das war nicht wirklich schnell, hat im Schnitt gut 0,2 Sekunden gedauert. Und wie ich das bedeutend schneller bekommen soll weiß ich auch nicht. Ich habe auch versucht mit einem if, also nur prüfen ob 2. Nummer kleiner als meine Nummer, aber das war kaum schneller. Vielleicht liegt es auch am explode, aber so viel macht das wohl nicht.

Nur mal probehalber habe ich das mal mit mysql probiert, genau die Datentypen wie angegeben, einfach mit folgendem Kommando:

"SELECT COUNTRY_CODE, COUNTRY_NAME FROM ip WHERE IP_FROM <= '$dec_ip' && IP_TO >= '$dec_ip'"

Und alles in allem(mit Verbindung herstellen und einlesen in PHP) hat das ganze nur noch  0,04 Sekunden gedauert, es war fast 6 mal so schnell.
Dann habe ich mal den Typen von MyISAM auf HEAP verändert, da hat sich auch kaum was getan, lag vermutlich daran dass die Daten so kurz danach noch in irgendeinem Cache lagen.
Dann habe ich es mit einem Index versuchen wollen, aber egal was ich da probiert habe hat das ganze eher verlangsamt als es zu beschleunigen. Lässt sich hier einfach kein sinnvoller Index verwenden?
Aber was mich extremst wundert, wieso ist das auslesen von diesen paar Datensätzen um so viel langsamer ist als mit MySQL ohne jeglichen Index. Ich meine, wie bitte geht das dann mit dem Archiv hier performant?

Das beste was mir eingefallen war

$fp = fopen("ips.csv","r");
while (!feof($fp)) {
    $buffer = fgets($fp , 21);
    $com = strpos($buffer, ',');
    if((INT) substr($buffer,$com+1,10) >= $dec_ip){
    break;
    }
}

Das hat ja nun wirklich nichts gemacht, aber es liegt immer noch über 0,2 Sekunden. Wieso?

Gibts irgendwelche "Tricks" sowas schneller zu machen?

Viele Grüße
Andreas

PS: wer "mitspielen" will ;-)

<?php
function start_timer($event) {
    printf("timer: %s<br>\n", $event);
    list($low, $high) = explode(" ", microtime());
    $t = $high + $low;
    flush();
    return $t;
}

function next_timer($start, $event) {
    list($low, $high) = explode(" ", microtime());
    $t    = $high + $low;
    $used = $t - $start;
    printf("timer: %s (%8.4f)<br>\n", $event, $used);
    flush();
    return $t;
}

$ip = $_GET['ip']; // 213.139.94.131
$num = explode(".", $ip);
$dec_ip = $num[0]*pow(256,3) + $num[1]*pow(256,2) + $num[2]*pow(256,1) + $num[3];

$t = start_timer("Start");

/* Version 1
$fp = fopen("ips.csv","r");
while (!feof($fp)) {
    $buffer = fgets($fp , 21);
    $com = strpos($buffer, ',');
    if((INT) substr($buffer,$com+1,10) >= $dec_ip){
    break;
    }
}
fclose ($fp);
*/

/* Version 2
$fp = fopen("ips.csv","r");
while (!feof($fp)) {
    $buffer = fgets($fp , 72);
    $ips = explode(',', $buffer, 2);
    if($ips[0]<= $dec_ip && $dec_ip <= $ips[1]) {
        $result = explode(',', $buffer, 4);
        break;
    }
}
fclose ($fp);
*/

/* Version 3
mysql_connect("localhost", "user", "pass");
mysql_select_db("db");
$sql = "SELECT COUNTRY_CODE, COUNTRY_NAME FROM ip WHERE IP_FROM <= '$dec_ip' && IP_TO >= '$dec_ip'";
$res = mysql_query($sql);
$row = mysql_fetch_assoc($res);
echo $row['COUNTRY_NAME'];
*/
/*

Tabellenstruktur für Tabelle ip

CREATE TABLE ip (
  IP_FROM double(10,0) NOT NULL default '0',
  IP_TO double(10,0) NOT NULL default '0',
  COUNTRY_CODE char(2) NOT NULL default '',
  COUNTRY_NAME char(50) NOT NULL default ''
) TYPE=MyISAM;
*/

$t = next_timer($t, "Ende");
?>
<html>
<head>
  <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
</head>
<body>
<h2>locate IP</h2>
<form method="get" action="<?php echo $_SERVER['PHP_SELF']?>">
  <p>IP:
  <input type="text" name="ip" value="<?php echo $_GET['ip']?>">
  <?php echo ($result[3]) ? $result[2].' ('.trim($result[3]).')' : 'NO DATA'; ?>
</p>
  <p>
    <input type="submit" value="abschicken">
  </p>
</form>
</body>
</html>

PPS: bedenkt das ich bei der CSV-Version alle " entfernt habe.

[Cheatah]

Hi,

"SELECT COUNTRY_CODE, COUNTRY_NAME FROM ip WHERE IP_FROM <= '$dec_ip' && IP_TO >= '$dec_ip'"

Dann habe ich es mit einem Index versuchen wollen, aber egal was ich da probiert habe hat das ganze eher verlangsamt als es zu beschleunigen. Lässt sich hier einfach kein sinnvoller Index verwenden?

doch; einer über ip_from und ip_to sollte die Effizienz steigern - Caching mal außer Acht gelassen. Ich kann mir allerdings gut vorstellen, dass er noch effizienter ist, wenn Du die Spalten nummerisch speicherst.

Aber was mich extremst wundert, wieso ist das auslesen von diesen paar Datensätzen um so viel langsamer ist als mit MySQL ohne jeglichen Index.

Auch ohne Index geht ein DBMS anders vor - es liest z.B. nicht _alle_ Daten in den Speicher, sondern nur die benötigten Spalten, und spart sich ebenfalls die Stringverarbeitung (inkl. Speicher-Management der Arrays et.al.). Ich muss jedoch zugeben, dass eine fünffache Geschwindigkeit doch überraschend ist.

Ich meine, wie bitte geht das dann mit dem Archiv hier performant?

Ah, tut es das? ;-)

Das beste was mir eingefallen war [...]
Das hat ja nun wirklich nichts gemacht, aber es liegt immer noch über 0,2 Sekunden. Wieso?

Keine Ahnung. Versuche es mal mit Verzicht auf $com.

Gibts irgendwelche "Tricks" sowas schneller zu machen?

So wie ich das sehe, hast Du schon eine konstante Zeilenlänge garantiert. Das wäre für mich ein solcher Trick. Mehr fällt mir ganz spontan auch nicht ein.

Cheatah

[Philipp Hasenfratz]

Halihallo Andreas

Ich dachte mir, 16.000 Zeilen müsste man doch eigentlich auch recht performant aus einer Flat-File auslesen können, also habe ich das (mit PHP, ich habe alle " aus den Daten entfernt) so versucht:

Jain, die Flat-File müsste schon einige Anforderungen erfüllen, um sie performant
verarbeiten zu müssen. Z. B. würde ich versuchen von der "Textverarbeitung" wegzu-
kommen und eine Lösung über Random-File-Access zu untersuchen. Also alle Datensätze
haben eine fixe Grösse, somit liesse sich bei geordneten IP-Blöcken selbst bei einer
eigenen Lösung schnell eine Art Index entwickeln (mit fseek immer halbieren und so in
log(n) Zeit zum gewünschten Datensatz springen). Aber lassen wir den Index aus:
Durch den wahlfreien Zugriff auf die Datei mit fixer Datensatz Länge lassen sich die
einzelnen Komponenten (IP_FROM, IP_TO) schnell durch deren relativen Position im
Datensatz extrahieren und ein explode würde hinfällig. Grundsätzlich arbeitet explode
ja sehr performant, aber was passiert wirklich? - Explode splittet einen Text und
generiert ein _neues_ Array, neuer Speicher wird allokiert und eine neue Liste wird
aufgebaut. Je nach dem, wie performant die Speicherverwaltung intern von PHP geregelt
ist kann es hier zu Performanceverlust kommen. Bei Datensätzen mit fixer Länge beschränkt
sich das extrahieren von Daten auf einen substr, welcher höchstens ein neuer String
generieren muss (wenn die Variable global definiert ist fällt ein allokieren von neuem
Speicher weg, da die Daten ja per definition gleich lange sind und der global definierte
String genau diese Länge hat [spätestens nach dem ersten Datensatz]).

Aber das war nicht wirklich schnell, hat im Schnitt gut 0,2 Sekunden gedauert. Und wie ich das bedeutend schneller bekommen soll weiß ich auch nicht. Ich habe auch versucht mit einem if, also nur prüfen ob 2. Nummer kleiner als meine Nummer, aber das war kaum schneller. Vielleicht liegt es auch am explode, aber so viel macht das wohl nicht.

Gleicher Vorschlag wie Cheatah: Nummerisch liesse sich dies wohl performanter lösen.
Auch wenn in PHP da nicht unterschieden wird, wird ein String der Länge 4 wohl schneller
verglichen, als ein String mit 15 Zeichen (127.000.000.001).

Und alles in allem(mit Verbindung herstellen und einlesen in PHP) hat das ganze nur noch  0,04 Sekunden gedauert, es war fast 6 mal so schnell.

MySQL arbeitet mit Datensätzen fixer Länge :-)
Nun ja, in C liesse sich das natürlich auch wesentlich schneller realisieren :-)
Datensatz einfach in ein vordefiniertes struct einlesen und die einzelnen Komponenten
vergleichen, wäre IMHO höchst performant!

Dann habe ich mal den Typen von MyISAM auf HEAP verändert, da hat sich auch kaum was getan, lag vermutlich daran dass die Daten so kurz danach noch in irgendeinem Cache lagen.

Tja, oder der HEAP wurde aufgrund grosser Datenmengen in eine Datei ausgelagert...
Kann auch passieren.

Das beste was mir eingefallen war

$fp = fopen("ips.csv","r");
while (!feof($fp)) {
    $buffer = fgets($fp , 21);
    $com = strpos($buffer, ',');
    if((INT) substr($buffer,$com+1,10) >= $dec_ip){
    break;
    }
}

Das hat ja nun wirklich nichts gemacht, aber es liegt immer noch über 0,2 Sekunden. Wieso?

Hm, das heisst doch schon mal Faktor 2 verbessert??? - Das ist doch schon allerhand?
Nun ja, ich kenne die PHP internals nicht, aber ich kann mir vorstellen, dass die
VM von PHP hier Speicher für 6 temporäre Variablen erstellt.

- $buffer
 - 21 wird skalarer Wert, der fgets übergeben wird
 - $com
 - ',' => wird skalarer Wert, der strpos übergeben wird
 - $com+1 wird skalarer Wert, der substr übergeben wird
 - 10 wird skalarer Wert, der substr übergeben wird

Wenn die C-internen Umsetzungen von fgets, strpos und substr mit *char arbeiten[1],
wären es immer noch zwei Variablen, die allokiert werden müssen (und die werden wohl
auch immer vor der Verwendung auf deren Typ und evtl. Inhalt geprüft).

[1] wovon ich (fast) überzeugt bin

Keine Ahnung wie Zend funktioniert, ich habe nur die letzte Zeit etwas über die internas
von Perl nachgedacht und war schockiert! - Wenn ich Computer wäre, würde ich mich bei
meinem Arbeitgeber wegen "zuvielen sinnlosen und redundanten Arbeiten" beschweren! :-)

---

BTW: Ist das langsam? - 0.4 / 0.2 Sekunden für 16'000 Datensätze[1]? - Ich halte 0.04 von
der Datenbank eher für sehr schnell... Oder traue ich den Computern zuwenig zu?

[1] und 4GL Language PHP/Perl

Viele Grüsse

Philipp

[Michael Schröpl]

Hi Andreas Korthaus,

Habe mir die Tabelle runtergeladen, enthält 16.000 Datensätze, und zwar der Form:

das ist genug, um durch den Einsatz einer Baumstruktur etwas gewinnen zu können.

log2(10000) ist 14; Du kannst also bis zu Faktor 1000 gewinnen, abzüglich des Verbindungsaufbaus zur Datenbank und deren interner Code-Generierung & Dateiauslieferung.

Aber das war nicht wirklich schnell, hat im Schnitt gut 0,2 Sekunden gedauert. Und wie ich das bedeutend schneller bekommen soll weiß ich auch nicht. Ich habe auch versucht mit einem if, also nur prüfen ob 2. Nummer kleiner als meine Nummer, aber das war kaum schneller. Vielleicht liegt es auch am explode, aber so viel macht das wohl nicht.

Doch, genau das denke ich. In der Datenbank liegen die einzelnen Felder ja schon getrennt vor.

"SELECT COUNTRY_CODE, COUNTRY_NAME FROM ip WHERE IP_FROM <= '$dec_ip' && IP_TO >= '$dec_ip'"
Und alles in allem(mit Verbindung herstellen und einlesen in PHP) hat das ganze nur noch  0,04 Sekunden gedauert, es war fast 6 mal so schnell.

Seh'nse wohl. ;-)

Dann habe ich mal den Typen von MyISAM auf HEAP verändert, da hat sich auch kaum was getan, lag vermutlich daran dass die Daten so kurz danach noch in irgendeinem Cache lagen.

Dafür wiederum ist Deine Tabelle zu klein. 16000 mal knapp 10 Byte sind kaum mehr als 1 MB - das wird eine gut konfigurierte (!) Datenbank permanent im RAM halten können.

Dann habe ich es mit einem Index versuchen wollen, aber egal was ich da probiert habe hat das ganze eher verlangsamt als es zu beschleunigen. Lässt sich hier einfach kein sinnvoller Index verwenden?

Hier schließe ich mich meinen Vorrednern an: Ein (möglichst) UNIQUE INDEX über die Spalte(n) Deiner WHERE-Klausel(n) bringt ziemlich sicher etwas (je nachdem, wie gut er projeziert - sieht bei Dir aber gut aus).

Aber was mich extremst wundert, wieso ist das auslesen von diesen paar Datensätzen um so viel langsamer ist als mit MySQL ohne jeglichen Index. Ich meine, wie bitte geht das dann mit dem Archiv hier performant?

Das Archiv hat exakt dasselbe Problem wie Du, und es verwendet praktisch dasselbe Verfahren (das ich heute nicht mehr "performant" nennen würde ...).

Viele Grüße
      Michael