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]
nachsum(mulMat)
irritiert - das würde darauf hindeuten dass auch hier ein Vektor zurückkommt.Und zuletzt müssen die beiden Ergebnis-
Mat
s 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 AdditionenLesen/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 AdditionenAlso 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.
- Eine N Elemente grosse
-
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.