Optimierung: lieber Rechnen oder Speichern?

[ActiviT]

Hi Selfler!!

Angenommen ich habe eine Javascript Klasse. Nun muss ich für viele Instanzen dieser Klasse, alle 40 Millisekunden eine bestimmte Größe berechnen. Beispielsweise hat die Instanz die Attribute A1 und A2 und es muss folgendes berechnet werden:

pow( (A1 + A2), 2) - A1

Da sich die Werte A1 und A2 sehr sehr selten ändern, ist zu überlegen, ob ich nicht den entsprechenden ausgerechneten Wert in einer weiteren Variable speichere. Nun stellt sich mir die Frage, wieviel RAM so eine Variable inkl. Overhead in Javascript verbraucht und ob sich das lohnt. Immerhin haben die meisten PCs heutzutage schon 1GB RAM und fast alle mindestens 512MB RAM.

PS: Falls ihr eine gute Möglichkeit kennt, um die Performance eines Javascripts zu messen (vermutlich braucht man ja sehr viele Durchläufe), bitte teilt sie mir mit.

PPS: Es kann ruhig ein großer Teil des restlichen Arbeitsspeichers benutzt werden. Das ganze ist für ein Spiel, weswegen es nicht schlimm ist, wenn der Arbeitsspeicher auch entsprechend gebraucht wird.

[molily]

Hallo,

ob ich nicht den entsprechenden ausgerechneten Wert in einer weiteren Variable speichere

Ist prinzipiell erstmal besser als die Operation immer wieder durchzuführen.

Ich lege bei komplizierteren Berechnungen, bei denen es nur einen oder wenige Eingabewerte gibt, einen Cache an und runde dabei um einige Stellen, sodass der Cache klein bleibt, aber viele Anfragen schnell und ausreichend genau beantwortet werden können, ohne nochmal zu rechnen. (Meistens interessieren einen nur ein paar Nachkommastellen, wenn man links vom Komma nicht viel hat.)

Nun stellt sich mir die Frage, wieviel RAM so eine Variable inkl. Overhead in Javascript verbraucht

Es hängt wohl ganz vom Browser und dessen JavaScript-Engine ab, wie der Speicher gemanaget wird. Wenn du nicht gerade hunderttausende Objekte anlegst, dürfte das kaum ins Gewicht fallen, diese Zahlen zwischenzuspeichern.

PS: Falls ihr eine gute Möglichkeit kennt, um die Performance eines Javascripts zu messen (vermutlich braucht man ja sehr viele Durchläufe), bitte teilt sie mir mit.

Du kannst im Prozessmonitor deines Betriebssystems sehen, wieviel Speicher die Browserinstanz gerade braucht und wie der Speicherverbrauch zu- und abnimmt beim Laden und Verlassen der Seite.

Mathias

[ActiviT]

Hallo,

ob ich nicht den entsprechenden ausgerechneten Wert in einer weiteren Variable speichere

Ist prinzipiell erstmal besser als die Operation immer wieder durchzuführen.

O.K.

Ich lege bei komplizierteren Berechnungen, bei denen es nur einen oder wenige Eingabewerte gibt, einen Cache an und runde dabei um einige Stellen, sodass der Cache klein bleibt,

Einen Cache? In welcher Form? Und wieso rundest du? Brauchen gerundete Werte mit weniger dezimalen Nachkommastellen auch weniger RAM?

Nun stellt sich mir die Frage, wieviel RAM so eine Variable inkl. Overhead in Javascript verbraucht

Es hängt wohl ganz vom Browser und dessen JavaScript-Engine ab, wie der Speicher gemanaget wird. Wenn du nicht gerade hunderttausende Objekte anlegst, dürfte das kaum ins Gewicht fallen, diese Zahlen zwischenzuspeichern.

Du hast jetzt natürlich übertrieben. Aber was ist bei 1000 oder 10000 Objekten? Dazu könnte es durchaus kommen.

PS: Falls ihr eine gute Möglichkeit kennt, um die Performance eines Javascripts zu messen (vermutlich braucht man ja sehr viele Durchläufe), bitte teilt sie mir mit.

Du kannst im Prozessmonitor deines Betriebssystems sehen, wieviel Speicher die Browserinstanz gerade braucht und wie der Speicherverbrauch zu- und abnimmt beim Laden und Verlassen der Seite.

Klar, aber diese Werte sind zu ungenau, weil sie natürlich durch diverse andere Programme und den Kernel beeinflusst werden. Mit 1000 Durchläufen, wäre das ganze sicherliche präziser, aber das manuell zu machen ist Wahnsinn. Gibt es eine Möglichkeit das ganze zu automatisieren oder doch noch eine andere Möglichkeit, die Werte herauszufinden? (Ich denke da z.B. an eine FF Erweiterung, die den aktuellen RAM-Verbrauch nur von Javascript auslesen kann)

[Alexander (HH)]

Moin Moin!

Hallo,

ob ich nicht den entsprechenden ausgerechneten Wert in einer weiteren Variable speichere

Ist prinzipiell erstmal besser als die Operation immer wieder durchzuführen.

O.K.

Ich lege bei komplizierteren Berechnungen, bei denen es nur einen oder wenige Eingabewerte gibt, einen Cache an und runde dabei um einige Stellen, sodass der Cache klein bleibt,

Einen Cache? In welcher Form?

z.B. ein assoziatives Array.

Und wieso rundest du? Brauchen gerundete Werte mit weniger dezimalen Nachkommastellen auch weniger RAM?

Nein. Aber Du mußt weniger Werte speichern, wenn Du auf drei bis vier tragende Stellen rundest, statt acht bis zwölf tragende Stellen herumzuschleppen. Dabei wird das Ergebnis natürlich auch ungenau.

Beispiel:

Mit drei tagenden Stellen gibt es 3.13, 3.14, 3.15. Dazwischen gibt es gar nichts. Der Cache belegt für den Bereich von 3.13000 bis 3.15999 exakt drei Plätze (mit jeweils ein paar Bytes). PI wird stumpf auf 3.14 abgerundet, je nach Operation erzeugt das einen Fehler im Bereich 1%.

Mit "nur" sechs tragenden Stellen belegt der Cache von 3.13000 bis 3.15999 dreitausend Plätze (einige kBytes), mit neun tragenden Stellen drei Millionen Plätze (einige MBytes), mit zwolf tragenden Stellen drei Millarden Plätze (einige GBytes).

Nun stellt sich mir die Frage, wieviel RAM so eine Variable inkl. Overhead in Javascript verbraucht

Das hängt von der JS-Engine ab. Eine nackter float, single oder double (in C) belegt irgendwo zwischen vier und zwölf Bytes.

Du kannst im Prozessmonitor deines Betriebssystems sehen, wieviel Speicher die Browserinstanz gerade braucht und wie der Speicherverbrauch zu- und abnimmt beim Laden und Verlassen der Seite.

Klar, aber diese Werte sind zu ungenau, weil sie natürlich durch diverse andere Programme und den Kernel beeinflusst werden.

Nein, die Speicherdaten für den einen Prozess hängen nur von dem einen Prozess ab.

Mit 1000 Durchläufen, wäre das ganze sicherliche präziser, aber das manuell zu machen ist Wahnsinn.

Warum willst Du derartig große Datenmengen in Javascript herumschleppen? Ich befürchte, Du machst entweder etwas, was besser auf dem Server aufgehoben wäre, oder etwas, das besser mit Flash umgesetzt würde. Die "40 Millisekunden" sprechen für eine Animation. Nimm Flash, das ist dafür ausgelegt. Sorge für alternativen Inhalt, falls der Benutzer kein Flash hat oder haben möchte.

Alexander

[Klawischnigg]

Hi there,

Mit drei tagenden Stellen gibt es 3.13, 3.14, 3.15. Dazwischen gibt es gar nichts. Der Cache belegt für den Bereich von 3.13000 bis 3.15999 exakt drei Plätze (mit jeweils ein paar Bytes). PI wird stumpf auf 3.14 abgerundet, je nach Operation erzeugt das einen Fehler im Bereich 1%.

Zuerst redest Du vom Cache als assoziativem Array und dann behauptest Du, dieser Cache würde gefüllt mit dazwischenliegenden Dezimalzahlen, wenn nur die drei Zahlen benötigt werden???

Mit "nur" sechs tragenden Stellen belegt der Cache von 3.13000 bis 3.15999 dreitausend Plätze (einige kBytes), mit neun tragenden Stellen drei Millionen Plätze (einige MBytes), mit zwolf tragenden Stellen drei Millarden Plätze (einige GBytes).

wird ja immer schlimmer. Wenn Du irgendein Array mit den Werten arr[0]=3.13000 und arr[1]=3.15999 hast füllt Javascript dazwischen drei Millionen Plätze aus ????

Warum willst Du derartig große Datenmengen in Javascript herumschleppen? Ich befürchte, Du machst entweder etwas, was besser auf dem Server aufgehoben wäre, oder etwas, das besser mit Flash umgesetzt würde. Die "40 Millisekunden" sprechen für eine Animation. Nimm Flash, das ist dafür ausgelegt. Sorge für alternativen Inhalt, falls der Benutzer kein Flash hat oder haben möchte.

Ich glaub nicht, daß er für mich extra eine Javasriptvariante programmieren will, nur weil ich die Flashzapplerei wie soviel nicht sehe...

[molily]

Hallo,

Zuerst redest Du vom Cache als assoziativem Array und dann behauptest Du, dieser Cache würde gefüllt mit dazwischenliegenden Dezimalzahlen, wenn nur die drei Zahlen benötigt werden???

Häh? Ich weiß gar nicht, warum du dich so echauffierst, Alexander hat genau erklärt, was ich meinte.

Wenn Du irgendein Array mit den Werten arr[0]=3.13000 und arr[1]=3.15999 hast füllt Javascript dazwischen drei Millionen Plätze aus ????

Das hat doch niemand gesagt. Ich kann einen Algorithmus haben, der mir soviele Zahlen in diesem Bereich liefert, aber durch geschickte Rundung kann ich einen Cache anlegen mit Ergebnissen für die Eingabewerte 3.13, 3.14 und 3.15 (als Beispiel).

Mathias

[ActiviT]

Du kannst im Prozessmonitor deines Betriebssystems sehen, wieviel Speicher die Browserinstanz gerade braucht und wie der Speicherverbrauch zu- und abnimmt beim Laden und Verlassen der Seite.

Klar, aber diese Werte sind zu ungenau, weil sie natürlich durch diverse andere Programme und den Kernel beeinflusst werden.

Nein, die Speicherdaten für den einen Prozess hängen nur von dem einen Prozess ab.

Die Speicherdaten schon, nicht aber die CPU Auslastung. Die kann ich ja nur durch Durchschnittswerte messen.

Mit 1000 Durchläufen, wäre das ganze sicherliche präziser, aber das manuell zu machen ist Wahnsinn.

Warum willst Du derartig große Datenmengen in Javascript herumschleppen? Ich befürchte, Du machst entweder etwas, was besser auf dem Server aufgehoben wäre, oder etwas, das besser mit Flash umgesetzt würde. Die "40 Millisekunden" sprechen für eine Animation.

Letzteres.

Nimm Flash, das ist dafür ausgelegt.

Nein, möchte ich nicht. Mit Flash wäre das ganze natürlich einfach, aber dann macht's ja keinen Spaß mehr. Außerdem ist Flash böse. Da würde ich schon eher Java nehmen. ;)

[molily]

Hallo,

Einen Cache? In welcher Form? Und wieso rundest du? Brauchen gerundete Werte mit weniger dezimalen Nachkommastellen auch weniger RAM?

Siehe Alexander, es geht darum,
a) Berechnungen zu vermeiden,
b) Ergebnisse zentral und nur einmal zu speichern, dann aus dem Cache zu holen anstatt sie an einzelnen Objekten zu speichern.

Ob das Sinn macht, kann man sagen, wenn man deine Berechnungen kennt. Wenn du mehrere Eingabewerte hast, ist das natürlich komplizierter, aber möglich.

Du hast jetzt natürlich übertrieben. Aber was ist bei 1000 oder 10000 Objekten? Dazu könnte es durchaus kommen.

10000 Number-Eigenschaften fallen kaum ins Gewicht. (Eine Zahl braucht in JavaScript immer 64 Bit, plus Overhead.)

10000 Objects mit einer zufälligen Number-Eigenschaft namens »zahl« gespeichert in einem Array führen in meinem Firefox/Linux so einem solchen Speicheranstieg:

sz,size,rsz,vsize
39,156,96,156

Das sind 39 Pages à 4096 Bytes = 156 KBytes. Das ist absolut vernachlässigbar.

Mit 1000 Durchläufen, wäre das ganze sicherliche präziser, aber das manuell zu machen ist Wahnsinn.

Warum musst du es manuell machen? Ich dachte, du hast schon das Spiel und damit realistische Testbedingungen?

Gibt es eine Möglichkeit das ganze zu automatisieren oder doch noch eine andere Möglichkeit, die Werte herauszufinden? (Ich denke da z.B. an eine FF Erweiterung, die den aktuellen RAM-Verbrauch nur von Javascript auslesen kann)

So eine Erweiterung gibts meines Wissens nicht. Du kannst dir höchstens die JavaScript-Engine des Firefox als Kommandozeilen-Programm kompilieren. Aber ich wüsste nicht, was das bringt. Das sind dann künstliche Testbedingungen. Teste einfach im Browser und schau dir den Speicherverbrauch des Prozesses an. Die verbrauchte Zeit verschiedener Umsetzungen misst du am besten in JavaScript selbst mit Date-Objekten.

Mathias

[Slyh]

Hallo,

Ich lege bei komplizierteren Berechnungen, bei denen es nur einen oder wenige Eingabewerte gibt, einen Cache an und runde dabei um einige Stellen, sodass der Cache klein bleibt, aber viele Anfragen schnell und ausreichend genau beantwortet werden können, ohne nochmal zu rechnen.

Rundest du die Eingabewerte (Keys) oder die Ausgabewerte (Values)? Aus deinem
Posting lese ich heraus, dass du die Ausgabewerte (Values) rundest, was IMHO
gar keinen Sinn ergibt. Daher wohl auch die Nachfrage von ActiviT.

Korrigier mich, wenn ich deine Aussage jetzt falsch präzisiere:

Wenn nur wenige Eingabewerte (<1000 oder so) existieren, kann man einen Cache
anlegen, in dem diese Eingabwerte UND die Ausgabwerte in voller Präzision
gespeichert werden.

Wenn viele mögliche Eingabewerte mit kleiner Abweichung und mit korrespondierender
kleiner Abweichung bei den Ausgabewerten existieren, kann man die Eingabewerte
auf x Nachkommastellen runden, weil dann ggf. nicht jede minimale Abweichung
im Nachkommabereich einen neuen Cache-Eintrag zur Folge hat.

Wenn man viele Eingabe/Ausgabewerte mit großen Abweichungen hat, sollte man
einen Cache mit brauchbarer Verdrängungsstrategie anwenden.

Gruß
Slyh

[molily]

Wenn viele mögliche Eingabewerte mit kleiner Abweichung und mit korrespondierender
kleiner Abweichung bei den Ausgabewerten existieren, kann man die Eingabewerte
auf x Nachkommastellen runden

Das meinte ich.

Mathias

[exadogg]

Hi Selfler!!

Angenommen ich habe eine Javascript Klasse. Nun muss ich für viele Instanzen dieser Klasse, alle 40 Millisekunden eine bestimmte Größe berechnen. Beispielsweise hat die Instanz die Attribute A1 und A2 und es muss folgendes berechnet werden:

pow( (A1 + A2), 2) - A1

Ich gehe mal davon aus, dass diese pow() die Potenz von einer Zahl berechnet, in diesem Fall wohl das Quadrat der Summe von A1 und A2. Nun weiß ich ja nicht, wie die Funktion Math.pow() von JavaScript intern gestrickt ist.

Aber wenn Du den Term (A1 + A2) ^ 2 mittels einer der binomischen Formeln erweiterst, kommst Du auf A1 * A1 + 2 * A1 * A2 + A2 * A2, was IMHO mit weniger Aufwand als die Math.pow() zu berechnen ist. Ich hoffe, Dir damit geholfen zu haben.

Da sich die Werte A1 und A2 sehr sehr selten ändern, ist zu überlegen, ob ich nicht den entsprechenden ausgerechneten Wert in einer weiteren Variable speichere. Nun stellt sich mir die Frage, wieviel RAM so eine Variable inkl. Overhead in Javascript verbraucht und ob sich das lohnt. Immerhin haben die meisten PCs heutzutage schon 1GB RAM und fast alle mindestens 512MB RAM.

PS: Falls ihr eine gute Möglichkeit kennt, um die Performance eines Javascripts zu messen (vermutlich braucht man ja sehr viele Durchläufe), bitte teilt sie mir mit.

Ich bin zur Zeit dabei, das Aptana Studio für Eclipse zu testen, und ich meine, dass es dort die Möglichkeit gibt, die Performance eines JavaScripts zu messen. Falls Du mal selbst nachschauen willst: Eclipse gibt es unter http://www.eclipse.org/ und das Aptana Studio dafür unter http://72.3.219.182/studio/download

PPS: Es kann ruhig ein großer Teil des restlichen Arbeitsspeichers benutzt werden. Das ganze ist für ein Spiel, weswegen es nicht schlimm ist, wenn der Arbeitsspeicher auch entsprechend gebraucht wird.

[ChrisB]

Hi,

pow( (A1 + A2), 2) - A1

Ich gehe mal davon aus, dass diese pow() die Potenz von einer Zahl berechnet, in diesem Fall wohl das Quadrat der Summe von A1 und A2. Nun weiß ich ja nicht, wie die Funktion Math.pow() von JavaScript intern gestrickt ist.

Aber wenn Du den Term (A1 + A2) ^ 2 mittels einer der binomischen Formeln erweiterst, kommst Du auf A1 * A1 + 2 * A1 * A2 + A2 * A2, was IMHO mit weniger Aufwand als die Math.pow() zu berechnen ist.

Etwas, was bereits nativ implementiert ist, durch "Herunterbrechen" in elementarere (Rechnen-)Operationen zu "vereinfachen", ist selten performanter, als eben den nativen Weg zu nutzen.
Sollte mich stark wundern, wenn sich das hier im konkreten Falle anders verhielte.

MfG ChrisB

[Gunnar Bittersmann]

@@ChrisB:

Aber wenn Du den Term (A1 + A2) ^ 2 mittels einer der binomischen Formeln erweiterst, kommst Du auf A1 * A1 + 2 * A1 * A2 + A2 * A2, was IMHO mit weniger Aufwand als die Math.pow() zu berechnen ist.

Etwas, was bereits nativ implementiert ist, durch "Herunterbrechen" in elementarere (Rechnen-)Operationen zu "vereinfachen", ist selten performanter, als eben den nativen Weg zu nutzen.
Sollte mich stark wundern, wenn sich das hier im konkreten Falle anders verhielte.

Das hieße, Math.pow() müsste mit etlichen Fallunterscheidungen implementiert sein.

Wenn es das nicht ist, dann wird es wohl für alle y nach [latex]x^y = \mathrm{e}^{\ln{x^y}} = \mathrm{e}^{y \ln x}[/latex] berechnet.*

Zumindest für y = 2 u.a. kleinen ganzzahligen y dürfte die Umschreibung als Multiplikation effizienter sein.

Live long and prosper,
Gunnar

* Oder geht es mit [latex]x^y = 2^{\operatorname{ld}{x^y}} = 2^{y \operatorname{ld} x}[/latex] im Dualsystem besser?

[KurtZ]

Hallo

Zumindest für y = 2 u.a. kleinen ganzzahligen y dürfte die Umschreibung als Multiplikation effizienter sein.

guter einwand, aber der Gewinn liegt bei mir selten über 20%

  
  
function bench(code) {  
  bench0="pow=Math.pow; start=Date.now(); for (i=0;i<max;i++) {";  
  bench1="}; end=Date.now();";  
  pow=Math.pow;  
  eval(bench0+code+bench1);  
  dif=end-start;  
  res.push( dif+"\t"+code+"\t->"+x );  
}  
  
document.writeln("<pre>");  
for (j=0;j<3;j++) {  
  a=129289;  
  max=10000;  
  res=[];  
  bench("x=a*a");  
  bench("x=Math.pow(a,2);");  
  bench("x=pow(a,2)");  
  document.writeln(res.join("\n")+"\n\n");  
}  

Bye
 Kurt

[KurtZ]

Hi

berechnest du zufällig Apfelmännchen? :)

die Vorschläge die du bekommen hast sind alle sehr gut, aber am Bechmarken kommst du nicht vorbei.

Rechenkomplexität mit Speicherkomplexität zu ersetzen lohnt sich heutzutage fast nur noch bei "relativ komplexen" Berechnungen die mit "relativ wenigen" Tabelleneinträgen auskommen, weil das Verhältnis zw. Prozessorleistung und RAM-Geschwindigkeit immer asymmetrischer wird.

M.a.W. wenn deine Tabellen incl. Code  in den Prozessorcache passen, hast du gute Performancegewinne.

ciao
 kurt

[Bio]

Sup!

Ich würde ja eher versuchen herauszubekommen, welche Instanzen überhaupt von Änderungen betroffen sein können ("Dirty-List"), und dann nur diese updaten.

Bio

[ActiviT]

Sup!

Ich würde ja eher versuchen herauszubekommen, welche Instanzen überhaupt von Änderungen betroffen sein können ("Dirty-List"), und dann nur diese updaten.

_Das_ wird sowieso schon gemacht. Aber trotzdem danke für den Tipp ;)