Efficiency difference between row first and column first traversal of mat data types in opencv

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 .