当前位置:网站首页>Efficiency difference between row first and column first traversal of mat data types in opencv
Efficiency difference between row first and column first traversal of mat data types in opencv
2022-07-05 21:35:00 【MrL_ JJ】
List of articles
One 、 How arrays are stored in memory
Array is the basis of data structure , The reason for this is that arrays reflect the physical structure of memory . In memory , Arrays are continuously distributed . And in the program , It is often necessary to allocate a continuous piece of space in memory to use . for example , In the neighborhood of image processing , Familiar with opencv There is a data type in Mat, We usually use Mat To store image data .Mat Is a two-dimensional array , Two for Loop through the values of each pixel on the image . Some people are used to traversing by line first , Some people like to traverse by column first , On the surface , The time complexity of these two methods is O(nm)(n Indicates the height of the image ,m Represents the width of the image ), But are they all O(nm) Well ?
Two 、 Code examples and results
The code of column first traversal is as follows ( Example ):
Mat src = imread("image0.jpg", IMREAD_GRAYSCALE);
if (!src.empty())
imshow("src", src);
int nums = 10;
while (nums)
{
double t = (double)getTickCount();
for (int i = 0; i < src.cols; i++)
{
for (int j = 0; j < src.rows; j++)
{
uchar srcValue = src.at<uchar>(j, i);
}
}
t = ((double)getTickCount() - t) / getTickFrequency(); // For the time , The unit is seconds
cout << "time:" << t<<"ms"<<endl;
nums--;
}
Through a cycle , Repeat the test 10 Time , The time-consuming of column priority traversal is printed through the console as follows :
Line first traversal code is as follows ( Example ):
Mat src = imread("image0.jpg", IMREAD_GRAYSCALE);
if (!src.empty())
imshow("src", src);
int nums = 10;
while (nums)
{
double t = (double)getTickCount();
for (int i = 0; i < src.rows; i++)
{
for (int j = 0; j < src.cols; j++)
{
uchar srcValue = src.at<uchar>(i, j);
}
}
t = ((double)getTickCount() - t) / getTickFrequency(); // For the time , The unit is seconds
cout << "time:" << t<<"ms"<<endl;
nums--;
}
Again , Row first traversal also passes through a loop , Repeat the test 10 Time , The time consumption is printed as follows through the console :
Through the above tests, we can find that , Row first traversal is faster than column first .
3、 ... and . analysis
1. CPU Cache ( English :CPU Cache): In computer system ,CPU Cache is a component used to reduce the average time required by the processor to access memory . When the processor makes a memory access request , It will first check whether there is request data in the cache . If there is ( hit ), Return the data directly without access to memory ; If it doesn't exist ( invalid ), First, load the corresponding data in memory into the cache , Return it to the processor . Why caching works , The main reason is that the access to memory when the program is running is local (Locality) features . This locality includes both spatial locality (Spatial Locality), It also includes time locality (Temporal Locality). Use this locality effectively , Cache can achieve a very high hit rate .( Baidu Encyclopedia explains ).
2. Virtual memory : Virtual memory is used by the operating system to manage memory , Expand physical memory , Its function is to replace part of the work of physical memory to run programs , Let the operating system run more programs , Perform more tasks at the same time .
3. The storage structure of two-dimensional array in memory is shown in the figure below : Data is stored in memory in a row first manner .
4. The image size of the code test is 4096X1200, Bit depth is 8, Here's the picture . The reason why row first traversal is faster than column first , Because cpu When accessing the memory address , The first thing to access is virtual memory , Check TLB, Map to the corresponding physical address for data access . If hit , Will get its physical address , After that, I will visit cache, If cache There is data to access in , Then this visit is over , without , Just look in memory , And update the cache; If TLB Miss hit , Then the system kernel will call the missing page exception handler to handle , Page replacement and other operations will be carried out in this process , Finally get the data to be accessed . In the physical address of memory , Two dimensional arrays are stored in row first order , The size of the test image data is 4096X1200 byte , Suppose the memory page is 4096 byte , Then traverse by line first , After traversing a line, the page is broken once , The whole process only needs to be interrupted 1200 Next page missing exception , Make page replacement . And traverse by column first , Every time you traverse an element, you break the page missing exception , The whole process 4096X1200 Interrupt times , As one can imagine , The interruption time of traversal by column first is much larger than that of traversal by row first . In reality, physical memory is generally sufficient , The system allocates far more page memory 4096 byte , So there won't be so many page breaks . Empathy , If you check TLB hit , After getting its physical address, you will visit cache, If cache There is no data to access , Just look in memory , And update the cache; Due to the storage mode of two-dimensional array in memory , Traverse the access by column first cache The hit rate of is lower than that of traversing by row first .
in summary : Row first traversal is faster than column first .
边栏推荐
- ESP32
- MySQL deep paging optimization with tens of millions of data, and online failure is rejected!
- 2022-07-03-cka- latest feedback from fans
- Selenium finds the contents of B or P Tags
- Why can't Chinese software companies produce products? Abandon the Internet after 00; Open source high-performance API gateway component of station B | weekly email exclusive to VIP members of Menon w
- R language learning notes
- Introduction to TS, constructor and its this, inheritance, abstract class and interface
- R语言【数据管理】
- ESP32
- [case] Application of positioning - Taobao rotation map
猜你喜欢
Some common processing problems of structural equation model Amos software
XML modeling
[case] Application of element display and hiding -- element mask
Xlrd common operations
Emotional analysis of wechat chat records on Valentine's day based on Text Mining
How to send samples when applying for BS 476-7 display? Is it the same as the display??
第05章_存储引擎
MySQL 千万数据量深分页优化, 拒绝线上故障!
Uni app Bluetooth communication
让开发效率飞速提升的跨端方案
随机推荐
Zhang Lijun: la pénétration de l’incertitude dépend de quatre « invariants»
selenium 获取dom内验证码图片
Teach yourself to train pytorch model to Caffe (I)
Emotional analysis of wechat chat records on Valentine's day based on Text Mining
事项研发工作流全面优化|Erda 2.2 版本如“七”而至
1.2 download and installation of the help software rstudio
100 cases of shell programming
Environment configuration problem record
Utils/index TS tool function
KingbaseES V8R3集群维护案例之---在线添加备库管理节点
Making global exception handling classes with aspect
GCC9.5离线安装
leetcode:1755. Sum of subsequences closest to the target value
Recursive query of multi-level menu data
Chap2 steps into the palace of R language
Explain various hot issues of Technology (SLB, redis, mysql, Kafka, Clickhouse) in detail from the architecture
The transformation based on vertx web sstore redis to realize the distributed session of vertx HTTP application
Zhang Lijun: penetrating uncertainty depends on four "invariants"
@Validated basic parameter verification, grouping parameter verification and nested parameter verification
Exercise 1 simple training of R language drawing