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

我在MATLAB中有一个2D矩阵,我使用两种不同的方式来访问它的元素.一个基于下标索引,另一个基于线性索引.我通过以下代码测试这两种方法:

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.有谁知道为什么？我以为他们差不多了.

正如丹尼尔在他的回答中提到的,线性索引在RAM中占用更多空间,而下标则更小.

对于下标索引,在内部,Matlab不会创建线性索引,但它将使用(双)编译循环来循环遍历所有元素.

另一方面,下标版本必须循环遍历从外部传递的所有线性索引,这将需要更多内存读取,因此需要更长时间.

线性索引更快

......只要指数总数相同

计时

从时间上我们看到第一个索赔的直接确认,我们可以通过一些额外的测试推断第二个索引(下面).

LOOPED
      subs assignment: 0.2878s
    linear assignment: 0.0812s

VECTORIZED
      subs assignment: 0.0302s
    linear assignment: 0.0862s

我们可以用循环测试它.subref操作数相同,但线性索引直接指向感兴趣的元素,而内部的下标需要转换.

感兴趣的功能:

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('LOOPED\n')
fprintf('      subs assignment: %.4fs\n',  timeit(@()subscriptedIndexing(A,row,col)))
fprintf('    linear assignment: %.4fs\n\n',timeit(@()linearIndexing(A,index)))
fprintf('VECTORIZED\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访问次数.确实,最终矩阵具有相同数量的元素.但是,线性赋值必须检索索引的所有元素才能获取数字.

使用MATLAB R2015b在Win7 64上测试.由于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

这再次证实了线性和sibscripted赋值之间的时序差异应该来自RAM访问的数量,因为JIT在矢量化方法中不起作用.