Ideen zur Beschleunigung des Codes (Camera Bild einlesen)

[gastgast]

Die Berechnung der aktuellen Pixelposition ist wg. multiplikation nicht besonders effizient:

for ( int x = 0; x < m_nSizeX; x++ ) {
            for ( int y = 0; y < m_nSizeY; y++ ) {
                // (x*bytes) + (y * sizex)
                long lMemoryPixelOffset = ((long)x * m_nBytesPerPixel) + ((long)y * nPitch );
                pPixelPointer = (reinterpret_cast<char*> (pMemVoid) + (lMemoryPixelOffset)) ;

                pixelToRGB(pPixelPointer, r, g, b);
                d->rgbMatrix.setPixel(x,y,r,g,b);
            }
        }

Für jedes Pixel werden zwei Multiplikationen und zwei Additionen ausgeführt (plus die Inkremente der Schleifen). Besser ist es, wenn Du eine Datenstruktur bereit hälst, die Dein aktuelles Pixelformat abbildet:

// Diese struct muss der organisation eines Pixels im Speicher entsprechen
struct RGBPixel
{
    unsigned char r;
    unsigned char g;
    unsigned char b;
    unsigned char x; // unused, 32bit alignment
};

// jetzt der Zugriff
RGBPixel* imageIterator = getImageStart(); // Hier den Start des Bildes im Speicher bestimmen
for( int y = 0; y < rows; y++ )
{
    for( int x = 0; x < columns; x++ ) // hier wird imageStart immer um ein ganzes Pixel weiter geschoben
    {
        setPixel(imageIterator.r, imageIterator.g, imageIterator.b);
        imageIterator++;
    }
}

Hier ist jetzt nur noch eine Addition plus Addressbildung mit offset (in der Struktur). Das ist in der Regel deutlich schneller. Die setPixel Methode muss nicht geändert werden. DAs funktioniert so natürlich nur, wenn die Daten hintereinander im Speicher liegen.

[pospiech]

Das dumme ist nur, dass die Daten sehr unterschiedlich organisiert sein können.
Der Hersteller kennt ~20 Verfahren wie die Daten organisiert sein können.
Selbst wenn ich es auf 3 sinnvolle reduziere (8 mono, 10 mono, 8 rgb),
dann ist es nicht möglich das mit nur einer Struktur zu umzusetzen.
und insbesondere die 10 Bit Strukturen machen Problem. Ansonsten hast du natürlich recht.

[gastgast]

Du kannst Dir ja entsprechende Strukturen mit Zugriffsoperatoren anlegen. Dann hast Du eine einheitliche Schnittstelle und der Rest des Codes bleibt gleich. Das gilt für den von Dir beschriebenen Code ja ähnlich. Da muss ja in pixelToRGB() im switch-Statement jeweils eigener Code implementiert werden.

Statt dessen könntest Du Dir eine Factory bauen, die die entsprechenden Klassen zusammenbaut und Dir zurückliefert. Das macht natürlich nur dann Sinn, wenn der Code im Moment noch nicht schnell genug ist.

Ich habe beide Versionen bei mir mal ausprobiert (VisualStudio2008, ReleaseBuild):
Mit Multiplikation auf 5MPixel großem Int-Array: 110ms mit Addition und Strukturen: 15ms

Hier der Code:

const int m_size_x = 1024;
const int m_nSizeX = 1024;
const int m_nSizeY = 1024;

const int chunkSz = 5*m_nSizeX*m_nSizeY;
int largeChunk[chunkSz];

char red[chunkSz];
char green[chunkSz];
char blue[chunkSz];

void pixelToRGB(char* pPixelPointer, int  & r, int & g, int & b)
{
    r = static_cast<int>(*(reinterpret_cast<char*>(pPixelPointer+2)));
    g = static_cast<int>(*(reinterpret_cast<char*>(pPixelPointer+1)));
    b = static_cast<int>(*(reinterpret_cast<char*>(pPixelPointer+0)));
}

int ArrPos(int x, int y)
{
    // y + height * x
    return (x + m_size_x * y);
} 

void setPixel(int x, int y, int r, int g, int b)
{
    int pos = ArrPos(x,y);
    red[pos] = r;
    green[pos] = g;
    blue[pos] = b;
}

void checkPerfMult(void)
{
    int m_nBytesPerPixel = 4;
    int nPitch = 4;
    void* pMemVoid = (void*)largeChunk;
    char* pPixelPointer;
    for ( int x = 0; x < m_nSizeX; x++ ) 
    {
        for ( int y = 0; y < m_nSizeY; y++ ) 
        {
            // (x*bytes) + (y * sizex)
            int r;
            int g;
            int b;
            long lMemoryPixelOffset = ((long)x * m_nBytesPerPixel) + ((long)y * nPitch );
            pPixelPointer = (reinterpret_cast<char*> (pMemVoid) + (lMemoryPixelOffset)) ;

            pixelToRGB(pPixelPointer, r, g, b);
            setPixel(x,y,r,g,b);
        }
    } 
}

void* getImageStart(void)
{
    return largeChunk;
}

void checkPerfAdd(void)
{
    // Diese struct muss der organisation eines Pixels im Speicher entsprechen
    struct RGBPixel
    {
        unsigned char r;
        unsigned char g;
        unsigned char b;
        unsigned char x; // unused, 32bit alignment
    };

    // jetzt der Zugriff
    RGBPixel* imageIterator = reinterpret_cast<RGBPixel*>(getImageStart()); // Hier den Start des Bildes im Speicher bestimmen
    for( int y = 0; y < m_nSizeY; y++ )
    {
        for( int x = 0; x < m_nSizeX; x++ ) // hier wird imageStart immer um ein ganzes Pixel weiter geschoben
        {
            setPixel(x, y, imageIterator->r, imageIterator->g, imageIterator->b);
            imageIterator++;
        }
    } 
}

int main( void )
{
	for(int i = 0; i<sizeof(testCases)/sizeof(testPattern); i++)
	{
		testCases[i].tstPowOfTwo();
	}
    {
        Timer t;
        checkPerfMult();
    }
    {
        Timer t;
        checkPerfAdd();
    }
}

Die Timer-Klasse misst die Zeit per clock() . Bei Bedarf kann ich den Code posten.

[gastgast]

Habs mal mit 100 Durchläufen nachgemessen:

11,027s zu 0,313s. Das ist doch signifikant.

[zeusosc]

Hi,..

Für so etwas gibt es die "Streaming Single Instruction Multible Data Extension" kurz SSE. Oder per GPGPU mittels VBO's.

Damit kannst du Multiplikationen um etliches beschleunigen.
Bei gängigen Graka's kommst Du damit bis auf 300 GFlops,... ( 300 * 10^9 floating point operations per second)

Grüße

[gastgast]

Das ist für Adressberechnungen aber mit Eulen auf Spatzen geschossen (oder Kanonen nach Athen getragen)

Intelligente Algortihmen bringen mehr (s. mein Benchmark)

[darkfate]

gastgast schrieb:

Intelligente Algortihmen bringen mehr (s. mein Benchmark)

nicht ganz weil:
Wenn du es kombinierst, erreichst du einen deutlich höheren Faktor mehr weil mit SSE(1,2,3,4.x) und insbesondere GPGPU deutlich mehr aus gleichbleibendem System und Code herauszuholen ist.

[Gast]

Wenn du es kombinierst, erreichst du einen deutlich höheren Faktor mehr weil mit SSE(1,2,3,4.x) und insbesondere GPGPU deutlich mehr aus gleichbleibendem System und Code herauszuholen ist.

Für allgemeine Verarbeitung gilt das ja, aber im Thread geht es nur um Adress- und Kopieroperationen.

[darkfate]

ogni42 schrieb:

Für allgemeine Verarbeitung gilt das ja, aber im Thread geht es nur um Adress- und Kopieroperationen.

Ich könnte wetten dass durch zuschalten von SSE sich doch mehr rausholen lässt.

[pospiech]

ogni42 schrieb:

Wenn du es kombinierst, erreichst du einen deutlich höheren Faktor mehr weil mit SSE(1,2,3,4.x) und insbesondere GPGPU deutlich mehr aus gleichbleibendem System und Code herauszuholen ist.

Für allgemeine Verarbeitung gilt das ja, aber im Thread geht es nur um Adress- und Kopieroperationen.

Ich erinnere mich an einen Artikel in der Ct wo über die Performance von GPU Algorithmen geredet wurde. Und ein maßgeblicher Faktor war dabei die Zeit die benötigt wird die Daten in die GPU zu bringen. Solange sich hier nicht die gesamte Arithmetik auf Matrizen und massive parallel Verarbeitung abbilden lässt lohnt es sich daher gar nicht GPU zu verwenden.

Bei SSE weiß ich nichteinmal wie man das programmiert.

Da ich aber in wesentlichen Datenstrukturen in andere Datenstrukturen abbilde und eigentlich gar nicht rechnen will, denke ich das Vektor/Matrizen Algorithmen der falsch Ansatz sind.

[darkfate]

pospiech schrieb:

Ich erinnere mich an einen Artikel in der Ct wo über die Performance von GPU Algorithmen geredet wurde. Und ein maßgeblicher Faktor war dabei die Zeit die benötigt wird die Daten in die GPU zu bringen. Solange sich hier nicht die gesamte Arithmetik auf Matrizen und massive parallel Verarbeitung abbilden lässt lohnt es sich daher gar nicht GPU zu verwenden.

Matrizen und Vektoren sind ja nichts anderes als Schleifenkonstrukte.

for( int y = 0; y < m_nSizeY; y++ )
    {
        for( int x = 0; x < m_nSizeX; x++ ) // hier wird imageStart immer um ein ganzes Pixel weiter geschoben
        {
            setPixel(x, y, imageIterator->r, imageIterator->g, imageIterator->b);
            imageIterator++;
        }
    }

Dieser Teil lässt sich mMn sehr gut parallelisieren.

[Gast]

Dieser Teil lässt sich mMn sehr gut parallelisieren.

Ja, aber nicht mit SSE und schon gar nicht mit GPGPU.

Mit SEE macht es keinen Sinn, da in die SSE Register ein komplettes Wort gelegt werden muss und als Ergebnis aber kein weiteres vollständiges Datenwort heraus kommt, sondern auf drei unterschiedliche Worte verteilt wird.

Mit GPGPU macht das keinen Sinn, weil es ja nur um das Umkopieren der Daten geht und die liegen nun mal im Hauptspeicher des Rechners und nicht im Speicher der GPU. GPGPU beschleunigt im Wesentlich Matrixoperationen wie MulAdd, Inversion etc.

Alternative wäre, die Schleife zu entrollen (z.B. mit OpenMP). Das kann, muss aber nicht zu schnellerer Verarbeitung führen. Das hängt von der Organisation der Caches ab. Dazu gibt es ein gutes Paper "What every programmer should know about memory".

[darkfate]

ogni42 schrieb:

Dieser Teil lässt sich mMn sehr gut parallelisieren.

....

Diese Antwort bezog sich nur auf die Schleifen nicht auf SSE oder GPGPU

Ja muss man halt durchprobieren, gibt ja nicht nur openmp..

[zeusosc]

Hi,...

Also die doppelten schleifen durchläufe brauchen Vieeeel zu viel zeit,...
Die Zeilen liegen bei beiden doch so oder so hintereinander im Speicher
Und wie ich das verstanden habe muss nur ein Byte, und zwar x, entfernt werden.

struct RGBX
{ 
  u8 r;
  u8 g;
  u8 b;
  u8 x;
};

struct RGB
{
  u8 r;
  u8 g;
  u8 b;
};

RGBX* startmemRGBX= GetStartOfRGBX();
RGB*  startmemRGB = GetStartOfRGB();

size_t RGBXIndex =0;
size_t RGBIndex  =0;

for(int i=0; i<pixelanzahl; i++)
{
memcpy_s(startmemRGB+RGBIndex,sizeof(RGB),startmemRGBX+RGBXIndex,sizeof(RGBX));

RGBXIndex++;
RGBIndex++;
};

grüüße

[Gast]

Nein, im Ursprungscode wird das Bild in drei separate Felder geschrieben. Die Daten sind auch 24 bit weise organisiert.

[zeusosc]

Ja mein gott,..
dann halt:

u8* redmemory  = getStartOfRedMemory();
u8* bluememory = getStartOfBlueMemory();
u8 greenmemory = getStartOfGreenMemory();  

RGBX* RGBXMemory = getStartOfRGBXMemory();

size_t ColorIndex=0;
size_t RGBXIndex=0;

for( int i=0; i<number_of_pixels; i++)
{
  memcpy_s(redmemory  + ColorIndex,1,((char*)RGBXMemory + RGBIndex) + 2,1);
  memcpy_s(bluememory + ColorIndex,1,((char*)RGBXMemory + RGBIndex) + 1,1);
  memcpy_s(greenmemory+ ColorIndex,1,((char*)RGBXMemory + RGBIndex) + 0,1);
RGBXIndex++;
ColorIndex++;
}

grüüße

[darkfate]

zeusosc schrieb:

Ja mein gott,..
dann halt:

memcpy_s(redmemory  + ColorIndex,1,((char*)RGBXMemory + RGBIndex) + 2,1);
  memcpy_s(bluememory + ColorIndex,1,((char*)RGBXMemory + RGBIndex) + 1,1);
  memcpy_s(greenmemory+ ColorIndex,1,((char*)RGBXMemory + RGBIndex) + 0,1);

memcpy_s braucht man nicht
Dann läuft das ganze noch einen Tacken schneller.

[Gast]

Die memcpy_s Version ist bei mir deutlich langsamer, die mit memcpy ein Drittel schneller:

`

Copying with Mul based address calculation: Time elapsed 11.236s

Copying with Add based address calculation: Time elapsed 0.313s

Copying with memcpy_s based address calculation: Time elapsed 4.844s

Copying with memcpy based address calculation: Time elapsed 0.203s

`

Also macht memcpy das Rennen. Hab' ich wieder was gelernt, ich hatte vermutet, dass bei wortweisem Kopieren da kein Unterschied ist. Danke für den Tipp!

[darkfate]

ogni42 schrieb:

...

Könntest du grad den Code nochmal posten, so langsam verliert man den Überblick wo welche Veränderungen enthalten sind.

0.2s je Frame ist doch ein wenig langsam.
uEye cams können doch wohl mehr als 5frames/s?
Oder ist es die Messung im Debug Modus?

[Gast]

Hier nochmal mein Testcode:

#include <iostream>
#include <Timer.h>

using std::cout;
using std::endl;

const int m_size_x = 1024;
const int m_nSizeX = 1024;
const int m_nSizeY = 1024;

const int chunkSz = 5*m_nSizeX*m_nSizeY;
int largeChunk[chunkSz];

char red[chunkSz];
char green[chunkSz];
char blue[chunkSz];

// Diese struct muss der organisation eines Pixels im Speicher entsprechen
struct RGBPixel32
{
    unsigned char r;
    unsigned char g;
    unsigned char b;
    unsigned char x; // unused, 32bit alignment
};

struct RGBPixel24
{
    unsigned char r;
    unsigned char g;
    unsigned char b;
};

struct MonoPixel8
{
    unsigned char g;
};

struct MonoPixel10Left // left aligned
{
    unsigned short pad  :    6; // padding bits
    unsigned short g    :   10; // 10bit grey value
};

struct MonoPixel10Right
{
    unsigned short g    :   10; // 10bit grey value
    unsigned short pad  :    6; // padding bits
};

void pixelToRGB(char* pPixelPointer, int  & r, int & g, int & b)
{
    r = static_cast<int>(*(reinterpret_cast<char*>(pPixelPointer+2)));
    g = static_cast<int>(*(reinterpret_cast<char*>(pPixelPointer+1)));
    b = static_cast<int>(*(reinterpret_cast<char*>(pPixelPointer+0)));
}

inline int ArrPos(int x, int y)
{
    // y + height * x
    return (x + m_size_x * y);
} 

inline void setPixel(int x, int y, int r, int g, int b)
{
    int pos = ArrPos(x,y);
    red[pos] = r;
    green[pos] = g;
    blue[pos] = b;
}

void checkPerfMult(void)
{
    int m_nBytesPerPixel = 4;
    int nPitch = 4;
    void* pMemVoid = (void*)largeChunk;
    char* pPixelPointer;
    for ( int x = 0; x < m_nSizeX; x++ ) 
    {
        for ( int y = 0; y < m_nSizeY; y++ ) 
        {
            // (x*bytes) + (y * sizex)
            int r;
            int g;
            int b;
            long lMemoryPixelOffset = ((long)x * m_nBytesPerPixel) + ((long)y * nPitch );
            pPixelPointer = (reinterpret_cast<char*> (pMemVoid) + (lMemoryPixelOffset)) ;

            pixelToRGB(pPixelPointer, r, g, b);
            setPixel(x,y,r,g,b);
        }
    } 
}

void* getImageStart(void)
{
    return largeChunk;
}

void checkPerfAdd(void)
{
    // jetzt der Zugriff
    RGBPixel32* imageIterator = reinterpret_cast<RGBPixel32*>(getImageStart()); // Hier den Start des Bildes im Speicher bestimmen
    int targetIterator = 0;
    for( int y = 0; y < m_nSizeY; y++ )
    {
        for( int x = 0; x < m_nSizeX; x++ ) // hier wird imageStart immer um ein ganzes Pixel weiter geschoben
        {
//            setPixel(x, y, imageIterator->r, imageIterator->g, imageIterator->b);
            red[targetIterator] = imageIterator->r;
            green[targetIterator] = imageIterator->g;
            blue[targetIterator] = imageIterator->b;
            imageIterator++;
            targetIterator++;
        }
    } 
}

char* getStartOfRedMemory()
{
    return red;
}

char* getStartOfGreenMemory()
{
    return green;
}

char* getStartOfBlueMemory()
{
    return blue;
}

RGBPixel32* getStartOfRGBXMemory()
{
    return reinterpret_cast<RGBPixel32*>(getImageStart());
}

void checkPerfMemCpy_s()
{
    char* redmemory  = getStartOfRedMemory();
    char* bluememory = getStartOfBlueMemory();
    char* greenmemory = getStartOfGreenMemory();  

    RGBPixel32* RGBXMemory = getStartOfRGBXMemory();

    size_t ColorIndex=0;
    size_t RGBXIndex=0;
    int  number_of_pixels = m_nSizeX*m_nSizeY;

    for( int i=0; i<number_of_pixels; i++)
    {
        memcpy_s(redmemory  + ColorIndex,1,((char*)RGBXMemory + RGBXIndex) + 2,1);
        memcpy_s(bluememory + ColorIndex,1,((char*)RGBXMemory + RGBXIndex) + 1,1);
        memcpy_s(greenmemory+ ColorIndex,1,((char*)RGBXMemory + RGBXIndex) + 0,1);
        RGBXIndex++;
        ColorIndex++;
    } 
}

void checkPerfMemCpy()
{
    char* redmemory  = getStartOfRedMemory();
    char* bluememory = getStartOfBlueMemory();
    char* greenmemory = getStartOfGreenMemory();  

    RGBPixel32* RGBXMemory = getStartOfRGBXMemory();

    size_t ColorIndex=0;
    size_t RGBXIndex=0;
    int  number_of_pixels = m_nSizeX*m_nSizeY;

    for( int i=0; i<number_of_pixels; i++)
    {
        memcpy(redmemory  + ColorIndex,((char*)RGBXMemory + RGBXIndex) + 2,1);
        memcpy(bluememory + ColorIndex,((char*)RGBXMemory + RGBXIndex) + 1,1);
        memcpy(greenmemory+ ColorIndex,((char*)RGBXMemory + RGBXIndex) + 0,1);
        RGBXIndex++;
        ColorIndex++;
    } 
}

int main( void )
{
    const int runs = 100;
    {
        cout << "Copying with Mul based address calculation: ";
        Timer t;
        for (int i = 0; i<runs; i++)
        {
            checkPerfMult();
        }
    }
    cout << endl;
    {
        cout << "Copying with Add based address calculation: ";
        Timer t;
        for (int i = 0; i<runs; i++)
        {
            checkPerfAdd();
        }
    }    
    cout << endl;
    {
        cout << "Copying with memcpy_s based address calculation: ";
        Timer t;
        for (int i = 0; i<runs; i++)
        {
            checkPerfMemCpy_s();
        }
    }
    cout << endl;
    {
        cout << "Copying with memcpy based address calculation: ";
        Timer t;
        for (int i = 0; i<runs; i++)
        {
            checkPerfMemCpy();
        }
    }
    cout << endl;
}

Und hier die Compileroptionen von VisualC++ 2008:
/O2 /Ob2 /Oi /Ot /GL /I "C:\work\learning\playGroundForCpp\playGroundForCpp" /D "WIN32" /D "NDEBUG" /D "_CONSOLE" /D "_UNICODE" /D "UNICODE" /FD /EHsc /MD /Gy /Fo"Release\\" /Fd"Release\vc90.pdb" /W3 /nologo /c /Zi /TP /errorReport:prompt

Bitte beachten: Ich teste nur auf einem Laptop mit lahmem Speicher und 1.6GHz CPU

EDIT: Die Messungen sind mit dem Release Build gemacht.