Masterarbeit: Performanceprobleme

Hallo.

Ich schreibe gerade meine Masterarbeit (Uni, Angewandte Informatik), welche ich diesen Monat abgeben werde.
Meine Aufgabe bestand u.a. darin, einige Algorithmen zu entwickeln, um bestimmte Informationen aus größeren Datenquellen zu extrahieren.

Die Datenquellen liegen mir als JSON und CSV vor, können aber in jedes beliebige Format konvertiert werden.
Auf meine Testdaten, die eher klein sind, lassen sich die Algorithmen erfolgreich anwenden, mein PC bekommt allerdings schon Probleme, wenn ich die Daten auf 300 Zeilen erhöhe. Nach mehreren Minuten wird er sehr langsam, bis er sich sogar aufhängt. Sinnvolles Testen mit unterschiedlichen Parametern wird somit unmöglich. Besonders, wenn man berücksichtigt, dass die realen Daten über 100.000 Zeilen lang sind.

Mit meinem Betreuer haben wir meine Algorithmen bereits begutachtet und etwas verbessert. Auch alleine habe ich bereits mehrere Wochen damit verschwendet, sie noch effizienter zu implementieren. Wirklich geholfen hat es nicht.
Die Zeit drängt allerdings. Nun mache ich mir Sorgen, dass ich nicht viel zur Evaluation schreiben werde, was das wichtigste Kapitel meiner Thesis darstellt.
Nur 300 Zeilen zu evaluieren macht wenig Sinn, wenn die realen Daten über 100.000 Zeilen haben.

Klar, man könnte die Algorithmen wochenlang verbessern und evtl. über Multithreading nachdenken, dies war jedoch nicht Teil meiner Aufgabe und am Anfang auch noch nicht ersichtlich.

PS: Es handelt sich um mehrere Funktionen mit verschachtelten Schleifen, die jeweils über die ganzen Daten laufen. Da es eine Webanwendung ist, kann es nur im Browser ausgeführt werden.

Hat jemand einen Tipp? Es wäre nämlich schade, an der Performance zu scheitern.

Danke!

Im Ernst jetzt?

Der Kernpunkt deiner Aufgabe waren große Datenmengen und Multithreading ist kein Thema? Was ist dann das Thema und wieso ist das eine Masterarbeit (tut mir Leid, sieht für mich nicht so aus). Multithreading drüber zu bauen sollte übrigens weniger als eine Woche dauern... (wie viele verschiedene Algos sind es denn?)

Außerdem passt da ja etwas nicht. 300 Zeilen zu parsen ist nichts. Was machst du mit den Daten? (wie groß sind die, ist die Speicherverwaltung das Problem?)

Ich versteh auch nicht, wie es zu einem frezze kommt. Du verwendest Java/C# nehm ich an?

hallo7 schrieb:

Der Kernpunkt deiner Aufgabe waren große Datenmengen und Multithreading ist kein Thema? Was ist dann das Thema und wieso ist das eine Masterarbeit (tut mir Leid, sieht für mich nicht so aus). Multithreading drüber zu bauen sollte übrigens weniger als eine Woche dauern... (wie viele verschiedene Algos sind es denn?)

Außerdem passt da ja etwas nicht. 300 Zeilen zu parsen ist nichts. Was machst du mit den Daten? (wie groß sind die, ist die Speicherverwaltung das Problem?)

Ich versteh auch nicht, wie es zu einem frezze kommt. Du verwendest Java/C# nehm ich an?

Zum Vergrößern anklicken....

Das Auslesen der Datenmengen ist nicht das Problem. Nur das Anwenden der Algorithmen braucht Zeit. Es sind mehrere, 2 davon brauchen besonders lang. Da die Daten untereinander verglichen werden müssen, steigt die Ausführungszeit quadratisch an.
Am Anfang war es nicht ersichtlich, dass es zu solchen Problemen kommen wird, deshalb wurde über Multithreading auch nicht nachgedacht. Mein Thema besteht auch nicht darin, die Performance der Algorithmen zu evaluieren, sondern herauszufinden, ob die Ideen bzw. Probleme, die wir uns anfangs gestellt hatten, zu lösen sind.

Wie bereist erwähnt, handelt es sich um eine Browseranwendung (dafür gab es Gründe), ich verwende also JavaScript.

Ist der Algorithmus von dir? An sich klingt, dass nach einem recht schlechten Algorithmus für das Problem. Auch mehr CPU power und rechenleistung wird nichts bringen wenn du schon mit 300 Zeilen deine Probleme hast.

Das PS: hab ich gekonnt überlesen, tut mir leid

Ok, das erklärt etwas mehr (z.B. die freezes bzw. die erhöhte Komplexität die man für eine Masterarbeit erwartet).

Weißt du warum er abstürzt? Prozessorauslastung sollte ja egal sein, der kann auch stundenlang auf 100% laufen. Wenn es auch nicht der Speicher ist, der langsam voll wird (auch untersuchen ob der Browser bestimmte Limits hat), dann wird es irgendetwas sein, was der Browser nicht mag. Das kann unschön werden, da kann ich dir nicht helfen (viel zu viele Möglichkeiten) :/

Theoretisch könntest du die Algorithmen ja in einer klassischen Sprache implementieren und die große csv evaluieren lassen. Dann hast du zumindest ein Ergebnis ob die Algorithmen an sich funktionieren. Keine Ahnung ob das eine Option ist.

Wenn es darum geht Performance zu evaluieren ist ein mögliches Ergebnis immer, dass die zu evaluierenden Ansätze Mist sind. Es muss nur begründet werden mit anschließendem Ausblick welche Möglichkeiten zukünftig in Betracht gezogen werden können um das eigentliche Problem zu lösen.

Eine Analyse wieso der Algorithmus lange dauert zum Beispiel. Was sich daran verbessern lässt und ob Konzepte wie Parallelisierung (im Zweifelsfall über gar über die GPU) für den Algorithmus anwendbar sind. Im Zweifelsfall sind auch Ergebnisse wie "JavaScript ist ungeeignet" Ergebnisse. Wenn ein Prototyp in C/C++ um Faktoren schneller läuft beispielsweise.

----------------------

Alle Daten mit allen Daten vergleichen? Ist es möglich vor diesem Vergleich die Daten sinnvoll zu sortieren / klassifizieren / ordnen, das spart mitunter viel Zeit beim Vergleichen/Suchen.

hallo7 schrieb:

Weißt du warum er abstürzt? Prozessorauslastung sollte ja egal sein, der kann auch stundenlang auf 100% laufen. Wenn es auch nicht der Speicher ist, der langsam voll wird (auch untersuchen ob der Browser bestimmte Limits hat), dann wird es irgendetwas sein, was der Browser nicht mag. Das kann unschön werden, da kann ich dir nicht helfen (viel zu viele Möglichkeiten) :/

Zum Vergrößern anklicken....

Browser möge es nicht, wenn langandauernde scripte laufen. Warum er es im Browser ausführt ist mir aber ein rätzel. Könnte es genauso mit nem Taskrunner wie gulp local laufen lassen.

Funart schrieb:

Ist der Algorithmus von dir? An sich klingt, dass nach einem recht schlechten Algorithmus für das Problem. Auch mehr CPU power und rechenleistung wird nichts bringen wenn du schon mit 300 Zeilen deine Probleme hast.

Zum Vergrößern anklicken....

Ja, er ist von mir.
Wie gesagt, die letzten 2 Wochen habe ich ausschließlich damit verbracht, die Performance zu optimieren, zusammen mit meinem Betreuer. Viel mehr in dieser Richtung kann ich leider nicht mehr machen.
Die eigentliche Aufgabe wird ja erfüllt, bei kleinen Datenmengen wird das gewünschte Ergebnis geliefert.

hallo7 schrieb:

Theoretisch könntest du die Algorithmen ja in einer klassischen Sprache implementieren und die große csv evaluieren lassen. Dann hast du zumindest ein Ergebnis ob die Algorithmen an sich funktionieren.

Zum Vergrößern anklicken....

Das wäre sicherlich eine Möglichkeit, nur muss ich abschätzen, ob die Zeit dafür reicht.

Piktogramm schrieb:

Wenn es darum geht Performance zu evaluieren ist ein mögliches Ergebnis immer, dass die zu evaluierenden Ansätze Mist sind. Es muss nur begründet werden mit anschließendem Ausblick welche Möglichkeiten zukünftig in Betracht gezogen werden können um das eigentliche Problem zu lösen.

Zum Vergrößern anklicken....

Nein, es geht eben nicht darum, die Performance zu evaluieren, sondern die Algorithmen an sich. Ob sie die gewünschten Ergebnisse liefern. Dies ist der Fall bei kleineren Daten, allerdings kann ich dazu nicht viel zu großen Daten sagen.

Funart schrieb:

Browser möge es nicht, wenn langandauernde scripte laufen. Warum er es im Browser ausführt ist mir aber ein rätzel. Könnte es genauso mit nem Taskrunner wie gulp local laufen lassen.

Zum Vergrößern anklicken....

Von Taskrunnern habe ich noch nie etwas gehört. Ich habe zwar eben 2 Stück gefunden gruntjs und gulbjs, allerdings muss ich mich damit erstmal beschäftigen.
Könntest du mir verraten, welche Vorteile sie mir genau bieten?

Basieren auf NodeJS. Damit kannst an sich nur relative leicht etwas ausführen. Je nachdem wie dein Code aussieht lässt der sich dann vl 1:1 ohne browser in der console ausführen. Browser stoppen unter umständen langandauerende Scripte.

Ich geh davon aus, dass dein Algorithmus ungeeignet ist um das Problem mit größeren Datenmengen zu lösen. Dazu müsste ich aber das Problem und deinen Algo kennen.

stjudent schrieb:

Das wäre sicherlich eine Möglichkeit, nur muss ich abschätzen, ob die Zeit dafür reicht.

Zum Vergrößern anklicken....

Das schaffst du bestimmt heute noch, du musst ja nur die Syntax ändern
Manchmal muss man eben etwas Freizeit investieren.

stjudent schrieb:

Nein, es geht eben nicht darum, die Performance zu evaluieren, sondern die Algorithmen an sich. Ob sie die gewünschten Ergebnisse liefern. Dies ist der Fall bei kleineren Daten, allerdings kann ich dazu nicht viel zu großen Daten sagen.

Zum Vergrößern anklicken....

Naja, wenn der Algorithmus für sich evaluiert werden soll wird es doch sicher irgendwo eine Betrachtung bzw. Abschätzung zur Laufzeit geben. In deinem Falle ist die gerade recht mies und würde so wie du es beschreibst derzeit die Anwendung für reale Fälle verhindern. Diese Einschätzung kann man so durchaus in eine Arbeit schreiben. Erfahrungsgemäß ist wird sowas von Professoren und Betreuern gern angegriffen. Wenn also die Performance der beschränkende Faktor ist, sollte da evaluiert werden, welche Verbesserungen möglich sind. Sowas wie Multithreading, Wechsel der Laufzeitumgebung/Sprache, Sortieren von Daten etc. ist da ein Blick wert. Man sollte also ausschließen, dass die naheliegensten Ansätze das Problem nicht lösen, oder man lebt damit, dass die eigene Arbeit zerrissen wird.

Wie lange braucht dein Code um ausgeführt zu werden für deine 300 Zeilen? Anhand der Komplexität kannst du dann abschätzen wie lange es mindestens dauern würde für 10.000 Zeilen.

Warum wird für eine scheinbar rechenintensive Aufgabe Javascript verwendet?
Javascript ist definitiv das falsche Werkzeug für performanceintensive Berechnungen. War das vorgegeben oder deine Idee?
In letzterem Falle wäre das sehr schwer im Kolloqium zu rechtfertigen. Wenn die Performance zu schlecht ist für die vorhersehene Datenmenge und dazu ein um mehrere Größenordnungen langsamere Programmiersprache verwendet wurde, ist das fachlich nicht begründbar.

Je nach Problem ist Javascript zb. 250 mal langsamer als C++ (verlinktes Beispiel mit FLOPS)
SO Js vs C++

Versuch es mal in C++/C und parallelisier es schmerzfrei mit OpenMP oder sogar OpenAcc. Das geht einfach mit Pragmas, falls der Code es hergibt.

Wenn dir deine Note wichtig ist würde ich eine Verlängerung der Masterarbeit beantragen und es in C++ implementieren. Da du die Algos einmal entwickelt hast, sollte die Portierung nicht allzu schlimm werden.

Das Javascript langsamer ist als C stimmt zwar noch immer, die Performancedifferenz Javascript zu C ohne Compileroptimierung bewegt sich jedoch je nach Problem heutzutage eher im Bereich der unteren einstelligen Faktoren und selbst mit Optimierungen ist die Differenz zu klein um bei quadratisch steigendem Rechenbedarf den Anstieg annähernd zu kompensieren, den es beim Sprung von 300 auf 10.000 Datensätze gibt. Insofern müsste der Wechsel der Programmiersprache entweder induziert werden, weil technische Grenzen dies erzwingen, oder aber man switcht auf C bzw. eine andere Sprache um alle Compileroptimierung und zusätzlich Sachen wie Multithreading, OpenMP, Cilk, etc. mit zu nutzen. Je nach System lässt sich so real wohl wirklich ein Geschwindigkeitsvorteil von >100 herausholen.

Hi, ich sehe hier 2 Möglichkeiten, wie du die Performanceprobleme lösen kannst:

#1 wie oben erwähnt, die Algorithmen serverseitig mit C++ o. ä. durchlaufen lassen. Wenn das Ergebnis im Browser dargestellt werden muss, kann man heutzutage sehr schnell eine JSON API zusammenstellen dann einfach per Ajax das Ergebnis holen und anzeigen.

#2 mit Web Workers API https://developer.mozilla.org/en-US/docs/Web/API/Web_Workers_API/Using_web_workers
JavaScript an sich ist zwar single threaded und synchron, aber mit den ganzen browser apis kann man damit auch rechenintensive Sachen durchführen ohne das UI zu blockieren.