Perl-Hashes verkleinern

bitmuncher

bitmuncher

Senior-Nerd
Ich muss ziemlich grosse Datenmengen durchparsen und daraus spezifische Daten sammeln. Soweit mit Perl auch kein Problem, allerdings erreiche ich eine RAM-Benutzung von ca. 1,5GB, wenn ich die benötigten Daten in Hashes ablege. Das ist aufgrund des zu erwartenden Datenzuwachses (ca. das 100-fache in einem Jahr) absolut inakzeptabel und so suche ich nun schon seit geraumer Zeit eine Möglichkeit die Daten möglichst effizient zu nutzen. Da die Laufzeit auch so schon > 1 Stunde ist, scheidet das temporäre Ablegen der Daten auf der Festplatte aus, da damit die Laufzeit noch weiter verlängert wird. Langsam bin ich mit meinem Latein am Ende. Die in den Hashes abgelegten Daten sind primär Strings als Keys und Integer als Werte. Hat hier evtl. jemand eine Idee, wie ich die Daten möglichst einfach im RAM komprimiert ablegen kann ohne auf die Hashes verzichten zu müssen? Derzeit sieht das Parsen so aus:

Code: 
...
foreach my $line (<INFILE>) {
    if($line =~ /^http:\/\/([\w\.]*)\/.*\s->\s(.*)/) {
        my $referer = $1;
        my $script = $2;
        if(exists($allstats{$referer})) {
            $allstats{$referer} = ++$allstats{$referer};
        } else {
            $allstats{$referer} = 1;
        }
        if($script =~ '^/script1') {
            if(exists($jsw_stat{$referer})) {
                $jsw_stat{$referer} = ++$jsw_stat{$referer};
            } else {
                $jsw_stat{$referer} = 1;
            }
        } elsif($script =~ '^/script2') {
            if(exists($tokstaim_stat{$referer})) {
                $tokstaim_stat{$referer} = ++$tokstaim_stat{$referer};
            } else {
                $tokstaim_stat{$referer} = 1;
            }
        } else {
            if(exists($other_stat{$referer})) {
                $other_stat{$referer} = ++$other_stat{$referer};
            } else {
                $other_stat{$referer} = 1;
            }
        }
    }
}
...
foreach my $line (<INFILE>) {
    if($line =~ /^(\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3})\s.*/) {
        my $ip = $1;
        print $ip."<br />\n";
        if(exists($unique_stat{$ip})) {
            $unique_stat{$ip} = ++$unique_stat{$ip};
        } else {
            $unique_stat{$ip} = 1;
        }
    }
}
...
 
1. Aus Performance Gründen nicht lieber c/C++ verwenden?
2. Ist es nicht möglich, momentan nicht verwendete Daten auf die HD zu schreiben?
3. Wenn du stetig auf GB weise Daten Zugriff brauchst, wäre evtl. der Einsatz einer internen DB wie SQLite interessant.

lg
 
1. Das Ganze in C umzusetzen ist nicht drin, da ich nicht davon ausgehen kann, dass jeder Admin, der da ggf. später Änderungen dran machen muss, auch C beherrscht. Bei wachsender Server-Anzahl ist es aber wahrscheinlich, dass weitere Admins bei uns arbeiten werden.

2. Das Schreiben der Daten auf die HD würde das Auswerten unnötig kompliziert machen, da ich die Datei(en) ja doch wieder einlesen muss. Ausserdem würde es die Laufzeit des Skript noch weiter verlängern, was bei wachsendem Datenzuwachs keine gute Idee wäre. Mehr als 6 Stunden für einen Durchlauf ist einfach nicht drin, selbst wenn irgendwann drastisch mehr Daten anfallen.

3. Ich brauche sie nicht ständig. Ich benötige sie nur zur einmaligen Auswertung. Momentan wäre das aber auch mein Ansatz, nur wäre mir lieber, wenn ich ohne zusätzliche Server-Lösungen auskommen könnte.
 
foreach my $line (<INFILE>) {
Zum Vergrößern anklicken....

Du liest in einem script mehrmals die ganze Datei ein?

In Faellen von grossen Datenmengen und begrenzten Kapazitaeten
splitte ich vorher die Dateien in kleinere Teile. Das hat aber meist andere
Gründe. Aber egal was du tust, wirkllich schneller wirst du es nicht bekommen.
Und wenn du irgendwann das 100-fache an Daten hast, solltest du ernsthaft darueber
nachdenken das in einer etwas performanteren Sprache zu loesen. Regex sind und bleiben
leider arschlahm.
 
Momentan wäre das aber auch mein Ansatz, nur wäre mir lieber, wenn ich ohne zusätzliche Server-Lösungen auskommen könnte.
Zum Vergrößern anklicken....
Darum eben SQLite ;) http://www.sqlite.org/serverless.html

Es gibt dabei keinen SQL Server, der separat läuft oder Einrichtung benötigen würde. Desweiteren ist SQLite gerade in dieser Hinsicht super schnell, da keine aufwändige Client/Server Verbindung zwischen deinem Skript und der DB steht.
 
Du liest in einem script mehrmals die ganze Datei ein?
Zum Vergrößern anklicken....

Nein, ich lese 2 Dateien zeilenweise ein. Würde ich sie komplett einlesen, würde das sämtliche Dimensionen an verfügbarem RAM und Swap sprengen. Sieht evtl. etwas verwirrend aus, weil ich die Zuweisungen von $infile und die open()-Funktionen für den Deskriptor INFILE nicht gepostet habe.

In Faellen von grossen Datenmengen und begrenzten Kapazitaeten splitte ich vorher die Dateien in kleinere Teile.
Zum Vergrößern anklicken....

Das Problem ist nicht die Grösse der Datei, sondern die Grösse der entstehenden Hashes mit den rausgeholten Daten.

Regex sind und bleiben leider arschlahm.
Zum Vergrößern anklicken....

Das halte ich für ein Gerücht. Das Parsing geht unheimlich schnell, was ich sehen kann, wenn ich mir $1 und $2 direkt ausgeben lasse. Die lange Laufzeit kommt dadurch zustande, dass er beim Verarbeiten der Daten ständig am Swappen ist, weil die Hashes nicht in den RAM passen.

@90nop: Das klingt gut. Ich schau mir das mal an. Die DBD-Module für Perl hab ich eh im System und das scheint SQLite-Funktionalitäten mit drin zu haben.
 
SQLLite soll "nicht so gut" für richtig große Datenmengen sein. Probieren kann man es natürlich trotzdem :).
Btw: sehe ich das richtig, dass der Hash samt Ergebnis in einem assoziativen Array gespeichert wird? Rein hashmäßig würde man ja sonst die 1.5GB erst mit 200 Mio Hashs vollbekommen (8Byte pro Hash).

Problem ist also: die ganzen Daten belegen 1.5 GB, wobei bei der Datenmenge zur eigentlichen Ausführungszeit nur Hashes zum Vergleich gebraucht werden - die Daten(der Inhalt) an sich ist erstmal egal und wird erst am Ende für die Statistik/sonstwas gebraucht.
Da es soviele Daten sind, wird geswappt - ohne dabei auf die "Wichitgkeit" der Daten zu achten (da alles "in einer Tabelle/Array" steht. "wichtigkeit"=Häufigkeit des Vorkommens, gibt ja bestimmt Datensätze, die sehr oft vorkommen und einige, die nur paar mal drin sind) - bei weiteren Zugriffen muss der Teil wieder in den Speicher geladen werden ->Verzögerung.

Lösungsmöglichkeit 1: die Daten so organisieren, dass die "wichtigsten" (also am häufigsten anzutreffenden) möglichst immer im Speicher verbleiben. Da könnte man mittels Splay-Bäumen machen. Das sollte Tree::Smart Modul sein (sagt zumindest google). Hier hat man den Nachteil, dass die Zugriffszeit auf die einzelnen Hashs sich verlängert - der Vorteil ist allerdings, dass die Hashs und Daten, die auf häufigsten zugegriffen wird, auch am längsten im Speicher verbleiben.

Lösungsmöglichkeit 2 (finde ich irgendwie am praktikabelsten): Hashs und Daten trennen. D.h einmal eine reine Hashtabelle und einmal eine, bei der Hashs+zugehörige Daten stehen. Bei der Suche wird dann in der reinen Hashtabelle erstmal geschaut, ob das überhaupt vorkommt - und wenn nicht, in diese (und die Datan-Hashtabelle) eingefügt. Vorteile: die "reine" Hashtabelle sollte viel kompakter sein und insgesamt kaum ausgelagert werden - erst wenn es irgendwas komplett Neues gibt, wird die zweite, "große" Tabelle bemüht. Nachteile - mehr Programmieraufwand.
Diese Trennung (in etwa) lässt sich natürlich auch mit benutzung einer DB erreichen (primary Keys sind ja i.R gehasht und die DB-Engine trennt die Daten von Hashs "automatisch").
 
Zur Begriffsklärung: In Perl nennt man assoziative Arrays "Hashes". Hat nichts mit Verschlüsselung zu tun. Siehe: http://www.perl.com/pub/a/2006/11/02/all-about-hashes.html

In den Hashes gibt es keine Daten, die besonders häufig vorkommen oder irgendwie besonders wichtig sind. Eine Sortierung der Daten würde daher keine Vorteile bringen und eine Trennung irgendwelcher Daten ist nicht möglich ohne die Auswertung unmöglich zu machen.
 
Zur Begriffsklärung: In Perl nennt man assoziative Arrays "Hashes". Hat nichts mit Verschlüsselung zu tun.
Zum Vergrößern anklicken....
Jep, allerdings wird intern der Key "gehasht" - also mittels einer Funktion (wie hier, eventuell inzwischen auch verbessert: http://perl.plover.com/FakeHash/FakeHash.pm) ein Wert gebildet, der dann für die Positionierung im Array genutzt wird. Entspricht z.B Hashtables in Java. So wie ich es im Source sehe, wird auch wie in Java die "double" Strategie verwendet (wird das Array zu klein, wird ein doppelt so großes angelegt und die ganzen Daten rüberkopiert, was inbesondere bei dem 512MB->1GB und 1GB->2GB Schritt doch deutlich spürbar sein sollte).

Die Idee ist nun, diesen Hashwert selbst zu nutzen (oder notfalls eine äquivaltente Funktion, die einen solchen Hashwert bildet) und in zwei Arrays abzulegen - einmal nur den "reinen" Wert und einmal mit zugehörigen Daten.
Bsp:
Code: 
Tabellen/Arrays:

Hashtabelle/array:
hash1
hash2
hash3


assoziatives_array
hash1<->daten1
hash2<->daten2
hash3<->daten3
Code: 
Bearbeite Daten:
myHash=bilde_hashwert(gefundene_daten);
if (exists(Hashtabelle(myHash))  do_something
else
füge_ein(hashtabelle(myHash);
füge_ein(assoziatives_array(myHash,gefundene_daten);
do_something;
Der Bezug Hashwert<->Daten bleibt also erhalten und die Daten können am Ende ausgewertet werden.

Bzw (auf den vorhandenen Code bezogen):
zusätzlich ein assoziatives Array mit Hash<->Daten Zuordnung anlegen, Hashwert von $1 bilden, in dem Array ablegen und dem $referer den Hashwert zugewiesen - dann stehen in den ganzen $_stat Arrays nicht die langen Strings, sondern nur der kurze Hash drin. Den zugehörigen String kann man dann bei der Auswertung am Ende in dem einen Array abfragen.
 
Hm, wäre Storable eventuell eine Möglichkeit?
Da dann die freeze und thaw Methoden (da du ja kein Festplatten-IO haben möchtest).
Nachteil: kurzzeitig würde die RAM-Auslastung recht signifikant hochspringen (nämlich dann, wenn du grade das echte Hash und die stringified-Version defined hast).
Vorteil:
Code: 
#!/usr/bin/env perl
use strict; use warnings;
use Storable qw(freeze thaw);
use Devel::Size qw(size total_size);

my %testHash;
for my $n (1 .. 100_000) {
    my $randstring = crypt $n => "ab";
    $testHash{$randstring} += $n;
}
my $stringified = freeze(\%testHash);
print "total size of %testHash:\t\t", total_size(\%testHash), " bytes\n";
print "total size of \$stringified:\t\t", size(\$stringified),     " bytes\n";
Ausgabe:
Code: 
total size of %testHash:                5624348 bytes
total size of $stringified:             2199660 bytes

Du brauchst ja zum Beispiel die ersten beiden hashes in der zweiten Schleife (vielleicht im gesamten zweiten Programmpart?) nicht wirklich. Ansonsten würde ich auch zu einer DB Lösung tendieren.

N paar Links:
tü del ü

edit: noch zum "warum" der Speicher-Freizügigkeit von perl-hashes Devel::Size
 
Perl-Hashes verkleinern gelöst, aber weitere Unklarheit

Nachdem ich die Methoden hier ausprobiert habe, habe ich das Ganze nun doch über MySQL gelöst, da es Performance-mässig offenbar das Brauchbarste ist. Auch SQLite konnte da nicht mithalten, da der HD-Durchsatz enorm anstieg, und die Verwendung ist weitaus umständlicher als MySQL mit DBIx::DWIW. Die Werte werden direkt in die DB gepackt und dort rausgeholt, wenn sie benötigt werden. Das setzt zwar die DB auch ziemlich unter Last, aber bei weitem nicht so sehr, als würde ich die Daten in Arrays oder Hashes halten.

Allerdings bin ich auf ein recht seltsames Verhalten gestossen, für das ich noch keine Erklärung habe. Anfangs hatte ich

Code: 
foreach my $line (<INFILE>)...

genutzt um zeilenweise durch die Datei zu gehen. Seltsamerweise hat aber schon das enorm RAM gefressen und den Code spätestens beim zweiten Loop in der Ausführung gestoppt, als würde er die Datei komplett einlesen. Mit kleinen Dateien geht es aber problemlos. Nun habe ich

Code: 
while (<INFILE>) {
    my $line = $_;...

verwendet und das Problem tritt nicht mehr auf. Hat evtl. jemand eine Idee woran das liegen kann? Theoretisch tut der Code ja das gleiche. Er nimmt die aktuelle Zeile aus der Datei und weist sie $line zu.
 
Auch SQLite konnte da nicht mithalten, da der HD-Durchsatz enorm anstieg, und die Verwendung ist weitaus umständlicher als MySQL mit DBIx::DWIW.
Zum Vergrößern anklicken....

Ich gehe mal davon aus, dass du lokal einen MySQL Server aufgesetzt hast, oder?
Abgesehen von der umständlichen Verwendung, bin ich doch überrascht dass SQLite mehr Probleme bereitet. Mehr HD Zugriffe als MySQL - SQLite sollte im direkten Vergleich performanter sein als MySQL.

Vielleiciht schreibt SQLite in gleicher Zeit mehr auf die HD weil es eben schneller ist - wäre dann auch schneller fertig. :)
 
Solange es um relativ kleine Datenmengen geht, ist SQLite sicherlich die bessere Lösung, aber sobald nicht sämtliche Daten vom Kernel in den HD-Cache gepackt werden können, beginnt die Begrenzung durch den HD-Durchsatz das Ganze auszubremsen. Momentan verteile ich das auf ein NDB-Cluster und schiebe nur die Endergebnisse in eine lokale DB, wodurch natürlich einiges an Performance rausgekitzelt wird. Temporär ist das auch erstmal ok so, aber irgendwann werde ich das ändern müssen, da das Cluster nicht der Firma gehört. Da will ich aber vorher noch verschiedene dateibasierte DB-Engines ausprobieren wie BDB, SQLite usw. um zu sehen, welche für meine Zwecke die schnellste ist. Der Zeitdruck ist jetzt aber erstmal genommen, da das Tool soweit funktioniert und andere Prozesse auf dem Server nicht zu stark ausbremst. Mit Arrays im RAM rumspielen scheidet aber auf jeden Fall aus. Egal was ich da mache, irgendwann ist das System nur noch mit Swappen beschäftigt.
 
Seltsamerweise hat aber schon das enorm RAM gefressen und den Code spätestens beim zweiten Loop in der Ausführung gestoppt, als würde er die Datei komplett einlesen.
Zum Vergrößern anklicken....
Tut er auch. <filehandle> in list-context liest die komplette Datei auf einmal ein. for-Scheifen iterieren über eine Liste, deswegen list-context. while liest halt jedesmal nur ne Zeile ein.

edit:
und
Code: 
while (<INFILE>) {
    my $line = $_;
Kann man besser gleich als
Code: 
while (my $line = <INFILE>) { }
schreiben.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben