extreme performance difference of in place vs intermediate saving



  • Hey, so I was implementing some functionalitys for image processing and wanted to make some code more reusable, instead of doing all operations in place I decided to save some intermediate values in a opencv::Mat (also tried a vector with the same result). However this change caused the execution time of my program to go from around 5 seconds to 30 seconds. Is the overhead of writing to a vector/Mat so much bigger? I was expecting such a big difference.
    I tried using a single temporary matrix so it wouldnt have to be recreated in memory but that didnt really change anything. I would have expected writing to a vector/Mat to be just as fast as writing to a variable, is there something i`m not seeing?

    This function gets called for every pixel in the image (I know there are better ways to do this)

    Original

    cv::Mat_<float> convolute(int colpos, int rowpos,const Mat_<float> &src,Mat_<float> &dest,const cv::Mat_<float> &kernel){
        //get values for each position in kernel
        int kernelCols = kernel.cols;
        int kernelRows = kernel.rows;
    
        int middleCol = kernelCols % 2 != 0 ? (kernelCols - 1) / 2 : kernelCols / 2;
        int middleRow = kernelRows % 2 != 0 ? (kernelRows - 1) / 2 : kernelRows / 2;
    
        float sum = 0;
        for(int col = 0 ; col < kernelCols; col++){
            for(int row = 0; row < kernelRows; row++){
                int offsetCols = col - middleCol;
                int offsetRow = row - middleRow;
                // get value at offset in imge
                float valAtPos = getValueAtPos(colpos + offsetCols, rowpos + offsetRow, src);
                float targetVal = valAtPos * kernel.at<float>(row, col);
                sum += targetVal;
            }
        }
        dest.at<float>(rowpos, colpos) = sum;
    

    Slow code

    Mat getMatForPixel(int colAnchor, int rowAnchor, int matCols,int matRows, const Mat &src){
        Mat dest = Mat::zeros(Size(matRows, matCols), CV_32FC1);
    
        int middleCol = matCols % 2 != 0 ? (matCols - 1) / 2 : matCols / 2;
        int middleRow = matRows % 2 != 0 ? (matRows - 1) / 2 : matRows / 2;
    
        for(int col = 0; col < dest.cols; col++){
            for(int row = 0; row < dest.rows; row++){
                int offsetCol = col - middleCol;
                int offsetRow = row - middleRow;
                dest.at<float>(row, col) = getValueAtPos(colAnchor + offsetCol, rowAnchor  + offsetRow, src);
            }
        }
        return dest;
    }
    
    cv::Mat_<float> convolute(int colpos, int rowpos,const Mat_<float> &src,Mat_<float> &dest,const cv::Mat_<float> &kernel){
        Mat_<float> convolutionMat = getMatForPixel(colpos, rowpos,kernel.cols, kernel.rows, src);
        //multiplicate convolution matrix with kernel values
        Mat_<float> mulMat = convolutionMat.mul(kernel); 
        // get sum of all values
        float sum = cv::sum(mulMat)[0];
        dest.at<float>(rowpos, colpos) = sum;
        return dest;
    }
    


  • Deutsche antworten sind übrigens in Ordnung, habe nicht gesehen, dass es sich um ein deutsches Forum handelt 🙂



  • @doepnern sagte in extreme performance difference of in place vs intermediate saving:

    Deutsche antworten sind übrigens in Ordnung, habe nicht gesehen, dass es sich um ein deutsches Forum handelt 🙂

    Ja, das kann man schnell übersehen, auch weil ja schon der Registrierungsprozess in deutscher Sprache ist ...



  • Überleg dir mal was das langsamere Programm macht. Sei N = kernel.cols * kernel.rows, dann muss das langsamere Programm...

    Für getMatForPixel:

    • Eine N Elemente grosse Mat für das Ergebnis anfordern (=dynamische Speicheranforderung)
    • Diese N Element mit 0 beschreiben
    • N Elemente aus src lesen ...
    • ...und in die Ergebnis-Mat schreiben
    • Die Ergebnis-Mat zurückgeben (sollte per (N)RVO optimierbar und daher quasi gratis sein)

    Für convolutionMat.mul:

    • Eine N Elemente grosse Mat für das Ergebnis anfordern (=dynamische Speicheranforderung)
    • N Elemente aus convolutionMat lesen
    • N Elemente aus kernel lesen
    • Die 2xN Elemente paarweise multiplizieren
    • Die N Produkte in die Ergebnis-Mat schreiben
    • Die Ergebnis-Mat zurückgeben (siehe oben)

    Für sum(mulMat):

    • N Elemente aus mulMat lesen
    • Die N Elemente addieren
    • Das Ergebnis zurückgeben

    Und ganz zuletzt wird 1 Element in dest geschrieben.

    Wobei mich hier das [0] nach sum(mulMat) irritiert - das würde darauf hindeuten dass auch hier ein Vektor zurückkommt.

    Und zuletzt müssen die beiden Ergebnis-Mats natürlich wieder freigegeben werden.

    Wohingegen der schnelle Code auskommt mit:

    • N Elemente aus src lesen
    • N Elemente aus kernel lesen
    • Die 2xN Elemente paarweise multiplizieren
    • Die N Produkte addieren
    • Die Summe in dest schreiben

    Wenn ich mich nicht vertan habe also beim langsamen Code

    2 dynamische Speicheranforderungen
    4N Elemente lesen
    3N + 1 Elemente schreiben
    N-1 Multiplikationen
    N-1 Additionen

    Lesen/Schreiben/Mul/Add ist alles in der selben Grössenordnung, Speicher Anforderung + Freigeben ist ganz grob Grössenordnung 100 langsamer. Also in Summe etwa 9N + 200 Zwetschkenknödel. Bzw. 9N + 300 falls sum auch dynamisch Speicher für das Ergebnis anfordert.

    Und beim schnellen

    0 dynamische Speicheranforderungen
    2N Elemente lesen
    1 Element schreiben
    N-1 Multiplikationen
    N-1 Additionen

    Also in Summe ca. 4N.

    Wenn man alles weitere ignoriert, also dass die Schleifen auch Zeit brauchen, dass getValueAtPos bzw. Mat::at auch multiplizieren und addieren müssen, sowie die ganzen komplizierten Effekte von Cache, Prefetcher etc., dann wäre bei einer Kernel Grösse von 3x3 ~ 4x4 Elemente ca. der von dir beobachtete Slowdown Faktor 6 zu erwarten.



  • Danke für die sehr ausführliche Antwort!
    Ich schätze ich habe die Anzahl an zusätzlichen Operationen unterschätzt. Weißt du wie es prinzipiell ist wenn man eine temporäre Mat als Referenz in die funktion gibt, welche wiederverwendet wird. Das müsste zumindest die dynamischen allokationen verhindern oder?



  • @doepnern sagte in extreme performance difference of in place vs intermediate saving:

    Weißt du wie es prinzipiell ist wenn man eine temporäre Mat als Referenz in die funktion gibt, welche wiederverwendet wird. Das müsste zumindest die dynamischen allokationen verhindern oder?

    Ich denke ja, so lange die Grösse sich nicht ändert.
    Du kannst ja einfach mal mit dem Debugger reinsteppen.

    Und BTW: wie gross war der Kernel in dem Test wo du Faktor 6 Slowdown gesehen hast?



  • Der kernel war 3x3, tatsächlich scheint die dynamische speicheranforderung das größte Problem gewesen zu sein. Ich hatte nicht bedacht, dass mat.mul auch Speicher anfordert. Ich habe nun eine temporäre matrix für die gesamte Operation verwendet und der unterschied ist nur noch gering.
    In place: 661.209ms,
    Mit dynamischen Speicheranfragen mit Matrixzwischenschritt; 3577.54ms
    Ohne dynamische Speichenanfragen mit Matrixzwischenscritt: 1379ms
    Vielen dank noch mal für deine Hilfe, war sehr hilfreich!



  • @doepnern Hinweis am Rande: Wenn du bei solchen Sachen Wert auf Performance legst, solltest du auch schauen, ob dein Faltungskern nicht eventuell separierbar ist, und das entsprechend ausnutzen.

    Falls du as nicht ohnehin schon machst.


Anmelden zum Antworten