Optimierungsproblem

rapso

Mati schrieb:

vielleicht kann mir jemand helfen was ich optimieren könnte. In der regel sollte ich höchsten 1 sekunde brauchen glaub ich (zumindest schafft das gimp so )

4MB, passt also nicht in den cache, wenn du nun optimierst, musst du versuchen cachefreundlicher zu sein. zudem koenntest du die divisionen durch multiplikationen mit reziproken werten ersetzen und ein paar spezialisierte innerloops machen, die nicht diese if abfragen haben die zu 99% nie eintreffen.

Mati

ich danke für die Hilfe und Antworten...

musst du versuchen cachefreundlicher zu sein. zudem koenntest du die divisionen durch multiplikationen mit reziproken werten ersetzen und ein paar spezialisierte innerloops machen, die nicht diese if abfragen haben die zu 99% nie eintreffen.

leider merke ich dass hier mein wissenstand so noch net ausreicht...
interloops, Divisionsersetzung durch Multiplikation mit reziproken Werten...nie gehört.

danke - ich werde mal surfen was das so ist/bedeutet

David_pb

Mati schrieb:

ich danke für die Hilfe und Antworten...

musst du versuchen cachefreundlicher zu sein. zudem koenntest du die divisionen durch multiplikationen mit reziproken werten ersetzen und ein paar spezialisierte innerloops machen, die nicht diese if abfragen haben die zu 99% nie eintreffen.

leider merke ich dass hier mein wissenstand so noch net ausreicht...
interloops, Divisionsersetzung durch Multiplikation mit reziproken Werten...nie gehört.

danke - ich werde mal surfen was das so ist/bedeutet

Statt:

x = foo / bar;

einfach:

float invBar = 1.0f / bar;
x = foo * invBar;

grüße

hellihjb

- mach kernel[] integer und skalier' die eintraege so, dass "gauss_sum" eine 2er-potenz ist.
- mach aus der innersten (col) schleife insgesamt drei, so dass du in der ersten nur "if (inner_offset < 0)" pruefen musst, in der mittleren gar nichts und in der letzten nur "if (inner_offset >= width)"
- hat der std::vector irgendwelchen overhead beim zugriff? falls ja, einmal pro scanline einen int* auf den ersten pixel holen und den linear durchlaufen
- die gewichtung der pixel ist ideale anwendung fuer mmx

ChaosAngel

@letzte eben genannte Optimierung:
[edit]Vorletzte, die mit der Reziproken[/edit]
Entschuldigung wenn ich dies anzweifle, aber was sollte das bringen ?!?!?!?
Sollte der Compiler nicht selbständig so clever sein ?

PPS: Du hast die Frage mit dem Debug/Release Mode noch nicht beantwortet.

Ansonsten ist da imho ur etwas durch Speicherausnutzung herauszubekommen.

Probier mal statt nem Vector jede Zeile in einer std::list zu speichern.
ist vielleicht nicht ganz so schön anzusprechen, aber sollte dem Zugriffsmuster vielleicht besser entsprechen.

David_pb

ChaosAngel schrieb:

@letzte eben genannte Optimierung:
[edit]Vorletzte, die mit der Reziproken[/edit]
Entschuldigung wenn ich dies anzweifle, aber was sollte das bringen ?!?!?!?
Sollte der Compiler nicht selbständig so clever sein ?

PPS: Du hast die Frage mit dem Debug/Release Mode noch nicht beantwortet.

Ansonsten ist da imho ur etwas durch Speicherausnutzung herauszubekommen.

Probier mal statt nem Vector jede Zeile in einer std::list zu speichern.
ist vielleicht nicht ganz so schön anzusprechen, aber sollte dem Zugriffsmuster vielleicht besser entsprechen.

Ja das bringt was. Je mehr Divisionen du durch Multiplkationen ersetzten kannst desto flotter wirds.
Ich hab' das mal jemand vorgeschlagen, für eine Methode zum normalisieren eines 3 Komponenten Vektors. Die Methode war, laut seiner Angaben, bis zu 10x schneller als zuvor!

grüße

ChaosAngel

Das ist für mich keine Erklärung. Vielleicht wusste ja auch er nicht was der Release Mode ist
Also eine ordentliche Begründung mit Referenz oder auch ohne, aber warum ne Division schneller ist, und warum vor allem der Compiler soetwas nicht selber optimieren können sollte. Halte ich alles wie gesagt für sehr unwahrscheinlich.

rapso

ChaosAngel schrieb:

Halte ich alles wie gesagt für sehr unwahrscheinlich.

es gibt regeln an die sich compiler halten _muessen_ und das hat nichts mit wahrscheinlichkeit zu tun. eine davon ist, dass sie die division machen, wenn sie verlangt wird und die hardware das kann. das gleiche gilt fuer sinus statt einer taylor approximation, wurzel statt einer simplen lookuptable usw.
bei manchen compilern gibt es aber flags, damit sie nicht standard conform optimieren muessen.

ChaosAngel

Hmmm, ok ...
Und warum genau sind Multiplikationen dann schneller als Divisionen ?
Vorallem wenn man vorher noch ein Reziprokes berechnen muss, was ja dann 2 Rechenschritte sind, also auch noch eine Division.

Mati

Vielen lieben Dank wiedermal für die gute Vorschläge und die Beschreibungen.
Ich führe sie mir alle gerade zu Gemüte..
Ich hätte da noch ne Frage. Bei mir ist der kernel der ein std::vector<float> ist eine member Variable also global in der KLasse.
Wäre es schneller wenn ich den kernel immer von Methode zu methode durchschleife also immer übergebe? Sorry wenn die Frage dumm ist aber könnte es nicht sein dass der Zugriff auf globale Variablen langsamer ist? Ich greife ja doch recht häufig auf den vector zu.

Danke euch

Jester

ChaosAngel schrieb:

Hmmm, ok ...
Und warum genau sind Multiplikationen dann schneller als Divisionen ?
Vorallem wenn man vorher noch ein Reziprokes berechnen muss, was ja dann 2 Rechenschritte sind, also auch noch eine Division.

Multiplikationen sind einfacher als Divisionen: Einfach shift&add. Das sind beides recht flotte Aktionen. Daß sie schneller sind ist Fakt. Schau in die Dokumentation eines nahezu beliebigen Prozessors.

Klar, das Berechnen des Reziproken kostet Dich eine Division. Wenn Du aber danach mehrfach durch diesen Wert teilst, dann kannst Du jedes Mal ne Division durch ne Multiplikation ersetzen. Damit sparst Du jedes Mal die Laufzeit-Differenz zwischen Multiplikation und Division. Sobald diese Ersparnisse über die Kosten einer einzelnen Division wachsen gewinnst Du mit der Variante.

Mati

- mach kernel[] integer und skalier' die eintraege so, dass "gauss_sum" eine 2er-potenz ist.
- mach aus der innersten (col) schleife insgesamt drei, so dass du in der ersten nur "if (inner_offset < 0)" pruefen musst, in der mittleren gar nichts und in der letzten nur "if (inner_offset >= width)"
- hat der std::vector irgendwelchen overhead beim zugriff? falls ja, einmal pro scanline einen int* auf den ersten pixel holen und den linear durchlaufen

was meinst du mit aus der innersten drei schleifen machen? würde sich der aufwand damit nicht erhöhen? oder meintest du drei if abfragen und in jeder if abfrage eine schleife ?

die skalierung der einträge so dass die summe eine 2er Potenz ist - noch bin ich nicht drauf gekommen wie ich das hinbiegen soll da bei mir die einträge immer zwischen 0 und 1 liegen

ChaosAngel

Vielen lieben Dank wiedermal für die gute Vorschläge und die Beschreibungen.
Ich führe sie mir alle gerade zu Gemüte..
Ich hätte da noch ne Frage. Bei mir ist der kernel der ein std::vector<float> ist eine member Variable also global in der KLasse.
Wäre es schneller wenn ich den kernel immer von Methode zu methode durchschleife also immer übergebe? Sorry wenn die Frage dumm ist aber könnte es nicht sein dass der Zugriff auf globale Variablen langsamer ist? Ich greife ja doch recht häufig auf den vector zu.

Danke euch

Nein, das ist egal.

@Jester

Vielen Dank für die Erklärung, war tatsächlich etwas was ich noch nicht wusste. Mich erstaunt wirklich nur das der Compiler das nicht optimieren darf. Soweit ich weiss muss er doch nur den Regeln der Sprache folgen(return Wert optimierung etc...) und nach aussen hin muss das erwartete Verhalten stattfinden. Und da eine Division/Multiplikation keine Randeffekte hat sollte er es doch optimieren dürfen.

Jester

Bist Du sicher, daß *(1/x) bei Fließkommazahlen *immer* das gleiche liefert, wie /x? Sollte dem nicht so sein (was ich mir gut vorstellen kann), würde der Compiler damit das Ergebnis unter Umständen verändern. Wenn Du jetzt sorgfältig Deinen Code so schreibst, daß die Rundungsfehler minimal bleiben, wäre es ganz schön ärgerlich, wenn dem Compiler das egal sein dürfte.

ChaosAngel

Da ist was wahres dran. Überzeugt.
War einfach nur überrascht das ich diese Optimierungsmöglichkeit noch nicht kannte.

Und um auf das ursprüngliche Problem zurückzukommen: Hast du es inzwischen mit einem anderen Speicherlayout versucht ?

hellihjb

was meinst du mit aus der innersten drei schleifen machen?
würde sich der aufwand damit nicht erhöhen?

nein, denn hier...

for(int col = 0; col < cols; col++)
{
  inner_offset = line_offset + col;
  if((inner_offset < 0) || (inner_offset >= width)) continue;
  // ...
}

...pruefst du fuer jeden pixel ob er rechts oder links ausserhalb des bildes liegt.
es liegen, entsprechend des filter-kernels, aber auf jeder seite nur n pixel ausserhalb des bildes.
fuer alle "mittleren" pixel ist diese ueberpruefung unnoetig.
- das erspart dir width*height*col (also bei deinem 1000x1000 bild: mehrere millionen!) bedingte spruenge.

die skalierung der einträge so dass die summe eine 2er Potenz ist
noch bin ich nicht drauf gekommen wie ich das hinbiegen soll

du berechnest diese summe ja sowieso jedes mal, obwohl die - jedenfalls fuer den fall wo keine pixel ausserhalb adressiert wuerden - sowieso konstant ist.
du koenntest also diese summe im vorfeld berechnen und die eintraege im kernel[] dann einfach so skalieren, dass die summe zb 2^16 ist (indem du einfach alle eintraege in kernel[] mit 2^16/summe multiplizierst). dadurch koennte kernel[] integer sein, wodurch du ueberhaupt keine floating-point berechnung mehr durchfuehren braeuchtest. das erspart dir am ende den cast von float zu integer und die division faellt komplett raus und kann durch einen einfachen shift ersetzt werden (integer-divison durch 2er-potenz).