下标索引和线性索引之间的性能差异

Question

我在MATLAB中有一个二维矩阵，使用两种不同的方式来访问它的元素。一种是基于下标索引，另一种是基于线性索引。我通过以下代码来测试两种方法：

N = 512; it = 400; im = zeros(N);
%// linear indexing
[ind_x,ind_y] = ndgrid(1:2:N,1:2:N);
index = sub2ind(size(im),ind_x,ind_y);

tic
for i=1:it
    im(index) = im(index) + 1;
end
toc %//cost 0.45 seconds on my machine (MATLAB2015b, Thinkpad T410)

%// subscript indexing
x = 1:2:N;
y = 1:2:N;

tic
for i=1:it
    im(x,y) = im(x,y) +1;
end
toc %// cost 0.12 seconds on my machine(MATLAB2015b, Thinkpad T410)

%//someone pointed that double or uint32 might an issue, so we turn both into uint32

%//uint32 for linear indexing
index = uint32(index);
tic
for i=1:it
    im(index) = im(index) +1;
end
toc%// cost 0.25 seconds on my machine(MATLAB2015b, Thinkpad T410)

%//uint32 for the subscript indexing
x = uint32(1:2:N);
y = uint32(1:2:N);
tic
for i=1:it
    im(x,y) = im(x,y) +1;
end
toc%// cost 0.11 seconds on my machine(MATLAB2015b, Thinkpad T410)

%% /*********************comparison with others*****************/
%//third way of indexing, loops
tic
for i=1:it
    for j=1:2:N
        for k=1:2:N
            im(j,k) = im(j,k)+1;
        end
    end
end
toc%// cost 0.74 seconds on my machine(MATLAB2015b, Thinkpad T410)

看起来直接使用下标索引比从sub2ind获得的线性索引更快。有谁知道为什么吗？我以为它们几乎一样。

- Yuanhao

---

sub2ind有一些开销。尝试使用其“手动”版本：index = bsxfun(@plus, (1:2:size(im,1)).', ((1:2:size(im,2))-1)*size(im,1))。此外，最好使用timeit进行计时，而不是使用 tic/toc。 - Luis Mendo

糟糕，现在我看到我所提到的开销超出了你的时间范围。 - Luis Mendo

据我所知，在MATLAB中，下标索引是一种语法糖。MATLAB在内部将所有高维矩阵存储为线性数组（http://www.mathworks.com/help/matlab/matlab_prog/memory-allocation.html?refresh=true#brh72ex-5）。 - Dan

@Dan，是的，我认为Matlab有线性存储。这就是为什么这段代码让我感到困惑的原因。在线性情况下，线性索引应该比下标方式更快。但结果显示相反。 - Yuanhao

你的处理器是什么？你能尝试使用int32而不是double作为索引吗？正如hbaderts所指出的，你的索引数组有64k个条目-512kB，而你的数据本身有4MB（2MB在缓存中活跃）。根据你的缓存大小，额外的512kB可能会使得所有内容都在缓存中和连续访问RAM之间产生差异（请参见http://stackoverflow.com/questions/34831118/speed-up-reshape-not-use-reshape-matlab/34831498#34831498）-典型的性能提升约为3-4倍。 - Alexander Kemp

Answer 1

直觉

正如Daniel在他的回答中提到的，线性索引在RAM中占用更多的空间，而下标要小得多。

对于下标索引，Matlab在内部不会创建线性索引，但它将使用一个（双重）编译的循环来循环遍历所有元素。

另一方面，下标版本将不得不循环遍历所有从外部传递过来的线性索引，这将需要更多的内存读取，因此需要更长的时间。

声明

• 线性索引更快
• 只要总索引数相同

计时

从计时结果可以直接证实第一个声明，并且我们可以通过一些额外的测试推断出第二个声明（如下所示）。

LOOPED
      subs assignment: 0.2878s
    linear assignment: 0.0812s

VECTORIZED
      subs assignment: 0.0302s
    linear assignment: 0.0862s

第一个声明

我们可以使用循环来测试它。子参考操作的数量是相同的，但是线性索引直接指向所需元素，而下标需要在内部进行转换。

感兴趣的函数：

function B = subscriptedIndexing(A,row,col)
n = numel(row);
B = zeros(n);
for r = 1:n
    for c = 1:n
        B(r,c) = A(row(r),col(c));
    end
end
end

function B = linearIndexing(A,index)
B = zeros(size(index));
for ii = 1:numel(index)
    B(ii) = A(index(ii));
end
end

第二个说法

这个说法是从使用向量化方法时观察到的速度差异推断出来的。

首先，向量化方法（与循环相反）加快了下标赋值，而线性索引略慢一些（可能没有统计学显著性）。

其次，两种索引方法之间唯一的区别来自索引/下标的大小。我们希望将其隔离为可能导致时间差异的唯一原因。另一个重要的影响因素可能是JIT优化。

测试函数：

function B = subscriptedIndexingVect(A,row,col)
n = numel(row);
B = zeros(n);
B = A(row,col);
end

function B = linearIndexingVect(A,index)
B = zeros(size(index));
B = A(index);
end

注意：我保留了B的过度预分配，以使矢量化和循环方法可比较。换句话说，时间差异应仅来自索引和循环的内部实现。

所有测试都是使用以下方式运行的：

function testFun(N)
A             = magic(N);
row           = 1:2:N;
col           = 1:2:N;
[ind_x,ind_y] = ndgrid(row,col);
index         = sub2ind(size(A),ind_x,ind_y);

% isequal(linearIndexing(A,index), subscriptedIndexing(A,row,col))
% isequal(linearIndexingVect(A,index), subscriptedIndexingVect(A,row,col))

fprintf('<strong>LOOPED</strong>\n')
fprintf('      subs assignment: %.4fs\n',  timeit(@()subscriptedIndexing(A,row,col)))
fprintf('    linear assignment: %.4fs\n\n',timeit(@()linearIndexing(A,index)))
fprintf('<strong>VECTORIZED</strong>\n')
fprintf('      subs assignment: %.4fs\n',  timeit(@()subscriptedIndexingVect(A,row,col)))
fprintf('    linear assignment: %.4fs\n',  timeit(@()linearIndexingVect(A,index)))
end

开启/关闭JIT对性能没有影响：

feature accel off
testFun(5e3)
...

VECTORIZED
      subs assignment: 0.0303s
    linear assignment: 0.0873s

feature accel on
testFun(5e3)
...

VECTORIZED
      subs assignment: 0.0303s
    linear assignment: 0.0871s

这个排除了下标赋值的超高速度来自JIT优化的可能性，只剩下一个合理的原因，即RAM访问次数。虽然最终矩阵具有相同数量的元素，但线性赋值必须检索索引中的所有元素才能获取数字。

设置

在Win7 64上测试，使用MATLAB R2015b版本。由于近期更改了MATLAB执行引擎，因此先前版本的MATLAB将提供不同的结果。

实际上，在MATLAB R2014a 中关闭JIT会影响计时，但仅对循环（预期结果）产生影响：

feature accel off
testFun(5e3)

LOOPED
      subs assignment: 7.8915s
    linear assignment: 6.4418s

VECTORIZED
      subs assignment: 0.0295s
    linear assignment: 0.0878s

这再次证实，线性和下标赋值之间时序差异应该来自RAM访问次数的不同，因为JIT在向量化方法中没有发挥作用。

- Oleg

Answer 2

我并不感到惊讶的是，这里使用下标索引要快得多。如果你看一下输入数据，你会发现在这种情况下，索引要小得多。对于下标索引的情况，你有512个元素，而对于线性索引的情况，你有65536个元素。

当你将你的示例应用到向量上时，你会发现两种方法没有区别。

这是我用来评估不同矩阵大小的略微修改过的代码：

it = 400; im = zeros(512*512,1);
x = 1:2:size(im,1);
y = 1:2:size(im,2);
%// linear indexing
[ind_x,ind_y] = ndgrid(x,y);
index = sub2ind(size(im),ind_x,ind_y);

tic
for i=1:it
    im(index) = im(index) + 1;
end
toc 

%// subscript indexing


tic
for i=1:it
    im(x,y) = im(x,y) +1;
end
toc 

- Daniel

---

@Dan：我添加了代码。它创建了一个向量。将zeros(512*512,1)更改为zeros(512*512,3)，你会发现线性索引版本的时间和索引大小大致翻倍，而下标索引版本仅稍微慢一些。 - Daniel

它们正在访问相同数量的元素，索引区域的大小相同，但索引本身的大小不同。 - Daniel

@Daniel，但这是否适用于我（现已被管理员删除）使用for循环并逐个访问单个元素的示例？在这种情况下，索引区域的大小永远不会超过1个元素。 - Dan

@Dan：针对你的例子，我只得到了10%和25%之间的轻微速度差异。不确定发生了什么。 - Daniel

当我执行im = zeros(N^2,1)（对于我之前评论中提到的代码）时，我得到了相同的速度。 - Dan

Answer 3

免责声明：我目前没有MATLAB许可证，所以我提供的下面的代码尚未经过测试。但是，如果有人决定进行测试，请相应地在这个答案下评论。

根据您使用的MATLAB版本（例如，您是否在使用R2015b？），在调用“zeros”时，您可能没有支付预分配的全部前期成本。有可能在第一次获取/设置im时为其分配内存，这会在您首次访问im内部值时引起额外但隐藏的开销。

请参见：http://undocumentedmatlab.com/blog/preallocation-performance

作为初步测试，建议更改您对代码的分析顺序：

N = 512; it = 400; im = zeros(N);

%// subscript indexing
x = 1:2:N;
y = 1:2:N;

tic
for i=1:it
    im(x,y) = im(x,y) +1;
end
toc %// What's the cost now?

%// linear indexing
[ind_x,ind_y] = ndgrid(1:2:N,1:2:N);
index = sub2ind(size(im),ind_x,ind_y);

tic
for i=1:it
    im(index) = im(index) + 1;
end
toc %// What's the cost now?

为了更公平地对比下标索引和线性索引，我建议采用以下两种可能的方法之一：

1. 通过创建两个分别初始化为zeros(N)的矩阵im1和im2，并将每个矩阵用于单独的索引方法，确保在两种方法上都产生分配成本。
2. 在实际对下标索引和线性索引进行分析之前，对im的每个元素运行完整的get/set操作。

方法1：

N = 512; it = 400; im1 = zeros(N); im2 = zeros(N);

%// subscript indexing
x = 1:2:N;
y = 1:2:N;

tic
for i=1:it
    im1(x,y) = im1(x,y) + 1;
end
toc %// What's the cost now?

%// linear indexing
[ind_x,ind_y] = ndgrid(1:2:N,1:2:N);
index = sub2ind(size(im2),ind_x,ind_y);

tic
for i=1:it
    im2(index) = im2(index) + 1;
end
toc %// What's the cost now?

方法二：

N = 512; it = 400; im = zeros(N);

%// Run a full get/set on each element to force allocation
tic
for i=1:N^2
    im(i) = im(i) +1;
end
toc 


%// subscript indexing
x = 1:2:N;
y = 1:2:N;

tic
for i=1:it
    im(x,y) = im(x,y) +1;
end
toc %// What's the cost now?

%// linear indexing
[ind_x,ind_y] = ndgrid(1:2:N,1:2:N);
index = sub2ind(size(im),ind_x,ind_y);

tic
for i=1:it
    im(index) = im(index) + 1;
end
toc %// What's the cost now?

我有第二个假设，即当您显式声明要访问的每个元素时，与让MATLAB为您推断元素相比，您会产生一些额外的开销。 excasa的"duplicate post" reference（在我看来并不完全是重复的）具有相同的一般见解，但使用不同的数据点得出了这个结论。我不会在这里写出这方面的例子，但基本上，创建一个直接的巨大数组index与较小的下标索引x和y相比，给MATLAB留下了更少的内部优化空间。我不知道MATLAB内部会执行哪些特定的优化，但也许它们来自您可能知道的黑魔法MATLAB的JIT/LXE。如果您真的想检查JIT是否是罪魁祸首（并且正在使用2014b或更早版本），那么您可以尝试禁用它，然后运行上面的代码。

有几种方法可以禁用JIT：

1. 使用未记录的特性方法。
2. 将命令复制/粘贴到命令提示符中，而不是直接从脚本编辑器运行它们。

不幸的是，我不知道如何在R2015a及更高版本中关闭LXE，而尝试诊断LXE是否是罪魁祸首可能会有点艰难。如果您卡在这里，也许您可以通过MathWorks技术支持或MathWorks Central进一步深入研究。您可能会惊讶地发现这两个来源都有一些惊人的专家。

- Nadesri

---

运行了你的所有代码片段后，下标索引仍然比线性索引快得多（在所有情况下）。此外，我尝试使用for循环，每次使用标量进行索引和使用下标索引，结果下标索引仍然更快。 - Dan

嗨，丹，感谢你测试这些代码片段。出于好奇，你是否也尝试过禁用/重新启用JIT？ - Nadesri

我没有尝试禁用JIT。 - Dan

Answer 4

一个非常好的问题。我不知道正确的答案，但你可以分析其行为。将第一个toc保存到t1中，将第二个toc保存到t2中。最后计算t1/t2。你会发现，改变迭代次数或矩阵大小（几乎）不会改变这个因子。 我的建议：

• 迭代次数仅提高了tictoc的质量。（显然？）
• 矩阵的大小没有影响，即语法中必须有时间延迟。

我想象一下，可能只是由于从线性索引转换为下标索引，即您执行的内部加法（操作）完全相同，所以使用下标索引似乎更自然，所以mathworks可能仅优化了第一种情况。

更新： 您还可以简单地访问矩阵中的元素，您会发现使用下标索引比使用线性索引更快。这支持了这样一个理论，即从线性到下标之间会进行内部的缓慢转换。

- rst

---

我添加了第三种索引方式，使用下标直接访问矩阵中的一个元素。这是三种方法中最慢的。我猜它没有使用matlab中的向量化，所以很慢。 - Yuanhao