对于> 4D阵列MatLab造成巨大的性能损失？

Question

介绍

我有一个循环数十亿(数万亿)次数的算法并操纵存储在7维[10x10x10x10x10x10x10]中的矩阵,我发现访问7维矩阵中的元素非常慢,很好奇,因为我运行了一些测试来识别访问多维矩阵元素的性能.

假设

我提醒MATLAB的使用引擎盖下的线性索引和我的一个朋友说,性能损失可能是由于"正常"索引线性索引引擎盖下的转换来源.

测试方法

为了测试这个假设,我测试了使用线性索引和2D到7D矩阵的常规索引访问元素.我改变了我访问的元素以及我访问的矩阵大小,即每个维度的长度,但这并没有显着改变结果.我用于测试的文件如下所示.使用的硬件是Intel(R)Xeon(R)CPU E5-1620 v2 @ 3.70 GHz,16GB RAM.MatLab版本是R2013B.

结果

Normal indexing 2D: 0.073659s
Linear indexing 2D: 0.064026s
Normal indexing 3D: 0.050719s
Linear indexing 3D: 0.064096s
Normal indexing 4D: 0.055674s
Linear indexing 4D: 0.062112s
Normal indexing 5D: 15.689907s
Linear indexing 5D: 5.265076s
Normal indexing 6D: 16.660496s
Linear indexing 6D: 5.295958s
Normal indexing 7D: 17.029072s
Linear indexing 7D: 5.291139s

在高达4D矩阵的性能方面,与线性索引相比,正常索引似乎非常相似.对于3D和4D矩阵,似乎使用正常索引略微优选.高于4D矩阵线性索引比正常索引更优选,但正常索引和常规索引都会受到巨大的性能损失(〜两个数量级).

结论

这个故事的寓意是在运行MatLab时要仔细考虑矩阵中超过四个维度的需求,以实现高性能(除了显而易见的事实,C++例如对于大多数应用程序来说更快等等,但这可能是另一个讨论) .

问题(S)

如标题所示:当矩阵超过四维时,这种巨大的性能损失的(潜在)原因是什么？其他语言(如C++)也证明了这种行为吗？

用于测试的代码

clear all
clc

% Number if iterations 
n=10000000;

A = rand(10,10);
k1=sub2ind(size(A),3,2);
fprintf('\n')
tic
for ii=1:n
    A1=A(3,2);
end
a=toc;
fprintf('Normal indexing 2D: %fs\n',a)


tic
for ii=1:n
    A2=A(k1);
end
a=toc;
fprintf('Linear indexing 2D: %fs\n',a)

B = rand(10,10,10);
k2=sub2ind(size(B),3,2,1);

tic
for ii=1:n
    B1=B(3,2,1);
end
a=toc;
fprintf('Normal indexing 3D: %fs\n',a)
tic
for ii=1:n
    B2=B(k2);
end
a=toc;
fprintf('Linear indexing 3D: %fs\n',a)

C = rand(10,10,10,10);
k3=sub2ind(size(C),3,2,1,10);

tic
for ii=1:n
    C1=C(3,2,1,10);
end
a=toc;
fprintf('Normal indexing 4D: %fs\n',a)
tic
for ii=1:n
    C2=C(k3);
end
a=toc;
fprintf('Linear indexing 4D: %fs\n',a)

D = rand(10,10,10,10,10);
k4=sub2ind(size(D),3,2,1,10,1);

tic
for ii=1:n
    D1=D(3,2,1,10,1);
end
a=toc;
fprintf('Normal indexing 5D: %fs\n',a)
tic
for ii=1:n
    D2=D(k4);
end
a=toc;
fprintf('Linear indexing 5D: %fs\n',a)

E = rand(10,10,10,10,10,10);
k5=sub2ind(size(E),3,2,1,10,1,2);

tic
for ii=1:n
    E1=E(3,2,1,10,1,2);
end
a=toc;
fprintf('Normal indexing 6D: %fs\n',a)
tic
for ii=1:n
    E2=E(k5);
end
a=toc;
fprintf('Linear indexing 6D: %fs\n',a)

F = rand(10,10,10,10,10,10,10);
k6=sub2ind(size(F),3,2,1,10,1,2,3);

tic
for ii=1:n
    F1=F(3,2,1,10,1,2);
end
a=toc;
fprintf('Normal indexing 7D: %fs\n',a)
tic
for ii=1:n
    F2=F(k6);
end
a=toc;
fprintf('Linear indexing 7D: %fs\n',a)

Answer 1

在某些时候,必须有一个值的线性地址,因为这是大多数处理器的工作方式.处理器非常适合从单个位置获取数据.

在整个答案中,术语矩阵和数组将可互换使用.

单维矩阵
单维数组的地址计算:

  address = starting_array_address + (index * sizeof(object_type));

的object_type的是对象,诸如类型unsigned char或int.

2维矩阵
表示为1D数组的2D数组中值的索引位置计算如下:

  index = Dimension2_value * Dimension1_capacity + Dimension1_value;

可以使用单维对象的索引和等式计算值的地址.

3维矩阵
Dimension3_value可以表示为立方体内的平面数.
因此,这延伸了另一个术语:

index = Dimension_3_value * (Dimension2_capacity)
      + Dimension2_value * Dimension1_capacity
      + Dimension1_value;

4D及以上矩阵4D及以上矩阵 的计算可以以类似的方式扩展.

指数计算的瓶颈是乘法.

某些平台可以并行计算这些术语,从而提供一些速度优势.

速度推测
我猜Matlab已经优化了2D和3D矩阵的索引计算,但不是更大的.2D和3D矩阵比4D和更大的使用更广泛.

典型的优化是将每个项的值分配给不同的寄存器,然后对寄存器求和.这是为了使值尽可能靠近处理器.某些处理器可能没有足够的寄存器用于4D计算,因此编译器可能必须将值放在临时存储器(处理器外部)中,从而降低性能.

获取值
对于1D,2D和3D矩阵,处理器可能能够将数据包含在其数据高速缓存中,从而加速性能.随着尺寸的增加,矩阵的大小必须缩小,以使其适合处理器的数据缓存.任何时候值都不在缓存中称为缓存未命中,处理器必须从处理器外部的内存加载值.根据数据的重新加载方式,它可能会重新加载"条带"数据或更多.在任何一种情况下,都会降低性能.

总结
计算索引会为矩阵的每个附加维度花费更多的处理时间.乘法是计算的瓶颈(即使它们可能是一条指令,乘法也需要比加法更长).尽管可以并行执行索引计算的每个项,但是可能没有足够的线程或核或处理单元来一次执行所有维的索引计算.可能没有足够的寄存器或数据缓存来进行最佳计算,因此处理器必须从外部存储器中取出,从而降低性能.如果数据项不在处理器的数据高速缓存中,则处理器将浪费时间重新加载整个或部分数据高速缓存(浪费时间,因为处理器可能正在执行计算而不是重新加载高速缓存).

通常,对决定因素(较小的子矩阵)的操作通常通常导致比在大的多维矩阵上操作更好的性能.