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.


Log in to reply