array algos

decembersoul · 18. Juni 2005

Ich bin auf der suche nach verschiedenen Möglichkeiten wie man am schnellsten mir array's umgeht.

Array's initialisieren kann man ja ganz gut mit memset machen.
Auch das kopieren von arrays geht gut und schnell mit memcpy

Was ist aber wenn ich das maximum oder den avg in einem Array finden will?
Gibt es dafür optimierte Möglichkeiten unter cpp?

Oder wenn ich überprüfen will ob alle Werte == 0 sind.
Da ich recht grosse arrays habe, wäre ich für diesen Fall für einen Tip dankbar.

Eine "for" Schleife über alle Elemente ist zwar einfach, aber auch recht langsam....

hmmm mir ist zwar gerade was eingefallen aber ich hoffe das jemand von euch vielleicht einen Tip hat.

Vielleicht kennt ja jemand auch eine gute Seite wo solche Tips besprochen werden.

DiCon · 18. Juni 2005

Wenn es sich einfach um ein unsortiertes Array handelt, bleibt dir wohl nichts anderes übrig, als eine Schleife zu benutzen, schließlich muss jedes Feld in die Überlegung einbezogen werden, ob ein bestimmter Wert Maximum oder ob alle Felder = 0 sind. Beim Durchschnitt kannst du natürlich ein paar repräsentative Werte nehmen, falls der nicht so genau sein muss.

Weitere Optimierungen kannst du aber nur dann vornehmen, wenn du ein bischen was über die Daten weißt oder sie sortierst. Entscheidend ist, woher die Daten in welcher Form kommen und wie oft du welche Operationen darauf ausführen musst.

Bei der Situation "zufälliges Array ohne weitere Informationen" kann man meines Wissens das Maximum und ob alle = 0 sind nur mit der Ordnung O(n) ermitteln. Zu deutsch: Bei n Elementen braucht man n Operationen (also Vergleiche). Wenns besser werden soll, musst du ein paar Infos mehr ausspucken...

decembersoul · 18. Juni 2005

OK fangen wir mal mit einer ganz schlechten Version an:

Code

int my_array[]={10,3,35,101,65,100};
int elements = sizeof(my_array)/sizeof(int);
int max=0;
for (int i=0;i<elements:i++){
  if (max<my_array[i])
     max=my_array[i];
}
 cout << "max: " << max << endl;

Besser ist:

Code

int my_array[]={10,3,35,101,65,100};
 int elements = sizeof(my_array)/sizeof(int);
 sort(my_array, my_array+elements);
 cout << "max: " << my_array[elements-1] << endl;

Problem hierbei ist nur das das array verändert wird.

Sinn der ganzen Sachen ist:
Ich möchte in einem Bild (als Array) alle Pixel auf 0 setzen wenn sie kleiner als (max - x) sind.

An einer anderen Stelle möchte ich überprüfen ob alle (pixel <= x) sind.
(x kann z.B. 3 sein.)

DiCon · 18. Juni 2005

Die Idee mit dem Sortieren ist definitiv nicht besser. Selbst der beste Sortieralgorithmus hat eine Ordnung von O(n*log(n)). (Da bringt mir Informatik als Nebenfach zum Physik-Studium ja auch mal was). Soll heißen: Allein das Sortieren dauert länger, als das Array einfach abzulaufen. Sortieren hilft hier nur, wenn zwischen zwei Test einzelne Werte hinzukommen und diese direkt sortiert eingefügt werden könnten.

Für dein Problem habe ich aber jetzt noch keine Idee, um das zu optimieren...

decembersoul · 18. Juni 2005

Um alles auf "0" zu überprüfen, würde mir noch ein dirtyTrick einfallen.
Weiß nur gerade nicht ob der geht.

Also mein array ist kein "int" array sondern ein "uint_8t" array (also 8 bit)
Wenn ich nun aber immer 16(oder vielleicht 32) bit mit 0 vergleichen würde, müsste ich nur jeden zweiten(oder vierten) vergleichen.

Soweit zur Theorie.
Ob das was bringt weiß ich nicht.
Müßte dann ja immer casten.
Werde ich mir mal überlegen.

Gibt es denn nicht von cpp irgendeine optimierte methode?

pram · 18. Juni 2005

Hi, wenns wirklich schnell gehen soll, dann empfehle ich MMX:

http://www.fh-zwickau.de/doc/prmo/mmxtutor/text/

Man kann mit dem "PCMPGTB" -Befehl gleich 8 Bit vergleichen:
http://www.fh-zwickau.de/doc/prmo/mmxtutor/text/mmx_10.htm

Wenn man das Ergebis von obeigen Befehl mit "PSUBUSB" (Subtraktion mit signed saturation) vom Original abzieht, sind alle Bytes 0. Somit hätte man mit 2 Befehlen 8 Bytes gleichzeitig bearbeitet (overhead für MMX-Initialisierung nicht mit gerechnet)

z.B. so (code nicht getestet)
MM7 = 40 40 40 40 40 40 40 40 // Schwellwert
[speicher] = 20 30 40 50 60 70 80 90 // Pixel

:loop
MOVQ [speicher], MM1 // 8 bit aus Speicher in MM0 laden

MOVQ MM7, MM0 // Schwellwert in MM0 kopieren

PCMPGTB MM0, MM1 // Ergebnis: MM0=FF FF 00 00 00 00 00 00

PSUBUSB MM1, MM0 // Ergebis: MM1= 00 00 40 50 60 70 80 90

MOVQ MM1,[speicher] // abspeichern

// speicher++8
jump loop

Durch ein weig loop unrolling lässt siich dann noch einiges heraus holen, wenn man die Zugriffe auf die einzelenen Prozessorteile gleichmäßig verteilt.

Der Nachteil von MMX ist, dass das Array eine vielfache Größe von 8 haben muss/soll, sonst wirds tricky zum programmieren.

Gruß
Roland

decembersoul · 18. Juni 2005

Das ist ganz gut.
Auf der Seite ist auch ein Beispiel für Filterung.
Ich wende auch einen Soble Filter an.
Das kann ich dann auch mal optimieren.

Das doofe dabei ist nur das man die Algos doppelt schreiben muss.
Einmal für MMX und einmal ohne.

Was passiert wenn ich einen MMX Befehl ausführe ohne zu testen ob die CPU das kann?
MMX ist ja eigentlich Intel Sache.

Mein Arbeitsrechner ist aber ein AMD

pram · 18. Juni 2005

...dann stürzt das Programm ab mit illegal execution.

MMX können eigentlich alle neueren Prozessoren ab 500 MHz
(bei den VIA/EPIA bin ich mir da im Moment nicht so sicher)

Einfach mal "cat /proc/cpuinfo" machen, da steht dann was der Prozi alles kann.

Gruß
Roland

decembersoul · 18. Juni 2005

alles klar.
Mein AMD kann mmxext

Urig · 19. Juni 2005

Ich würde einfache Schleifen verwenden, und den Rest dem Compiler überlassen, der ist ja beim Optimieren auch nicht ganz dumm. Selbst wenn der Code durch Zusammenfassen von 4-8 Bytes zu dword bzw. mmx-Registern schneller wird, in der Praxis ist die Gesamtlaufzeit entweder so minimal, dass es keinen Unterschied macht, oder das Array ist schon so groß, dass eh die Geschwindigkeit des Arbeitsspeichers das entscheidende ist.

Nimm als Beispiel ein 1Mb-Array, und verschwende pro Byte 10 CPU-Takte (das sind 20-30 Instruktionen!), dann hast du bei 1GHz trotzdem alles in 0.01s erledigt.

Wenn es unbedingt mmx sein muss, empfehle ich die Verwendung von intrinsics-Kapselungen wie zb. __builtin_ia32_pcmpgtb() statt direktem Assemblercode. Macht den Code lesbarer, man kann mit Variablen statt Registern arbeiten, und der Optimierer kümmert sich um die optimale Anordnung der Befehle.

Gruß,

Udo

Tyger · 19. Juni 2005

Hallo,

für einige generische Algorithmen unter cpp kann ich einen Blick in die STL empfehlen. Eine brauchbare Referenz findet sich z.B. unter http://www.sgi.com/tech/stl/

Die STL-Algorithmen werden in Hinblick auf Generalität und Effizienz implementiert und dürften ausser in echten Spezialfällen die optimale Wahl sein.

C

#include <algorithm>
#include <numeric>


void main() {
const int N = 42;
float my_array[N];
// Array mit Werten füllen
std::generate(my_array, my_array+N, drand48);
// Mittel berechnen: Summe/Anzahl
float fAvg = std::accumulate(my_array, my_array+N, 0)/N;
// Maximales Element bestimmen
float fMax = std::max_element(my_array, my_array+N);
}

Alles anzeigen

Cya, Ed

decembersoul · 19. Juni 2005

Ich habe hier ein array mit (max 1920x1080=2073600) Feldern.
Und das ca 25x60x60x~2=180000 mal.
EXTREMFALL
Und dann muss ich auch noch öfter über jedes Array rüber.

Da macht es schon gut was aus was man macht.
Auf der MMX Seite wird der Vergleich zu 1:2,5 gesagt.
Das wäre schon ein ganz guter unterschied.
Ich muß mal sehen ob ich das mit meinen Kenntnissen hinbekomme.

Hier mal der Vergleich(auch von der Seite)
Dabei wird ein Bild um einen Wert aufgehellt.

Code

// C Version Nr. 1
void c_version1 ( char *buffer, int xsize, int ysize, char add )
    {
    int i, j;


    for (j=0; j<ysize; j++)
        {
        for (i=0; i<xsize; i++)
            {
            *(buffer+ j*xsize+ i)+= add;
            }
        }
    }

Alles anzeigen

Code

// C Version Nr. 2
void c_version2 ( char *buffer, int xsize, int ysize, char add )
    {
    register int i;


    for (i=0; i<xsize*ysize; i++)
        {
        *( buffer )+= add;
        buffer++;
        }
    }

Alles anzeigen

Code

// C Version Nr. 3
void c_version3 ( char *buffer, int xsize, int ysize, unsigned int add )
    {
    register int i;


    for (i=0; i<xsize*ysize / 4; i++)
        {
        *( (unsigned int*) buffer )+= add;
        buffer+= 4;
        }
    }


Dabei sollte beachtet werden, daß diese Vorgehensweise hier nur möglich ist, weil ohne Saturation gearbeitet wird.

Alles anzeigen

Code

// ASM Version Nr. 1
// (besitzt gleiche Funktionalität wie C Version Nr. 2)
void asm_version1 ( char *buffer, int xsize, int ysize, int add );
#pragma aux asm_version1=               \
    "       imul ecx,eax               "\
    "                                  "\
    "inc_loop:                         "\
    "       add byte ptr [edi],bl      "\
    "       inc edi                    "\
    "       dec ecx                    "\
    "       jnz inc_loop               "\
    parm [edi] [ecx] [eax] [ebx] modify [edi ecx eax ebx];

Alles anzeigen

Code

// ASM Version Nr. 2
// (besitzt gleiche Funktionalität wie C Version Nr. 3)
void asm_version2 ( char *buffer, int xsize, int ysize, int add );
#pragma aux asm_version2=               \
    "       imul ecx,eax               "\
    "       shr ecx,2                  "\
    "                                  "\
    "inc_loop:                         "\
    "       add dword ptr [edi],ebx    "\
    "       add edi,4                  "\
    "       dec ecx                    "\
    "       jnz inc_loop               "\
    parm [edi] [ecx] [eax] [ebx] modify [edi ecx eax ebx];

Alles anzeigen

Code

// MMX Version Nr. 1 (im Modul mmx1.asm definiert)


        MOVD  MM1,ecx            ; Additionswert nach MM1
        MOVQ  MM0,MM1            ; alle gepackten Bytes nach MM1
        PSLLQ MM1,32
        PADDD MM1,MM0            ; alle gepackten Bytes in MM1
                                 ; besitzen Wert aus ecx
        imul eax,ebx
        xchg ecx,eax
        shr ecx,3                ; wir bearbeiten jeweils 8 Byte !


mbadd_loop:
        MOVQ    MM0,[esi]        ; 64-Bit nach MM0
        PADDB   MM0,MM1          ; 64-Bit gepackte Daten mit
                                 ; Unsigned Saturation addieren
        MOVQ    [esi],MM0        ; Ergebnis zurück


        add esi,8                ; 64-Bit (= 8 Byte) weiter
        dec ecx
        jnz mbadd_loop

Alles anzeigen

Code

Werte für 921600 bearbeitete Bytes:


  Funktion             Counter-High   Counter-Low
----------------------------------------------------
  C Version 1, Taktzyklen=    0       24210951
  C Version 2, Taktzyklen=    0       23084943
  C Version 3, Taktzyklen=    0        8177420
ASM Version 1, Taktzyklen=    0        5440261
ASM Version 2, Taktzyklen=    0        3087126
MMX Version 1, Taktzyklen=    0        3055348

Alles anzeigen

In diesem Einfachher Beispiel ist der Faktor sogar fast 1:8

anbr · 19. Juni 2005

Hi,

nur mal interessehalber, wie gehen den die Laufzeiten runter,
wenn Du Version 3 wie folgt abänderst ?

speziell preincrement (++i), sollte gegenüber postincrement(i++) noch ein paar OP einsparen...

Code

// C Version Nr. 3
void c_version3 ( char *buffer, int xsize, int ysize, unsigned int add )
    {
    register int i;
    register int s=xsize*ysize / 4;


    for (i=0; i<s; ++i)
        {
        *( (unsigned int*) buffer )+= add;
        buffer+= 4;
        }
    }

Alles anzeigen

Andreas

Urig · 20. Juni 2005

Bei den Vergleichsmessungen stört mich schon mal, dass mit keinem Wort erwähnt wird, welcher Compiler eingesetzt wurde, und welche Optimierungen aktiviert waren. Seriös vergleichen kann man so jedenfalls nicht. Ein guter optimierender Compiler sollte die C-Versionen 1 und 2 so gut übersetzen können wie ASM-Version 1, und C-Version 3 so gut wie ASM-Version 2. (sehr gute Optimierer könnten die ASM-Versionen vermutlich sogar schlagen.)

Dass bereits von C zu ASM Geschwindigkeitsunterschiede von Faktor 2 oder 4 auftreten, spricht jedenfalls nicht für den Compiler. Die Rechnerangabe Pentium MMX 166 spricht auch Bände - das dürfte keinerlei Rückschlüsse auf aktuelle Recher erlauben.

> speziell preincrement (++i), sollte gegenüber postincrement(i++) noch ein paar OP einsparen...

Vielleicht in Steinzeit-Compilern. Optimierende Compiler machen das Inkrement dann, wenn es am besten passt. Und das bedeutet, wenn eine Recheneinheit frei ist. Das Herausziehen der Multiplikation aus der Schleife hilft dagegen tatsächlich.

Als kleinen Test hab ich die Variante von Hulk mal durch GCC 3.3.3 gejagt, mit den flags -march=i686 -masm=intel -funroll-loops -O3 -S. Hier das (etwas aufgeräumte) Ergebnis:

Code

push	ebp
	mov	ebp, esp
	push	ebx
	mov	ebx, DWORD PTR [ebp+8]  // buffer
	mov	ecx, DWORD PTR [ebp+20] // add
	mov	eax, DWORD PTR [ebp+16] // ysize
	mov	edx, DWORD PTR [ebp+12] // xsize


	imul	eax, edx
	lea	edx, [eax+3]
	cmp	eax, -1
	cmovle	eax, edx
	sar	eax, 2


	test	eax, eax
	jle	EXIT
	mov	edx, eax
	neg	eax
	and	eax, 3
	je	LOOPROLL0
	cmp	eax, 3
	jge	LOOPROLL1
	cmp	eax, 2
	jl	LOOPROLL3
LOOPROLL2: 
	add	DWORD PTR [ebx], ecx
	add	ebx, 4
	dec	edx
LOOPROLL1: 
	add	DWORD PTR [ebx], ecx
	add	ebx, 4
	dec	edx
	je	EXIT
LOOPROLL0: 
	lea	eax, [ebx+12]
LOOP:
	add	DWORD PTR [eax-12], ecx
	add	DWORD PTR [eax-8], ecx
	add	DWORD PTR [eax-4], ecx
	add	DWORD PTR [eax], ecx
	add	eax, 16
	sub	edx, 4
	jne	LOOP
EXIT:
	pop	ebx
	pop	ebp
	ret
LOOPROLL3:
	add	DWORD PTR [ebx], ecx
	add	ebx, 4
	dec	edx
	jmp	LOOPROLL2

Alles anzeigen

Wie man sieht, macht die Hauptschleife jetzt jedes mal 16 Bytes in 7 Befehlen, das sollte ASM2 (4 Bytes in 4 Befehlen) deutlich schlagen.

Gruß,

Udo

array algos

Jetzt mitmachen!

Teilen

Benutzer online in diesem Thema