yip: verschiedene Retrografik-Funktionen mit und ohne Optimizer



  • Hi(gh)!

    Angeregt durch meinen letzten Thread im C-Subforum habe ich den Optimizer von g++ auch mal auf yip (Yadgar's Image Processor) angewandt und mit meinem Primitiv-Benchmark-Skript die Rechenzeiten gestoppt:

    Jeweils bearbeitet: 972 RGB-Bilder (TGA, 640 x 360)

    Schwarzweiß-Filter (Schwellwert 128):

    g++: 8'30,1394688
    g++ -O3: 7'40,0070784 - 10,9 % schneller!

    Schwarzweiß-Filter (Schwellwert mittlerer Grauwert des jeweiligen Frames):

    g++: 8'37,3663104
    g++ -03: 7'33,4849152 - 14,1 % schneller!

    Schwarzweiß-Filter mit Floyd-Steinberg-Rasterung:

    g++: 12'37,0607328
    g++ -O3: 8'38,4356832 - 46,0 % schneller!!!

    Jeweils bearbeitet: 972 RGB-Bilder (TGA, 40 x 23)

    Umrechnen auf C 64-Farbpalette, mit schwarzen Pixeln auf 40 x 25 ergänzen:

    g++: 0'07,6216032
    g++ -O3: 0'07,6025952 - nur 0,3 % schneller!

    Umrechnen auf C 64-Farbpalette (mit Floyd-Steinberg-Rasterung), mit schwarzen Pixeln auf 40 x 25 ergänzen:

    g++: 0'11,8573632
    g++ -O3: 0'07.8659424 - 50,7 % schneller!!!

    Die Floyd-Steinberg-Rasterfunktion:

    void floydsteinberg(vector<vector<pixel> > &img, vector<rgb> &pal)
    {
      unsigned short h = img.size();
      unsigned short w = img[0].size();
      unsigned short r, c, i;
      unsigned short p = pal.size();
      rgb t0, t1, t2, t3, t4, closest=pal.at(0);
      rgb triple, dist;
      float newred, newgreen, newblue;
      
      for (r=0; r<h; r++)
      {
        for (c=0; c<w; c++)
        {
          t0 = {-1, -1, -1}; // = triple
          t1 = {-1, -1, -1};
          t2 = {-1, -1, -1};
          t3 = {-1, -1, -1};
          t4 = {-1, -1, -1};
          t0.red = img[r].at(c).get_red();
          t0.green = img[r].at(c).get_green();
          t0.blue = img[r].at(c).get_blue();
          if (c < w-1)
          {
    	t1.red = img[r].at(c+1).get_red();
    	t1.green = img[r].at(c+1).get_green();
    	t1.blue = img[r].at(c+1).get_blue();
          }
          if (c > 0 && r < h-1)
          {
    	t2.red = img[r+1].at(c-1).get_red();
    	t2.green = img[r+1].at(c-1).get_green();  	  	
    	t2.blue = img[r+1].at(c-1).get_blue();  	  	
          }
          if (r < h-1 )
          {
    	t3.red = img[r+1].at(c).get_red();
    	t3.green = img[r+1].at(c).get_green();
    	t3.blue = img[r+1].at(c).get_blue();
          }
          if (c < w-1 && r < h-1 )
          {
    	t4.red = img[r+1].at(c+1).get_red();
    	t4.green = img[r+1].at(c+1).get_green();
    	t4.blue = img[r+1].at(c+1).get_blue();
          }    	  
          for (i=0; i<p; i++)
          {
    	if (coldist(t0, pal.at(i)) < coldist(t0, closest))
    	closest = pal.at(i);
          }
          img[r].at(c).set_all(closest.red, closest.green, closest.blue);
          dist.red = t0.red - closest.red;
          dist.green = t0.green - closest.green;
          dist.blue = t0.blue - closest.blue;
          if (t1.red > -1)
          {
    	img[r].at(c+1).get_all(triple);
    	newred = triple.red + dist.red*0.4375;
    	newgreen = triple.green + dist.green*0.4375;
    	newblue = triple.blue + dist.blue*0.4375;
    	img[r].at(c+1).set_all(mround(newred), mround(newgreen), mround(newblue));
          }
          if (t2.red > -1)
          {
    	img[r+1].at(c-1).get_all(triple);
    	newred = triple.red + dist.red*0.1875;
    	newgreen = triple.green + dist.green*0.1875;
    	newblue = triple.blue + dist.blue*0.1875;
    	img[r+1].at(c-1).set_all(mround(newred), mround(newgreen), mround(newblue));
          }
          if (t3.red > -1)
          {
    	img[r+1].at(c).get_all(triple);
    	newred = triple.red + dist.red*0.3125;
    	newgreen = triple.green + dist.green*0.3125;
    	newblue = triple.blue + dist.blue*0.3125;
    	img[r+1].at(c).set_all(mround(newred), mround(newgreen), mround(newblue));
          }
          if (t4.red > -1)
          {
    	img[r+1].at(c+1).get_all(triple);
    	newred = triple.red + dist.red*0.0625;
    	newgreen = triple.green + dist.green*0.0625;
    	newblue = triple.blue + dist.blue*0.0625;
    	img[r+1].at(c+1).set_all(mround(newred), mround(newgreen), mround(newblue));
          }
        }
      }
    }
    
    

    profitiert sichtlich am meisten von der Optimierung - aber wieso? Liegt es am häufigen Zugriff auf Klassenobjekte?

    In den nächsten Wochen habe ich vor, sukzessive eine C-Version von yip aufzubauen und die dann auch geschwindigkeitsmäßig mit der bisherigen C++-Version zu vergleichen...

    Bis bald im Khyberspace!

    Yadgar



  • @yadgar sagte in yip: verschiedene Retrografik-Funktionen mit und ohne Optimizer:

    .at(c)

    Wenn man schnell will nimmt man nicht at.



  • @yadgar sagte in yip: verschiedene Retrografik-Funktionen mit und ohne Optimizer:

    Optimierung

    klar, und das mit ständigem std::vector<>::at(), *lach*

    @yadgar sagte in yip: verschiedene Retrografik-Funktionen mit und ohne Optimizer:

    In den nächsten Wochen habe ich vor, sukzessive eine C-Version von yip aufzubauen und die dann auch geschwindigkeitsmäßig mit der bisherigen C++-Version zu vergleichen...

    Da brauchst du nicht vergleichen. Es ist ja allgemein bekannt, daß in C geschriebene Programme schneller sind, als in C++.



  • Das würde ich überhaupt nicht unterschreiben.



  • @swordfish sagte in yip: verschiedene Retrografik-Funktionen mit und ohne Optimizer:

    klar, und das mit ständigem std::vector<>::at(), *lach*

    Kann ich denn statt img[r].at(c) einfach img[r][c] schreiben? Nach dem Breymann-Kapitel über die Klasse vector (Ausgabe 1998) kam mir das nicht so vor...



  • @yadgar Ja. Du könntest es auch schön langsam mal bleiben lassen, rgb *und* pixel zu verwenden, wo beide doch dasselbe darstellen und die komponentenweise kopiererei bleiben lassen.

    @Mechanics Klar, der ganze unnütze objektorientierungs-Schmarrn und Templates machen doch alles nur unnötig überkompliziert und lahm. Mit der Meinung bin ich auch nicht alleine:

    @3xotherm sagte in WinAPI und C: Zukunftschancen und mehr:

    Ich habe Daten, will die verändern und neu schreiben, was ist die einfachste und cache freundlichste Art dies in purem C zu tun.



  • @yadgar sagte in yip: verschiedene Retrografik-Funktionen mit und ohne Optimizer:

    Kann ich denn statt img[r].at(c) einfach img[r][c] schreiben?

    img ist doch ein 2Dvector? Also die sichere Schreibweise img.at(r).at(c). Also kannst Du daraus auch img[r][c] machen.

    Statt unsigned short würde ich lieber std::size_t nehmen, schon der Name verrät, das dies ein besserer Typ für die Größe eines Array ist.



  • @lemon03 sagte in yip: verschiedene Retrografik-Funktionen mit und ohne Optimizer:

    img ist doch ein 2Dvector?

    Ja, das nächste Performance-*lach* lol



  • vector<vector<pixel>> ist aber die schlechteste Datenstruktur für 2D-Bild (weil speichertechnisch anders aufgebaut und auch unperformant).
    Entweder array<pixel, N>benutzen (falls die Größe schon zur Kompilierungszeit feststeht) oder aber nur vector<pixel>(und dabei das 2D-Bild als Rows*Columns auffassen und die Indizes selber berechnen bzw. eine passende Klasse bzw. Funktionen dafür schreiben).

    Und den Code selbst kann man sicherlich auch noch weiter optimieren. Ich würde z.B. die Floatingpointberechnungen (bzw. casten) eliminieren und nur mit Integern arbeiten, also z.B. newred = triple.red + (112*dist.red) / 256.



  • Wenn doch bloß letztens hier jemand ausführlich, inklusive Beispiel Implementierung, erklärt hätte, wie man ein 2 dimensionales Array in C++ implementiert.





  • Oder eine struct mit je pos_x, pos_y und einem Farbwert/einen Index aus einem bestimmten Farbbereich.



  • @swordfish sagte in yip: verschiedene Retrografik-Funktionen mit und ohne Optimizer:

    @Mechanics Klar, der ganze unnütze objektorientierungs-Schmarrn und Templates machen doch alles nur unnötig überkompliziert und lahm. Mit der Meinung bin ich auch nicht alleine:

    Es geht nicht um Meinungen. Nenn mir objektive Gründe, warum das so sein sollte. Es gibt keine.
    Und ja, in der Praxis wirst du oft Recht haben. Und man kann mit Objektorientierung ganz leicht etwas überkompliziertes bauen, was nicht mehr optimierbar ist. Das ist aber kein Grund pauschal zu sagen, C wär grundsätzlich schneller. Wenn du identischen Code wie in C schreibst, wird der C++ Compiler auch (mindestens) genauso schnellen Code erzeugen. Und mit Templates kann man leicht schnelleren Code erzeugen, als man das in C (mit vernünftigem Aufwand) machen könnte.



  • Ich bin mir sicher, dass Swordfish mitunter zu Sarkasmus neigt.



  • Yeah 🙂 Aber ich frage mich, ob Mechanics gerade dies bewusst war und extra "unschuldig" darauf reagiert hat. Sozusagen diesen Sarkasmus absichtlich ignoriert hat.



  • Mir ist schon klar, dass Swordfish zu Sarkasmus neigt. In dem Fall ist mir aber nicht klar, ob das so beabsichtigt war. Es gibt viele sehr gute Entwickler, die C bevorzugen, warum sollte das nicht seine ehrliche Meinung sein?



  • @mechanics sagte in yip: verschiedene Retrografik-Funktionen mit und ohne Optimizer:

    Es gibt viele sehr gute Entwickler, die C bevorzugen, warum sollte das nicht seine ehrliche Meinung sein?

    Vielleicht lehne ich mich zu weit aus dem Fenster, aber weil Swordfish den Thread [WinAPI und C: Zukunftschancen und mehr] als Beispiel seiner Argumentation genannt hat und sich schon dort sehr sarkastisch gegenüber dem C-Verfechter geäußert hat.



  • @yadgar sagte in yip: verschiedene Retrografik-Funktionen mit und ohne Optimizer:

    profitiert sichtlich am meisten von der Optimierung - aber wieso? Liegt es am häufigen Zugriff auf Klassenobjekte?

    Auch wenn schon einiges dazu geschrieben wurde, hier auch meine 2 Cent:

    Das .at() ist natürlich wegen der Range-Prüfung nicht besonders effizient, selbst wenn man sog. "Zero Overhead"-Exceptions nutzt. Möglicherweise kann der Compiler bei besserer Optimierung aber beweisen, dass die Range immer eingehalten wird, und daher die Prüfungen herausoptimieren. Das ist durchaus ein möglicher Grund.

    Allgemein ist der häufige "Zugriff auf Klassenobjekte" nicht langsamer. Diese Abstraktionen sind in C++ eigentlich recht leichtgewichtig und es kann gut sein, dass deine ganzen img[r].at(c+1).get_red() etc. am Ende in einzelne CPU-Instuktionen zerfallen, die man auch so "von Hand" in Assembler geschrieben hätte. Sowas habe ich schon oft am erzeugten Maschinencode beobachtet, wenn man die Abstraktion möglichst schlank hält und es ist auch einer der Gründe, weshalb ich C++ besonders mag 😉

    "Klassen" werden eigentlich nur "langsam" wenn man den Blick auf das Wesentliche verliert und unnötige Arbeit macht (z.B. bereits geprüfte notwendige Vorbedingungen irgendwo in einem tieferen Funktionsaufruf nochmals prüft, ohne es zu merken) - wie in jeder Sprache. Virtuelle Funktionen haben auch einen geringen Overhead - wenn man sie nicht benötigt, sollte man sie auch nicht verwenden - genauso wie man in C nicht für alles eine Funktionspointer-Tabelle benötigt.

    Ansonsten ist die Funktion auf den ersten Blick auch gut "manuell optimierbar", es würde mich also nicht wundern wenn der Compiler da auch einiges reißen kann: Z.B. lassen sich die Berechnungen gut vektorisieren (als SIMD-Operationen formulieren - SSE2, AVX, etc) und einige If-Blöcke aus den Schleifen herausziehen, so dass nur einmal, und nicht für jedes Pixel geprüft werden muss:

    z.B. ließe sich

    unsigned short w = img[0].size();
    ...
    for (r=0; r<h; r++)
    {
        for (c=0; c<w; c++)
        {
            t0.red = img[r].at(c).get_red();
            ...
            if (c < w-1)
            {
                t1.red = img[r].at(c+1).get_red();
                ...
    

    auch in ein

    unsigned short w = img[0].size();
    ...
    for (r=0; r<h; r++)
    {
        for (c=0; c<w-1; c++)
        {
            t0.red = img[r].at(c).get_red();
            ...
            t1.red = img[r].at(c+1).get_red();
            ...
        }
        t0.red = img[r].at(c).get_red();
        ...
    

    transformieren. Dafür müsste man zwar in diesem Fall zunächst zwar den Schleifenkörper in großen Teilen duplizieren, würde aber ein Prüfung pro Pixel einsparen . Ob das wirklich Sinn macht weiß der Compiler oft ganz gut, macht man es "manuell" sollte man natürlich immer messen. Das nur um eine Idee zu bekommen, was da alles möglich ist.

    Finnegan



  • @mechanics sagte in yip: verschiedene Retrografik-Funktionen mit und ohne Optimizer:

    Mir ist schon klar, dass Swordfish zu Sarkasmus neigt.

    Das ist doch nebenbei auch völlig wurscht.
    Wenn ich in einem (fremden) Forum nach einer Antwort suche, dann hab ich bestimmt keine Lust, mir 100te von alten Antworten durchzulesen, um einschätzen zu können, ob der Beantworter wohl zu Sarkasmus neigt.

    Danke fürs richtig stellen.



  • Doppelte Geschwindigkeit mit -O2 vs -O0 ist bei Schleifen die zum Grossteil aus eigenem Code bzw. Aufruf von Template-Gedöns aus der Standardlibrary bestehen nicht weiter verwunderlich. Da muss man IMO nicht anfangen nachzuforschen wieso.


Log in to reply