Sollte man Optimierung für bestimmte seltene Fälle einbauen?

[uhsuhz]

Also folgende Frage stellt sich:

Ich bin dabei eine Klasse zu schreiben in Java um mit allen möglichen Basen zu rechnen, jetzt bin beim optimieren und ich frage mich ob es jetzt Sinn gibt für die Spezialfälle Zero One und -One zu optimieren?

Für dieses drei Fälle kann man den rechenweg erheblich verkürzen, doch sollte der Fall nicht eintreffen muss jedere andere Rechnung mehrere if Schleifen mit equals-Methodenaufrufen aufrufen, die wiederum zeit brauchen.

Was glaubt ihr? Für alle Fälle gleiche Rechenzeit oder optimieren?

Oder gibt es sonst welche Techniken um das anders zu machen?

mfg
uhsuhz

[raps]

premature optimizations == root of evil

implementiere
profile
optimiere

alles andere ist nicht deterministisches kristalkugellesen.

[hustbaer]

Für alle Fälle gleiche Rechenzeit oder optimieren?

Das hängt wohl stark davon ab wie oft diese Spezialfälle vorkommen, und natürlich wie teuer die "gesparten" Berechnungen im Vergleich zu den nötigen Tests ("ifs") sind. Das weiss man entweder sowieso, oder man erfährt es durch den Profiler.

[tfa]

Du sagst selbst, die Fälle sind selten. Also lass es lieber bleiben. Optimiert wird nur, wenn du wirklich ein Performance-Problem hast, und das scheint nicht der Fall zu sein, oder?

[EXDW]

warum die normale arbeit durch ein selten auftretenden spezial fall ausbremsen
also nein - es sei denn man kann es optimieren ohne die normalen faelle zu beeinflussen

[volkard]

tfa schrieb:

Optimiert wird nur, wenn du wirklich ein Performance-Problem hast, und das scheint nicht der Fall zu sein, oder?

Ihr Schnapsnasen! Natürlich macht man sich von Anfang an Gedanken darüber. Will man solcherlei Art der Optimierung erlauben, kommt ein ganz anderes Klassengerüset heraus (und keine if-Schleifen).
Und hier ist die Überlegung auch so einfach, daß man das tatsächlich ohne Profiler schafft, wie tfa und Mr Evil beweisen. Der Profiler mag Euch zwar das Nachdenken abnehmen können, aber doch erst im Nachheinein, wenns schon zu spät ist, wenn für eine tiefgreifende Optimierung alles umgeschubst werden muß.

Bleibt nur noch zu fragen, wann und wo und warum man die Optimierungen für Zero, One und MinusOne sieht. Ach ja, bei Langzahlarithmetik. Klar, wenn man bei 100000000 Ziffern eine ganze Rechnung spart, ist die Einsparung so groß, daß man das bereits bei einer wahrscheinlichkeit von eins zu einer Million versucht.

[Registrierter Troll]

volkard schrieb:

Natürlich macht man sich von Anfang an Gedanken darüber.

Würde ich auch sagen. Wenn man allerdings noch in dem Stadium ist, in dem man "if-Schleifen" für korrekt hält, sollte man sich vielleicht lieber auf das wesentliche konzentrieren, statt seine Zeit mit dem Nachdenken über mögliche Optimierungen zu vergeuden.

[rapso]

Mr Evil schrieb:

warum die normale arbeit durch ein selten auftretenden spezial fall ausbremsen
also nein - es sei denn man kann es optimieren ohne die normalen faelle zu beeinflussen

warum nimmst du an die if abfrage wuerde irgendwas ausbremsen? woher weisst du dass diese cpu units ohne die if abfrage nicht einfach brach liegen?

[rapso]

da darueber zu streiten genau so sinnlos ist wie ohne profiling zu optimieren (meine meinung), hab ich euch mal ein sample zusammengestrickt

int Foo(int x)
{
	const int X=x;
	x*=x;
	x*=x;
	x*=x;
	x*=x;
	if(X==~0)
		return 2;
	x*=x;
	x*=x;
	x*=x;
	x*=x;
	return x;
}

#include <Windows.h>
#pragma comment ( lib, "winmm.lib" )

int Foo(int);
int main(int argc,char* argv[])
{
	const int Loops = 1000000000;
	int x=1;
	int T0 = timeGetTime();
	for(int a=0;a<Loops;a++)
		x	=	Foo(x);
	int T1 = timeGetTime();
	printf("%dms %d\n",T1-T0,x%4);
	return 0;
}

beide teile mussen in verschiedene translation units um jegliche compiler inlining optimierungen die das ergaebniss verfaelschen koennten auszuschliessen.

der auskommentierte teil ist die simulierte if abfrage, diese schlaegt NIE an, sie ist also eigentlich nur verlust.

bei mir:
ohne: 12030ms
mit: 12010ms

die ergebnisse unterscheiden sich, bis auf kleines rauschen, nicht.

[hustbaer]

volkard schrieb:

Bleibt nur noch zu fragen, wann und wo und warum man die Optimierungen für Zero, One und MinusOne sieht. Ach ja, bei Langzahlarithmetik. Klar, wenn man bei 100000000 Ziffern eine ganze Rechnung spart, ist die Einsparung so groß, daß man das bereits bei einer wahrscheinlichkeit von eins zu einer Million versucht.

Bei einer Wahrscheinlichkeit von 1 zu 1 Mio. ist die Erreichbare Verbesserung immer irrelevant, da sie im Bereich von 1 zu 1 Mio liegt. Ganz egal wie lange eine Operation braucht. Bei einer Laufzeit von 1 Mio stunden interessiert es micht überhaupt nicht ob eine Stunde gespaart wurde oder nicht.

Bei Langzahlarithmetik würde ich aber ohne auch nur darüber nachzudenken solche Optimierungen einbauen. Weils halt irgendwie Sinn macht. Und weil Null, Eins und minus Eins ja nicht wirklich seltene Zahlen sein müssen.

[volkard]

hustbaer schrieb:

Bei einer Wahrscheinlichkeit von 1 zu 1 Mio. ist die Erreichbare Verbesserung immer irrelevant, da sie im Bereich von 1 zu 1 Mio liegt. Ganz egal wie lange eine Operation braucht. Bei einer Laufzeit von 1 Mio stunden interessiert es micht überhaupt nicht ob eine Stunde gespaart wurde oder nicht.

aber ein if kostet nur eine million stel sekunde. und bei einer lauf zeit von einer oder einer million sekunden, also einer sekunde oder 12 tagen bist du sicherlich interessiert.
ist die mathe matik dir denn völlig fremd?

[witte]

volkard schrieb:

aber ein if kostet nur eine million stel sekunde.

Was hast Du denn für eine CPU? 1MHz?

[antwort]

Hängt davon ab wie lang eine stel-sekunde ist.

[hustbaer]

volkard schrieb:

hustbaer schrieb:

Bei einer Wahrscheinlichkeit von 1 zu 1 Mio. ist die Erreichbare Verbesserung immer irrelevant, da sie im Bereich von 1 zu 1 Mio liegt. Ganz egal wie lange eine Operation braucht. Bei einer Laufzeit von 1 Mio stunden interessiert es micht überhaupt nicht ob eine Stunde gespaart wurde oder nicht.

aber ein if kostet nur eine million stel sekunde. und bei einer lauf zeit von einer oder einer million sekunden, also einer sekunde oder 12 tagen bist du sicherlich interessiert.
ist die mathe matik dir denn völlig fremd?

Was ist denn jetzt kaputt?
Du schreibst von einer Wahrscheinlichkeit von 1 zu 1 Mio. Und sogar wenn ich mir 1% aller Rechnungen spare komme ich nicht von 1 Mio Sekunden auf eine Sekunde runter. Ist DIR Mathematik denn komplett fremd?

[if-schleife.de]

mehrere if Schleifen mit equals-Methodenaufrufen aufrufen, die wiederum zeit brauchen.

http://www.if-schleife.de

[+fricky]

if-schleife.de schrieb:

mehrere if Schleifen mit equals-Methodenaufrufen aufrufen, die wiederum zeit brauchen.

http://www.if-schleife.de

void if_schleife (int n)
{
  if (n)
    if_schleife (n-1);
  printf ("%d\n", n);
}

int main (void)
{
  if_schleife (10);
}

^^ich weiss, ist alt.

[Kenner des opas]

+fricky schrieb:

if-schleife.de schrieb:

mehrere if Schleifen mit equals-Methodenaufrufen aufrufen, die wiederum zeit brauchen.

http://www.if-schleife.de

void if_schleife (int n)
{
  if (n)
    if_schleife (n-1);
  printf ("%d\n", n);
}

int main (void)
{
  if_schleife (10);
}

^^ich weiss, ist alt.

nicht so alt wie dein Bart :p

[volkard]

hustbaer schrieb:

Was ist denn jetzt kaputt?
Du schreibst von einer Wahrscheinlichkeit von 1 zu 1 Mio. Und sogar wenn ich mir 1% aller Rechnungen spare komme ich nicht von 1 Mio Sekunden auf eine Sekunde runter. Ist DIR Mathematik denn komplett fremd?

^
du sparst dir EINMAL von einer million die teure rechnung, die millionenmal teurer als ein if ist und zahlst dafür jedesmal ein if mehr.

[hustbaer]

volkard schrieb:

hustbaer schrieb:

Was ist denn jetzt kaputt?
Du schreibst von einer Wahrscheinlichkeit von 1 zu 1 Mio. Und sogar wenn ich mir 1% aller Rechnungen spare komme ich nicht von 1 Mio Sekunden auf eine Sekunde runter. Ist DIR Mathematik denn komplett fremd?

^
du sparst dir EINMAL von einer million die teure rechnung, die millionenmal teurer als ein if ist und zahlst dafür jedesmal ein if mehr.

Ja verstehe ich schon.
Die Gesamtlaufzeit des Programms ändert sich dadurch aber nicht wesentlich.

Ich hab' ja bereits geschrieben dass ich es in dem Fall sicher auch machen würde. Weil es eben vermutlich Fälle gibt wo sehr oft 0, 1 oder -1 vorkommt. Und natürlich auch weil der Test so billig ist. Grundsätzlich bleibe ich aber dabei: eine Optimierung die mir eine Verbesserung um ein Millionstel bringt ist witzlos. Egal wie gross dieses Millionstel ist.

[volkard]

hustbaer schrieb:

Grundsätzlich bleibe ich aber dabei: eine Optimierung die mir eine Verbesserung um ein Millionstel bringt ist witzlos. Egal wie gross dieses Millionstel ist.

ja. jetzt verstehe ich dich.

unabhängig davon, daß du recht hast: "grundsätzlich" würde ich wie immer nicht sagen. es war ja nur eine wahrscheinlichkeit. für mich selber würde ich diese optimierung auch bei langzahlen weglassen. als bibliotheksentwickler würde ich auf die zielgruppe schauen müssen und sie im zweifelsfall unter umständen vielleicht gegen meine überzeugungen eher einbauen, weil sie mit optimierung unmerklich langsamer wird aber bei den nasen, die andauernd mit 0 oder 1 multiplizieren, statt sich vorher gedanken zu machen, satt was bringt.

[knivil]

Bei einer Wahrscheinlichkeit von 1 zu 1 Mio.

Das ist 'ne Art running gag bei Terry Pratchett. Wenn diese Chance exakt ist, dann wuerde ich auf alle Faelle optimieren.