Ich implementiere eine Turing-Maschine (man denke an sie als eine virtuelle Maschine) in Javascript. Ich arbeite an einer Routine, die die Berechnungen so effizient wie möglich durchführen soll (dies war von Anfang an kein Schwerpunkt des Projekts).
Ja, ich sollte nicht über die Optimierung nachdenken, außer wenn ich auf Leistungsprobleme stoße. Aber die Natur dessen, was ich tue (wo die meisten nicht-trivialen Programme sehr ineffiziente asymptotische Laufzeiten haben), bedeutet, dass es immer etwas zu gewinnen gibt, wenn man optimiert. Ich möchte mein Bestes geben, um so viele Anweisungen pro Sekunde wie möglich zu bekommen.
Die Lösung ist klar, wenn ich zum Beispiel in C ++ programmieren würde. Mach etwas Timing. %Code%. gprof usw. Ich würde die Architekturen untersuchen, von denen ich erwarte, dass der Code ausgeführt wird, und wahrscheinlich auch einen Blick auf die erzeugte Baugruppe werfen.
Kann das aber nicht mit Javascript tun. Mein erster Instinkt besteht darin, die Operationen in der inneren Schleife auf Array-Lookups zu reduzieren. Es scheint mir, dass es eine gute Wette ist, dass ich die CPU-Cache-Leistung nutzen kann, wenn der Interpreter es in eine (hoffentlich kurze) Reihe von Integer-Operationen übersetzen kann.
Eine Turing-Maschine ist sehr einfach. Es ist tatsächlich die einfachste Formel der Berechnung, die existiert (!): Sie hat eine endliche Anzahl von Zuständen, ein bidirektional unendliches Band, einen Bandkopf, der eine Einheit in eine Richtung bewegen kann und ein einzelnes Zeichen lesen und schreiben kann das Band.
Ein Programm ist in einer Übergangsfunktion codiert, die einen Zustand und ein Zeichen übernimmt, das gelesen wird, und mit dieser Information das zu schreibende Zeichen, die Richtung zum Bewegen des Kopfes und den neuen Zustand liefert.
Dies ist die Logik für jeden Schritt:
%Vor%Der Prozess geschieht in einer Schleife. Es scheint mir klar zu sein, dass das Band ein Array wäre. Ich stelle mir vor, dass das Speichern (Anhängen) von Werten an das Ende eines Arrays mindestens eine amortisierte konstante Zeitoperation mit Javascript-Arrays ist. Es ist viel weniger klar, dass das Anhängen an die Vorderseite eines Arrays auch eine gute Leistung haben würde, so dass ich wahrscheinlich zwei Arrays verwenden möchte, eines nach links und eines nach rechts.
Problem ist, das würde in der naiven Implementierung eine bedingte Anweisung in die innere Schleife einfügen. Ich mag das nicht. Es muss ohnehin eine bedingte Prüfung durchgeführt werden, um zu prüfen, ob der Status der Haltezustand ist. Also wird es vielleicht nicht so schlimm sein.
Es gibt auch eine weitere mögliche Optimierung, die die Indizierung in -O3 eliminieren könnte, indem der Index im Alphabet und nicht der Alphabetwert selbst auf dem Band gespeichert wird.
Aber das Hauptproblem ist das. Welche anderen Dinge könnte ich möglicherweise tun, um es schneller zu machen? Ist es möglich, es überhaupt schneller zu machen? Ich weiß nicht, welche Komponente der Ausführung der Flaschenhals sein wird (CPU oder I / O oder etwas anderes?) Und ich weiß nicht, wie ich das herausfinden könnte. Mit Javascript habe ich auch Hashtabellen zur Verfügung, aber Arrays scheinen immer schneller zu sein.
Vielleicht suche ich vorzeitig einen Rat. Ich werde zurückkommen und mit den Performance-Nummern bearbeiten, während ich Fortschritte mache.
Als Belohnung für das Lesen meiner Frage werde ich einen Link zu einer Live-Work-in-Progress-Version meines Projekts bereitstellen: Ссылка
Bisher wurde eine alph_index mit div gefüllt, die das Band repräsentiert. Es führt auch eine Menge von Operationen an Strings durch und macht auch viel Kopieren von Elementen, was bei der eigentlichen Berechnung der Turingmaschine völlig unnötig ist. Trotzdem erreicht es eine anständige Leistung. Es dauerte ungefähr eine Minute auf meiner Maschine, um 600.000 oder so Schritte zu berechnen (5 ^ 4 = 625), was 10.000 Schritte pro Sekunde ist. Was nicht so schlimm ist, aber ich weiß, dass ich wahrscheinlich mehr als eine Million pro Sekunde mit etwas niedrigerer Programmierung erreichen kann.
Ich schaue mir hier eine Benchmark-Performance an für die Vorgänger-CPUs, die ich kenne 10.000 MIPS pro Kern. Ich schätze daher, wenn ich meine innere Schleife einmal in der Zeit laufen lassen kann, die 50 Dhrystone-Iterationen benötigt (was bei einer einfachen C-Implementierung sehr wahrscheinlich ist, obwohl ich keine Ahnung habe, was diese synthetischen Benchmarks tatsächlich tun), ohne Speicherbandbreite Einschränkungen, ich habe 200 Millionen Iterationen pro Sekunde auf einem Thread. Meine 600k Schritt Berechnung wäre in 3ms abgeschlossen !!
Nun, wenn ich meine 5 ^ 4-Berechnung ausführen kann, ohne dass der Browser mir mitteilt, dass er aufgelegt hat, werde ich ziemlich glücklich sein ...
AKTUALISIEREN
Nachdem eine effizientere JavaScript-Implementierung des Algorithmus abgeschlossen wurde, benötigte die Berechnung von spans unter Verwendung von 58202209 Schritten 6173 ms für die Berechnung. Das sind 9,4 Millionen Schritte pro Sekunde. Fast eine 1000-fache Steigerung gegenüber meiner ursprünglichen DOM-abhängigen Methode.
Die ursprüngliche 9^4 = 6561 Berechnung (die selbst ohne Scrollen des Bandes etwa 30 Sekunden dauerte) ist jetzt in 84 ms abgeschlossen.
Mit Javascript habe ich auch Hash-Tabellen zur Verfügung, aber es scheint wie Arrays wären immer schneller.
Sie denken wahrscheinlich, dass "Array" -Lookup in JavaScript wie folgt funktioniert:
%Vor%Wenn Sie den Index 2 angeben, berechnen Sie einfach:
%Vor% Damit Ihre Suche einfach O(1) time bekommt.
Nicht so, zumindest traditionell, in JavaScript. Im Allgemeinen sind "Array" s Hash-Maps mit numerischen Schlüsseln. Jedes Mal, wenn Sie eine Suche durchführen, führen Sie Ihren Index (der nur als Schlüssel behandelt wird) durch eine Hash-Funktion aus. Also, das:
%Vor%Wird mehr wie behandelt:
%Vor%das, und Sie durchlaufen eine (wahrscheinlich anständig gute) Hash-Funktion, um zu versuchen, die Verteilung von Buckets regelmäßig zu machen und Kollisionen zu minimieren. Dies klingt teuer für mich, aber ich weiß nicht, wie optimierte Implementierungen sind (wie Hash-Map-Lookup-up-Zeit konstant amortisiert wird, aber es ist wahrscheinlich immer noch nicht so effizient und hängt davon ab, wie viele Kollisionen Sie erhalten und was Sie tun, wenn Sie begegnen ein).
Glücklicherweise verstehen einige (wenn nicht sogar die meisten) modernen JavaScript-Interpreter, wie sie mit dichten und dünnen Sammlungen arbeiten müssen, nachdem sie den Code nachverfolgt haben, um zu sehen, ob Sie ihn wie ein Sparse- oder ein dichtes Array verwenden. Überprüfen Sie die Umgebung, die Sie verwenden möchten.
Welche anderen Dinge könnte ich möglicherweise tun, um es schneller zu machen? Ist es möglich, es überhaupt schneller zu machen?
Eine Idee, die ich hatte, war, typisierte Arrays zu verwenden, um eine bessere Chance auf konstante Nachschlaggeschwindigkeit zu haben. Dies half Fabrice Bellard, einen vollständigen Linux-Kernel in den JavaScript / Browser ( jslinux.org ) zu portieren.
Die Lösung ist klar, wenn ich zum Beispiel in C ++ programmieren würde. Mach etwas Timing.
Ich empfehle die Verwendung von jsperf.com , wenn Sie planen, etwas in einem Browser auszuführen (was Ihnen scheint), da sie ziemlich gut sind Java-Timer (mehr Feinheiten, die sich mit Zeit in JavaScript, IIRC befassen) oder einfach node.js oder Rhino und andere Befehlszeilen-Profiling-Tools (Sie können ein DOM in dieser Umgebung emulieren, wenn Sie wirklich brauchen ...).
Wenn Sie sowohl + ve als auch -ve Ganzzahl-Indizes haben wollen, warum verwenden Sie kein einfaches Objekt? Verwenden Sie spezielle Array-Methoden? Die Array-Methoden sind meist generisch und können mit anderen nativen Objekten aufgerufen werden (funktioniert möglicherweise nicht mit Host-Objekten, aber das ist hier kein Problem, denke ich).
In Arrays sind Arrays nur Objekte, daher kann ich nicht nachvollziehen, warum der Zugriff auf Array [i] schneller oder langsamer als das Objekt [i] sein sollte (obwohl es sich natürlich um verschiedene Implementierungen handelt). Sie müssen nur Ihre eigene Längeneigenschaft behalten (vielleicht positive und negative Längen).
Wenn Sie einen Beispielcode bereitstellen, unabhängig von der Leistung, erhalten Sie möglicherweise einen konkreteren Hinweis.
Tags und Links javascript optimization arrays performance