OpenCV's SVD is slow

Tweet

SVD (singular value decomposition) of OpenCV 2.3 and later

LAPACK was used for OpenCV 2.2 and former. OpenCV 2.3 and later use original implementation.

Computation speed of OpenCV 2.3 and later is slower than that of OpenCV and former.
Significant slow down of SVD in OpenCV 2.3 #4313
solve CV_SVD very slow in the latest opencv #7563
SVD performance issue #7917

OpenCV 3.1's SVD is implemented in JacobiSVDImple_ in lapack.cpp. I don't know the reason why this happens. I first thought that the process when the singular value is zero makes the computation speed slow. So, I checked the computation speed of the matrix filled with 1 and that of the matrix filled with random values.

Source code of random matrix

const int ROW = 2000;
const int COL = 2000;
RNG gen(getTickCount());
Mat mat(ROW, COL, CV_64F);
gen.fill(mat, RNG::UNIFORM, 0.0, 1.0);
int64 start = getTickCount();
cout << "start = " << start << endl;
SVD svd(mat);
int64 end = getTickCount();
cout << "end = " << end << endl;
int calctime = (int)((end - start) * 1000 / getTickFrequency());
cout << "duration = " << calctime << " [msec]" << endl;
cout << "W = " << endl << svd.w.rowRange(Range(0, 9)) << endl;

Source code of 1 matrix

const int ROW = 2000;
const int COL = 2000;
Mat mat = Mat::ones(ROW, COL, CV_64F);
int64 start = getTickCount();
cout << "start = " << start << endl;
SVD svd(mat);
int64 end = getTickCount();
cout << "end = " << end << endl;
int calctime = (int)((end - start) * 1000 / getTickFrequency());
cout << "duration = " << calctime << " [msec]" << endl << endl;
cout << "W = " << endl << svd.w.rowRange(Range(0, 9)) << endl;

Benchmark

• Windows 10 Home
• 64 bit
• Intel Core i7-4710HQ CPU @ 2.50GHz 2.50GHz
• 16.0 GB
• Visual Studio Community 2015
• Python 3.6.3
• MATLAB R2017b
• numpy 1.13.3
• Numerical Recipes in C 3rd edition
• Eigen 3.3.4
• OpenCV 3.3.0 [Python]
• OpenCV 3.1 [C/C++] 64bit
• OpenCV 2.2 [C/C++] 32bit

Matrix size 2000-times-2000

Random matrix

Ones matrix

Summary

Sample source code of other library

MATLAB and numpy are optimized for CPU to get high performance.

Conclusion: OpenCV 3.1 is 3600 times slower than OpenCV 2.2
OpenCV 3.1's SVD is 3600 times slower than OpenCV 2.2's SVD #10084

Denormal number

If there is denormal number (subnormal number) in floating point variables, the computation speed will be extremely bad. You know, the computation speed becomes bad when there is NaN (Not a Number) such as infinity (INF) caused by division-by-zero, or NaN caused by sqrt or log with minus values.
https://en.wikipedia.org/wiki/Denormal_number
https://stackoverflow.com/questions/9314534/why-does-changing-0-1f-to-0-slow-down-performance-by-10x

Below is the result when the denormal number is forced to be zero. Two sentences are added as follows.
#include <xmmintrin.h>
_mm_setcsr(_mm_getcsr() | 0x8040);

• Windows 10 Home
• 64 bit
• Intel Core i7-4710HQ CPU @ 2.50GHz 2.50GHz
• 16.0 GB
• Visual Studio Community 2015
• Numerical Recipes in C 3rd edition
• Eigen 3.3.4
• OpenCV 3.1 [C/C++] 64bit
• OpenCV 2.2 [C/C++] 32bit

Matrix size 2000-times-2000

Random matrix

Ones matrix

Summary

Conclusion: OpenCV 3.1 is 70 times slower than OpenCV 2.2

Reliability

First, second, and third singular values of 2000-by-2000 matrix. Note that random matrix is different from each other, so the slight difference of values does not matter.

Conclusion: Are you okay, Eigen?

OpenMP

Some of the libraries do parallel computing. Visual Studio of above results are of default settings, and the belows enabled OpenMP.

[C/C++]-[Language]-[Open MP Support] set [Yes]
[C/C++]-[Code Generation]-[Enable Enhanced Instruction Set] set [Advanced Vector Extensions 2]

Conclusion: SVD is not suitable for parallel computing, thus the computation speed does not differ so much when either using parallel computing or not, even if the software library partially uses parallel computing.

Qiita

This webpage is the entry of 2017/Dec/6th, Japanese Qiita OpenCV advent calender 2017.
https://qiita.com/advent-calendar/2017/opencv

Aftermath

Upcoming version of OpenCV may include the LAPACK implementation of SVD.
https://github.com/opencv/opencv/wiki/OE-12.-Lapack

Back