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

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 得到的线性索引更快。有谁知道为什么？我认为它们几乎相同。

Answer 1

直觉

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

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

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

声明

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

时间

从时间上我们看到第一个声明的直接确认，我们可以通过一些额外的测试推断出第二个声明(如下)。

LOOPED
      subs assignment: 0.2878s
    linear assignment: 0.0812s

VECTORIZED
      subs assignment: 0.0302s
    linear assignment: 0.0862s

第一次 claim

我们可以用循环来测试它。 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

第二次 claim

此声明是根据使用矢量化方法时观察到的速度差异得出的推论。

首先，向量化方法(与循环方法相反)加速了下标赋值，而线性索引则稍慢(可能在统计上不显着)。

其次，两种索引方法的唯一区别在于索引/下标的大小。我们希望将此作为时间差异的唯一可能原因隔离开来。另一个主要参与者可能是 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 访问次数。确实，最终矩阵具有相同数量的元素。但是，线性赋值必须检索索引的所有元素才能获取数字。

设置

使用 MATLAB R2015b 在 Win7 64 上测试。由于最近对 Matlab's execution engine 的更改，早期版本的 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 在矢量化方法中没有发挥作用。