为什么在MatLab中使用超过4维数组会导致巨大的性能损失？

Question

为什么在MatLab中使用超过4维数组会导致巨大的性能损失？

c++performancematlabmultidimensional-arrayindexing

5

介绍

我有一个算法，需要循环数十亿（万亿）次，并操作一个存储在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)

- EJG89

只是一个小建议 - 你甚至不需要将 toc 保存到 a 中！ - Yvon

我知道，但为了绘图，我首先将它存储到另一个变量中的tocs中，这确实是有点冗余的代码。 - EJG89

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Thomas Matthews · Accepted Answer

大多数处理器都需要一个值的线性地址，这是因为它们擅长从单个位置获取数据。

在本答案中，“矩阵”和“数组”一词可以互换使用。

单维矩阵
对于单维数组的地址计算：

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

object_type 是对象的类型，例如 unsigned char 或 int。

二维矩阵
将一个以一维数组表示的二维数组中的值的索引位置计算方法如下：

  index = Dimension2_value * Dimension1_capacity + Dimension1_value;

通过索引和单维对象的方程，可以计算值的地址。

三维矩阵
Dimension3_value可以表示为立方体内平面的数量。
因此，这个方程式通过另一个术语进行扩展：

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

四维及以上矩阵 四维及以上矩阵的计算可以采用类似的方法进行扩展。

索引计算中的瓶颈在于乘法。

一些平台可以并行计算术语，从而提高速度。

速度推测
我猜Matlab已经对二维和三维矩阵进行了优化，但对更大的矩阵没有进行优化。二维和三维矩阵比四维及以上的矩阵更广泛地使用。

通常的优化方法是将每个术语的值分配给不同的寄存器，然后将寄存器的值相加。这是为了尽可能让值靠近处理器。某些处理器可能没有足够的寄存器来进行四维计算，因此编译器可能需要将值放置在临时内存（处理器外部），从而降低性能。

获取值
对于一维、二维和三维矩阵，处理器可以将数据保存在其数据缓存中，从而加快性能。随着维数增长，矩阵的大小必须缩小，以便适合处理器的数据缓存中。任何时候，如果一个值不在缓存中，则称为缓存未命中，处理器必须从处理器外部的内存加载该值。根据重新加载数据的方式，它可能会重新加载“条”数据或更多数据。在任何情况下，这都会降低性能。

总结
每增加一个矩阵维度，索引计算需要更多的处理时间。乘法是计算的瓶颈（即使它们可能是一条指令，乘法所需的时间比加法长）。虽然索引计算的每个术语可以并行执行，但可能没有足够的线程、核心或处理单元来同时执行所有维度的索引计算。可能没有足够的寄存器或数据缓存进行最优计算，因此处理器将不得不从外部内存中获取数据，从而降低性能。如果数据项不在处理器的数据缓存中，处理器将浪费时间重新加载整个或部分数据缓存（时间被浪费是因为处理器可以执行计算而不是重新加载缓存）。

通常情况下，对行列式（较小的子矩阵）进行操作通常比对大型多维矩阵进行操作具有更好的性能。