C/C++ Performance Probleme bei Bildumwandlung: RGB zu Grau

[kuddlmuddl]

Hi Leute,
ich habe ein Performance-Problem und brauche mal Tipps von euch Profi-Bitschubsern

Mein Ziel ist ganz einfach: Ich will möglichst schnell ein RGB Bild in ein Graubild umrechnen. Allerdings soll die Gewichtung der drei Farbkanäle wählbar sein. (8bit je Farbkanal und 8bit im Ziel-Grauwertbild)

Mein Code für einen Pixel sieht in etwa so aus:

char inline rgb_to_grey_pixel(int pixel, // rgb des Farbbilds steckt hier drin
                              int r_gewicht, int g_gewicht, int b_gewicht)
{
  char r = 0xff &  pixel;
  char g = 0xff & (pixel >> 8);
  char b = 0xff & (pixel >> 16);

  int new_grey_value = r * r_gewicht +
                       g * g_gewicht +
                       b * b_gewicht;

  if (new_grey_value < 0) return 0;
  else
  {
    new_grey_value >>= 1;
    if (new_grey_value > 255) return 255;
  }

  return (char)new_grey_value;
}

Die Gewichte haben Werte zwischen -9 und 9, sollen aber nicht so stark wirken. Daher der bitshift vor den ifs.

Der Code braucht ziemlich genau 5ms für 1mio Pixel was für meine Anwendung leider deutlich zu langsam ist.

Was ich bereits getestet habe ist eine Look-Up-Table für die Multiplikationen. Die hab ich als Member der Klasse deklariert und im Konstruktor des Farbumrechners initialisiert. Es gibt ja nur 256 Werte je Farbkanal und 19 verschiedene Gewichte. Ich hab also ein Array precalc_werte[256][19] benutzt und dann nur dort ausgelesen in der Form:

  int new_grey_value = precalc_werte[r][r_gewicht] +
                       precalc_werte[g][g_gewicht] +
                       precalc_werte[b][b_gewicht];

Ich habs hier jetzt etwas vereinfacht dargestellt denn natürlich darf man die (evtl negativen) Gewichte nicht als Array-Index verwenden. Ich hab dafür einfach den Wertebereich um 9 verschoben damit der Zugriff klappt. Bei 0 bis 8 standen dann also die Werte für <0 in der Tabelle. Hat funktioniert, nur:
Leider ist die Laufzeit dadurch nicht besser sondern sogar leicht schlechter geworden. Ich habs mir damit begründet, dass der Zugriff auf RAM/Heap (über langsamer als cpu getakteten bus?) länger dauert als mal eben 3 Multiplikationen zu rechnen.

Jetzt also die Frage:
- Seht ihr noch irgendeine Möglichkeit den Code zu optimieren?

[MaTT90]

Hallo,
hast du mal versucht das ganze über mehr Threads laufen zu lassen?

Mfg

MaTT

[kuddlmuddl]

Naja da wirds ohne Probleme linear skalieren wenn ich jedem Core ne Bildhälfte zuweise aber leider erhalte ich für mein Programm nur einen einzigen Kern. Die Systeme haben maximal Dual-Cores und wenn, dann ist der andere Kern bereits vergeben. GPGPU/CUDA/OpenCL ist auch keine Option da onboard-graka.

[DaZpoon]

schau mal im assembly des codes nach ob der compiler schon MMX Befehle (ffmul ...) verwendet. wenn nicht kannst du dort versuchen den compiler zu konfigurieren oder selbst codieren.

http://www.codeproject.com/Articles/...MX-Programming

[MaTT90]

Was mir noch einfällt. Deklariere die Variablen mal auserhalb der Funktion! Dadurch wird nicht jedes mal die Variable erzeugt und zerstört.. Kann natürlich auch nichts bringen wenn es der compiler schon optimiert.

Mfg MaTT

[kuddlmuddl]

Ja vielen Dank für die beiden Tipps!

Deklariere die Variablen mal auserhalb der Funktion

Ich hatte eh vor mal die inline-Funktion abzuschaffen und den Code direkt in die for-y und for-x Schleife zu packen. Da werde ich das gleich mit probieren.

ob der compiler schon MMX Befehle (ffmul ...)

Das ist auch ne sehr gute Idee. Bei uns sind eigtl. alle Architektur-spezifischen Optimierungen deaktiviert da eine sehr große Vielfalt von Hardware unterstützt werden muss. Das älteste ist allerdings nen Pentium 4 der ja auch schon MMX kann. Damit werde ich mal rumexperimentieren!
Außerdem seh ich gerad, dass nur -O2 gesetzt ist und kein -O3

[the_nobs]

multiplikation ist sicherlich schneller als lookup im ram
vor allem wenn du über die Cachegrössen der CPU hinauskommst.
auch könntest du die Gewichtung vielleicht vorher anpassen damit du dir die Overflow/Underflow abfragen ersparen könntest.

Schneller wird es nur wenn du SSE oder ähnliche libs verwendest
bzw. nimm den Intel Compilier, der sollte sowas recht gut optimieren können
http://software.intel.com/en-us/arti...tel-compilers/

[DaZpoon]

da es inline ist landet es eigentlich nicht nochmal extra auf dem stack.
du könntest mal probieren ob es noch was bringt die ersten drei shiftoperationen zu ersetzen durch adressierung. dazu den int pixel auf ein char[] casten und dann per index 0-2 direkt zugreifen. dass der code so lahm ist liegt mit sicherheit auch an den if's, da die branch prediction des prozessors hier nicht gut genug arbeiten kann und es so zu jeder menge pipeline stalls kommt.

[kuddlmuddl]

auch könntest du die Gewichtung vielleicht vorher anpassen damit du dir die Overflow/Underflow abfragen ersparen könntest.

Leider soll es möglich sein das Bild "zu überstrahlen" bzw komplett schwarz zu mischen. Dafür muss es möglich sein Gewichte zu wählen die quasi über 255 hinauskommen. Somit komm ich um die Abfrage kaum drumrum :-/
Der Intel-Compiler ist wahrscheinlich auch keine Option. Ich bin auf einen uralten gcc 2.95.3 festgelegt.. könnte sogar sein, dass der mmx noch garnicht kann :-X

die ersten drei shiftoperationen zu ersetzen durch adressierung. dazu den int pixel auf ein char[] casten und dann per index 0-2 direkt zugreifen

Das teste ich auch mal sobald wie möglich, danke dir

Die ifs sind auf jeden Fall eine merkbare Performance-Bremse aber ich komme kaum drumrum.

_______________________________________________________

Ich hab mir nochmal über den Look-Up Gedanken gemacht:
Ein anderer Ansatz den ich zur Zeit durchdenke ist eine riesige Look-Up-Table die alle ifs/else/bitshifts/Plus/Mal überflüssig macht. Allerdings wirds da etwas komplizierter...

Speichere ich in einer einzigen riesigen Tabelle für alle möglichen Kombinationen von r, r_gewicht, g,g_gewicht, b, b_gewicht brauche ich etwas der Form

char [256][19][256][19][256[19]

Was leider 256^3*19^3 byte und somit ~107GB entspricht.
Es ist durchaus denkbar die Skala der Gewichte zu vergröbern. Dh statt 19 (-9 bis 9 inkl der 0) nur 7 Gewichte zu erlauben. (-2 bis 4 oder so)
Allerdings bin ich dann auch bei viel zu großen Werten. Die Software muss auf Systemen mit 1GB RAM laufen.
Für 7: 256^3*6^3 byte = 5488MB
Für 6: 256^3*6^3 byte = 3456MB
Für 5: 2000MB
Für 4: 1024MB
Für 3: 432MB
Erst für 3 ergibt sich also ein denkbarer wert aber 3 ist leider viel zu wenig.

Nun ist es ja aber natürlich so, dass ich hier sehr viel redundant speichere.
Für einen Pixel mit r=g=b=100 ergibt sich ja für die Parameter r_gewicht, g_gewicht, b_gewicht mit den Werten (123) das selbe, als wenn die Gewichte eine andere Reihenfolge hätten. (213, 231, 132, 312, 321)
Dh was ich hier als Look-Up mache ist
Variation mit Zurücklegen
http://de.wikipedia.org/wiki/Abz%C3%...r.C3.BCcklegen

Es reicht aber
Kombination mit Zurücklegen
http://de.wikipedia.org/wiki/Abz%C3%...8Repetition.29

Wenn ich also nicht 19^3 sondern nur (19 über 3), also den Binomialkoeffizienten, errechne ergibt sich für den nötigen Speicherplatz:
Für 7: 256^3 * (7 über 3) = 560MB
Für 6: 320MB

Dh ich müsste die Parameter sortieren, oder? So müsste ich ja die Reihenfolge-Redundanz wegbekommen und könnte also die Look-Up-Table entsprechend verkleinern, oder?
Der große Vorteil wäre auch, dass das Sortieren der Gewichte nur ein einziges mal nötig ist und natürlich nicht Pixelweise passieren muss. Allerdings ist diese ganze Farbumrechnung nur ein winziger Teil des Programms und ich würde ungern dafür 300MB Ram verbrauchen.

[the_nobs]

Leider soll es möglich sein das Bild "zu überstrahlen" bzw komplett schwarz zu mischen. Dafür muss es möglich sein Gewichte zu wählen die quasi über 255 hinauskommen. Somit komm ich um die Abfrage kaum drumrum :-/

kannst du vielleicht es ändern das Gewicht von 9 -> überstrahlen bedeutet?
d.h. du machst am Anfang ein IF weight >= 9 return Black..

Der Intel-Compiler ist wahrscheinlich auch keine Option. Ich bin auf einen uralten gcc 2.95.3 festgelet.. könnte sogar sein, dass der mmx noch garnicht kann :-X

Naja ab P4 gibts SSE
da sollste im Internet beispiele finden wie es zu benutzen ist
musst halt Inline Assembler basteln..

Sehe eher nicht wie du den algorithmus verbessern kannst.
probier eher mal ein Stück zurückzugehen, vielleicht findest du eine ebene oberhalb eine möglichkeit die Anzahl der bilder zu reduzieren..
(duplikate finden, vorfiltern, falls keine gewichte angegeben eine eigene methode zu nehmen die nur Farb ->grauumwandlung macht, also ohne if)

[antred]

Hast du mal nachgeschaut, ob der Compiler die Funktion auch wirklich inline gemacht hat?

[Hancock]

bevor du dir Gedanken über Look-Up-Tabellen machst, schau erst mal, wie viele Rechenoperationen dein Programm pro Pixel überhaupt braucht:
3 MUL //nicht vermeidbar
2 ADD //auch nicht vermeidbar
1 BITSHIFT
2 CMP //wenn die Branch prediction fehlschlägt, kostet das viel
Was wohl reinziehen wird, sind die CMP, ich würde mal sowas versuchen:

grey=grey<0?0:grey;
grey=grey>255?255:grey>>1;
return grey;

Grund: Der Pentium 4 hat net lange Pipeline und wenn das zu nem cmov wird, dann gibts vielleicht keinen Pipline-Stall.

Ach ja: Und guck mal, wie du die Funktion aufrufst, du solltest sie linear aufrufen, also wenn den Bild Zeilwenweise im Speicher liegt, dann würde ein spaltenweises Abtasten nur jedes Mal nen Cache-Miss erzeugen.

BTW: Mich würde das Disassembly auch interessieren.

[convexus]

inline - Funktionen die tatsächlich ge-inline'd werden, sind am ehesten als "static inline" oder als Funktor definiert. Am besten mal ausprobieren. Was sich zusätzlich lohnen könnte, ist die max- und min-Funktionen ohne Verzweigung.

r = y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // min(x, y)
r = x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1))); // max(x, y)

Die Art des Speicherzugriff (Anmerkung von Blitzmerker) ist entscheidend für die Effizienz. Aufeinanderfolgender Zugriff stellt gute Cache-Ausnutzung sicher.

[kuddlmuddl]

Leider hat bisher alles nix gebracht:
- O3 statt O2
- statt inline den code-pro-pixel direkt in die for y for x
- chat statt int für die r,g,b variablen
- deklaration außerhalb der for y for x

du könntest mal probieren ob es noch was bringt die ersten drei shiftoperationen zu ersetzen durch adressierung. dazu den int pixel auf ein char[] casten und dann per index 0-2 direkt zugreifen

wie ginge das? kann man auf ein array casten? Ich dachte das is in c/c++ kein typ sondern nur n pointer aufs erste element

mmx/sse kann ich hier garnich testen da wir nur für x486 als zielplattform kompilieren .. neuerere hardware features fallen damit wohl weg :-/

kannst du vielleicht es ändern das Gewicht von 9 -> überstrahlen bedeutet?
d.h. du machst am Anfang ein IF weight >= 9 return Black..

vorher anhand der gewichte erkennen obs direkt schwarz/weiß wird geht leider auch nicht. es soll wirklich möglich sein additiv und subtraktiv die farbanteile zu mischen. dadurch werden evtl große Teile des Bildes schwarz/weiß aber es kann gut sein dass eben gerade die interessanten dadurch möglichst kontrastreich werden.

probier eher mal ein Stück zurückzugehen, vielleicht findest du eine ebene oberhalb eine möglichkeit die Anzahl der bilder zu reduzieren..

das is leider keine option :-/

@Blitzmerker und @convexus
Die beiden Sachen probier ich nachher mal wenn ich Zeit habe

danke schonmal an alle.. ich fürchte um den beschriebenen speicherplatz-optimierten lookup komm ich nicht herum

[antred]

wie ginge das? kann man auf ein array casten? Ich dachte das is in c/c++ kein typ sondern nur n pointer aufs erste element

int pixel = ...
char* const asSequenceOfChars = reinterpret_cast < char* > ( &pixel );
asSequenceOfChars [ 0 ] = ...
asSequenceOfChars [ 1 ] = ...

[Fortatus]

Schon probiert 1. die Gewichtung als Array zu übergeben (ein bisschen aufgeräumter) und 2. die Variablen und Ergebnis per Referenz zu übergeben? Wenn du die Variablen einfach so übergibst braucht er bei jedem Aufruf 4 Kopieroperationen und kopiert das Ergebnis zurück. Bei Zeigern/Referenzen werden die Variablen nicht erst kopiert und du hast weniger Overhead.
Bin mir nicht sicher, ob das bei Inline-Funktionen zieht oder ob er da die Copy-Operation dann direkt weg optimiert.

P.S.: Hast du mal ohne Inline getestet? Kann auch kontraproduktiv sein... http://www.parashift.com/c++-faq-lit...s.html#faq-9.3

[antred]

Schon probiert [...] und 2. die Variablen per Zeiger zu übergeben? Wenn du die Variablen einfach so übergibst braucht er bei jedem Aufruf 4 Kopieroperationen und kopiert das Ergebnis zurück. Bei Zeigern werden die Variablen nicht erst kopiert und du hast weniger Overhead.

Ob du nun 4 Integer-Parameter oder 4 Interger-Zeiger-Parameter kopieren mußt ... da hast du ja wohl nichts gewonnen. Im Gegenteil, je nach System können Zeiger sogar breiter sein als Integers. Dazu kommt noch, daß du dann immer erst die Zeiger dereferenzieren mußt, was sich eher negativ auf die Performance auswirken würde.

[Fortatus]

Stimmt natürlich auch. ^^ Wenn er aus den 3 Gewichtsparametern ein Array bzw. Vector macht, liegt man immerhin bei 2 Referenzen VS. 4 Kopien. Ansonsten zugegebenermaßen weniger sinnvoll.

Wenn du die Pixel in einer Liste hast, probier' auch mal Vector aus. Ab einigen tausend Elementen ist Vector in C++ schneller.

Ansonsten weißt du nun, warum Grafikkarten massiv auf Parallelisierung setzen. Eigentlich wäre das auch eher der Job für einen Shader. Sofern die Onboardgrafik also einen aktuellen Treiber hat, könntest du vllt. über OpenGL nachdenken...

[e-Laurin]

Viel kann man hier leider nicht mehr herausholen. Es gibt eine Grenze, wie weit man etwas optimieren kann. Und da SIMD-Krams wie MMX und SSE nicht erlaubt sind, ist die Grenze schon erreicht.

Es bleiben zwei Möglichkeiten:
1. Die Geschwindigkeit so akzeptieren, wie sie ist. Mehr als ein paar Prozente wird man mit den genannten Einschränkungen nicht mehr herausholen können.
2. Die Voraussetzungen ändern. MMX sollte das mindeste sein. 486er-like Computer werden heute eigentlich nicht mehr eingesetzt. Die Ära ist schon vor über 15 Jahren zu Ende gegangen.

[WhiteLionATX]

blupblup blup....

das sollte helfen (inline asm snippet was ich in autoit benutzt habe):

Func _graustufen()
_("use32") ;sollte immer eingesetzt werden!

_("mov esi," & $Scan) ;Startadresse Bitmapdaten (Pixel)
_("mov ecx," & $iWidth * $iHeight) ;anzahl Pixel
_("mov edi,21845") ;konstante, *21845/2^16 ist ungefähr 1/3

_("_schleife:") ;so lange, bis ecx=0
_("mov edx,[esi]") ;pixel laden AARRGGBB (RR+GG+BB)/3 =farbe graustufe
_("mov al,dl") ;lowbyte (BB) vom Pixel nach lowbyte al
_("movzx bx,dh") ;highbyte (GG) vom Pixel nach lowbyte von bx (bh ist 0)
_("shr edx,8") ;RR ins dh schieben
_("add ax,bx") ;BB + GG
_("movzx bx,dh") ;highbyte (RR) vom Pixel nach lowbyte von bx (bh ist 0)
_("add ax,bx") ;und dazuzählen dx=RR+GG+BB
_("imul edi") ;*21845 *21845/2^16 ist ungefähr 1/3
_("shr eax,16") ;/2^16 in al steht nun der farbcode (grauton) für RR, GG und BB
_("movzx dx,al") ;grauton nach dl, in dh steht 0
_("shl edx,16") ;grauton nach RR, in AA steht 0!
_("mov dh,al") ;grauton nach GG
_("mov dl,al") ;grauton nach BB In edx steht nun 00alalal=grauton
_("mov [esi],edx") ;pixel schreiben

_("add esi,4") ;3x4
_("sub ecx,1") ;3 pixel pro schleifendurchgang
_("ja _schleife") ;so lange, bis ecx=0
;wesentlich schneller als _("loop _schleife") ;so lange, bis ecx=0
_("mov [" & $ASM_VAR_pointer1 & "],esi") ;Register in Variable schreiben
_("mov [" & $ASM_VAR_pointer2 & "],edx") ;Register in Variable schreiben
_("ret ")
EndFunc ;==>_graustufen

zurechtschnippseln kannst du es von alleine , hoffe ich!

renegades