我已经读过,例如,如果我有一个for
遍历矩阵索引的双循环,那么将列运行索引放在外循环中会更有效。例如:
a=zeros(1000);
for j=1:1000
for i=1:1000
a(i,j)=1;
end
end
如果我有三个或更多for
循环,最有效的编码方式是什么?
例如:
a=zeros(100,100,100);
for j=1:100
for i=1:100
for k=1:100
a(i,j,k)=1;
end
end
end
我已经读过,例如,如果我有一个for
遍历矩阵索引的双循环,那么将列运行索引放在外循环中会更有效。例如:
a=zeros(1000);
for j=1:1000
for i=1:1000
a(i,j)=1;
end
end
如果我有三个或更多for
循环,最有效的编码方式是什么?
例如:
a=zeros(100,100,100);
for j=1:100
for i=1:100
for k=1:100
a(i,j,k)=1;
end
end
end
简短的回答,你想在最里面的循环上有最左边的索引。在您的示例中,循环索引为 k、j、i,数组索引为 i、j、k。这与 MATLAB 如何在内存中存储不同维度有关。有关更多信息,请参阅此 reddit 帖子的 #13 。
一个稍长的答案解释了为什么让最左边的索引变化最快会更有效。您需要了解两件关键的事情。
首先,MATLAB(和 Fortran,但不是 C 和大多数其他编程语言)以“列主要顺序”将数组存储在内存中。例如,如果 A 是 2 x 3 x 10 矩阵,则条目将按顺序存储在内存中
A(1,1,1)
A(2,1,1)
A(1,2,1)
A(2,2,1)
A(1,3,1)
A(2,3,1)
A(1,1,2)
A(2,1,2)
...
A(2,3,10)
这种列主顺序的选择是任意的——我们可以很容易地采用“行主顺序”约定,实际上这就是在 C 和其他一些编程语言中所做的。
您需要了解的第二件事是现代处理器不会一次访问一个位置的内存,而是加载和存储 64 甚至 128 个连续字节(8 或 16 个双精度浮点数)的“高速缓存行”一次从记忆中。这些数据块临时存储在快速内存缓存中,并根据需要写回。(实际上,缓存架构现在相当复杂,有多达 3 或 4 级缓存,但基本思想可以用我年轻时计算机所拥有的那种单级缓存来解释。)
现在,假设是一个包含 10,000 行和列的数组,我正在遍历所有条目。
如果循环嵌套使得最里面的循环更新行下标,则数组条目将按 A(1,1)、A(2,1)、A(3,1)、... 的顺序访问访问第一个条目 A(1,1),系统将从主存带入一个包含 A(1,1), A(2,1), ..., A(8,1) 的缓存行. 最内层循环的接下来 8 次迭代处理此数据,无需任何额外的主存储器传输。
如果在替代方案中,我们构造循环使得列索引在最内层循环中变化,那么 A 的条目将按 A(1,1)、A(1,2)、A(1,3) 的顺序访问), ... 在这种情况下,第一次访问会将 A(1,1), A(2,1), ..., A(8,1) 从主存带入高速缓存,但是 7/8这些条目不会被使用。在第二次迭代中对 A(1,2) 的访问会从主存中带来另外 8 个条目,依此类推。当代码开始处理矩阵的第 2 行时,A(2,1) 条目很可能会从缓存中清除,以便为其他需要的数据让路。结果,代码产生了 8 倍的流量。
一些优化编译器能够自动重组循环以避免这个问题。
许多用于矩阵乘法和分解的数值线性代数算法可以被优化,以根据编程语言有效地使用行优先或列优先排序方案。以错误的方式执行此操作会对性能产生重大的负面影响。