3. Codeoptimierung mit VC

Codeoptimierung mit VC

  • T

    Hallo,

    Ich hatte mal wieder ein bisschen Zeit zum Saubermachen und Review von älteren Codeschnipseln und dabei bin ich in meiner Bildverarbeitungslib auf ein paar Funktionen gestoßen, wo ich mich ein bisschen an Geschwindigkeitsoptimierung versucht habe.

    Zum Ablauf:

    Da ich keine genaue Zeitmessung eingebaut habe, habe ich einfach mit riesigen Bildern ( 24Bit bei 20496 x 672 Pixeln -> 40MB Pro Bild)getestet. Dadurch kommt man relativ leicht auf Performanceunterschiede im Sekundenbereich. Als erstes ist mir eine kleine Sortierfunktion ins Auge gefallen. Beim Medianfilter wird die für jeden zu filternden Pixel aufgerufen:

    //Sorts an array arr[1..n] into ascending numerical order, by straight insertion. n is input; arr is replaced on output by its sorted rearrangement.
//No. (1)
inline void __fastcall piksrt( BYTE* arr, int n )
{
	BYTE a = 0;
	BYTE i = 0;
	for (int j=2; j<=n; j++) 
	{	
		a = arr[j];//Pick out each element in turn.
		i=j-1;
		while (i > 0 && arr[i] > a) 
			arr[i+1]=arr[i--];//Look for the place to insert it.
		arr[i+1]=a;//Insert it.		
	}
}
//No. (2)
inline void __fastcall piksrt( int* arr, int n )
{
	int a = 0;
	int i = 0;
	for (int j=2; j<=n; j++) 
	{	
		a = arr[j];
		i=j-1;
		while (i > 0 && arr[i] > a) 
			arr[i+1]=arr[i--];
		arr[i+1]=a;	
	}
}

    Den Code habe ich ziemlich analog aus Numerical Recipies in C übernommen. Zu meinem Erstaunen war Variante (2) deutlich schneller - sowohl im Debug, als auch im Release - Modus. Wieso?

    DEBUG                 RELEASE
Zeit:     30s                   17s
          23,75                 6,7s

    Ich hätte eigentlich vermutet das (1) schneller ist, da ja weniger Daten hin und her geschaufelt werden müssen, oder liegt das an internen CPU - Optimierungen( 32Bit vs. 8Bit )?

    0
  • R

    Du benutzt doch sicher eine IA32 CPU? IA32 arbeitet am besten mit 32Bit Variablen. Also liegt das hier an der CPU.

    0
  • T

    Ich hab es bisher nur auf einem P4 getestet. Der Begriff IA32 war mir neu. Ich finde das trotzdem ziemlich häßlich. Diese Problematik taucht in meinen Algos an verschiedensten Stellen auf.
    Ich habe also wiedermal die Wahl Time vs. Space. Gehe ich von 8Bit pro Farbkanal aus, dann sind 32Bit eine sinnlose verschwendung von 3/4 Speicher. - Bei dem obigen Beispiel sicher unerheblich, da dass zu sortierende Array nie allzu groß wird.

    0
  • G

    Warum nimmst du überhaupt so einen lahmen Algorithmus zum Sortieren? Gibt es einen Grund, kein Quicksort oder ähnliches zu verwenden? ...und kannst du nicht generell die Standardbibliothek für dich sortieren lassen?

    0
  • T

    @Gregor:

    Darum gings mir eigentlich nicht, sondern zu verstehen, warum da ein für mich zunächst wiedersprüchliches Ergebnis rauskommt. Die Problematik, die kingruedi dort angesprochen hat würden dann ja dort genauso auftreten.

    Ich hatte den Quicksort aus Numerical Recipies in C auch schon drinne, ebenso, wie qsort aus der C - stdlib - war aber deutlich langsamer. Quicksort bringt doch IMHO nur was bei größeren Datenmengen ( qsort wurde bei mir sogar von 'nem simplen Bubblesort abgehängt ).

    Aber ich werde trotzdem mal ein bisschen die STL durchforsten ob ich was scheenes finde 🙂

    0
  • H

    Aber ich werde trotzdem mal ein bisschen die STL durchforsten ob ich was scheenes finde

    std::sort ist in der Regel deutlich performanter als qsort, da die Vergleichsfunktion hier problemlos inline generiert werden kann. Bei qsort ist dies aufgrund des indirekten Funktionsaufrufs nicht so ohne weiteres möglich.

    0
  • T

    Yop, kann ich bestätigen

    std::sort war noch mal ein bisschen schneller als mein kleines piksrt (1s im Release - Modus).

    @Hume:
    Asche auf mein Haupt, ich habe wohl bisher im allgemeinen in meinen Programmen die STL etwas vernachlässigt. Ich gelobe Besserung.

    @kingruedi

    Was heiß das jetzt aber genau: Wird jedes BYTE auf Assemblerebene dann in einen 32 Bit Wert umgesetzt. Das würde die langsamere Umsetzung von (1)erklären. (unabhängig von dem Sortierbeispiel betrachtet)

    0
  • H

    @TheBigW
    Break-Point setzen (im Release-Modus am Einfachsten mit __asm { int 3 } ) und notfalls Alt-8 drücken. Schwupps siehst du den Assemblercode und kannst wunderbar Vergleiche anstellen.

    0
  • B

    TheBigW schrieb:

    Was heiß das jetzt aber genau: Wird jedes BYTE auf Assemblerebene dann in einen 32 Bit Wert umgesetzt. Das würde die langsamere Umsetzung von (1)erklären. (unabhängig von dem Sortierbeispiel betrachtet)

    Ja, da wo du zwei BYTE-Werte vergleichst (integral promotion). Ich weiss nicht, ob das soviel ausmacht, das ist nur ein zusätzlicher Befehl. Das passiert natürlich auch jedesmal, wenn du i vergleichst oder als Arrayindex verwendest, und das ist viel öfter ... versuch mal, i als int zu deklarieren.

    0
  • T

    Tatsache!

    i als int deklariert und schon sind die zwei Funktionen nahezu genauso schnell. Das kommt mir auch sehr recht weil ich in allen anderen Funktionen meist mit for( int k =..... ) über alle Pixel laufe.

    0
Anmelden zum Antworten