MATLAB中的索引向量效率低吗？
背景
我的问题的动机是简单的观察，这在某种程度上破坏了有经验的MATLAB用户经常持有/做出的信念/假设：
当涉及到内置函数和基本语言功能时，
- MATLAB进行了很好的优化，例如MATLAB中的索引向量和matrices.
- Loops很慢(尽管存在JIT)，如果算法可以以本机的“矢量化”方式表达，则通常应该避免使用这些特性。
归根结底: MATLAB的核心功能是高效的，如果不是不可能的话，使用MATLAB代码试图超越它是困难的。
向量索引性能的研究
下面显示的示例代码是最基本的:我将一个标量值赋给所有向量条目。首先，我分配一个空向量x
tic; x = zeros(1e8,1); toc
Elapsed time is 0.260525 seconds.有了x，我想将它的所有条目设置为相同的值。在实践中，您可能会使用不同的方法，例如x = value*ones(1e8,1)，但这里的重点是研究向量索引的性能。最简单的方法是这样写：
tic; x(:) = 1; toc
Elapsed time is 0.094316 seconds.让我们将其命名为method 1(来自分配给x的值)。它看起来非常快(至少比内存分配快)。因为我在这里做的唯一一件事是对内存进行操作，所以我可以通过计算获得的有效内存带宽并将其与我的计算机的硬件内存带宽进行比较来估计此代码的效率：
eff_bandwidth = numel(x) * 8 bytes per double * 2 / time在上面，我乘以2，因为除非使用SSE流，否则在内存中设置值需要从内存读取向量和将向量写入内存。在上面的示例中：
eff_bandwidth(1) = 1e8*8*2/0.094316 = 17 Gb/s我的计算机的STREAM-benchmarked memory bandwidth大约是17.9 Gb/s，所以确实- MATLAB在这种情况下提供了接近峰值的性能！到现在为止还好。
如果您想要将所有向量元素设置为某个值，则方法1是合适的。但是如果你想访问每个step条目的元素，你需要用1:step:end替换:。下面是与方法1的直接速度比较：
tic; x(1:end) = 2; toc
Elapsed time is 0.496476 seconds.虽然你不会期望它会有任何不同的表现，但方法2显然是个大麻烦:因素5无缘无故地减速。我怀疑在这种情况下MATLAB显式地分配索引向量(1:end)。通过使用显式向量大小而不是end在某种程度上证实了这一点
tic; x(1:1e8) = 3; toc
Elapsed time is 0.482083 seconds.方法2和方法3的表现同样糟糕。
另一种可能是显式地创建索引向量id，并使用它来索引x。这为您提供了最灵活的索引功能。在我们的例子中：
tic;
id = 1:1e8; % colon(1,1e8);
x(id) = 4;
toc
Elapsed time is 1.208419 seconds.现在，这是真正的东西-比方法1慢了12倍！我知道它的性能应该比方法1差，因为id使用了额外的内存，但是为什么它比方法2和方法3差这么多呢？
让我们试一试这个循环--尽管听起来没有希望。
tic;
for i=1:numel(x)
x(i) = 5;
end
toc
Elapsed time is 0.788944 seconds.一个很大的惊喜-循环击败了vectorized方法4，但仍然比方法1，2和3慢。事实证明，在这种特殊情况下，你可以做得更好：
tic;
for i=1:1e8
x(i) = 6;
end
toc
Elapsed time is 0.321246 seconds.这可能是这项研究中最奇怪的结果--，一个由MATLAB编写的循环，它的性能明显优于原生向量索引。这肯定不应该是这样的。请注意，JIT‘’ed循环仍然比方法1几乎获得的理论峰值慢3倍，因此仍然有很大的改进空间。令人惊讶的是，通常的“向量化”索引(1:end)甚至更慢(一个更强的词会更合适)。
问题
在MATLAB中，
- 是简单的索引，效率非常低(方法2、3和4比方法1慢)，还是我错过了方法4的比方法2和3慢(这么多)？
- 为什么使用
1e8而不是<1e8>D50作为循环绑定将代码速度提高了2倍？
编辑在阅读了Jonas的评论之后，这里是使用逻辑索引的另一种方法：
tic;
id = logical(ones(1, 1e8));
x(id) = 7;
toc
Elapsed time is 0.613363 seconds.比方法4要好得多。
为方便起见：
function test
tic; x = zeros(1,1e8); toc
tic; x(:) = 1; toc
tic; x(1:end) = 2; toc
tic; x(1:1e8) = 3; toc
tic;
id = 1:1e8; % colon(1,1e8);
x(id) = 4;
toc
tic;
for i=1:numel(x)
x(i) = 5;
end
toc
tic;
for i=1:1e8
x(i) = 6;
end
toc
end回答 3
Stack Overflow用户
发布于 2012-11-15 00:12:14
当然，我只能推测。但是，当我在启用JIT编译器与禁用JIT编译器的情况下运行您的测试时，我得到以下结果：
% with JIT no JIT
0.1677 0.0011 %# init
0.0974 0.0936 %# #1 I added an assigment before this line to avoid issues with deferring
0.4005 0.4028 %# #2
0.4047 0.4005 %# #3
1.1160 1.1180 %# #4
0.8221 48.3239 %# #5 This is where "don't use loops in Matlab" comes from
0.3232 48.2197 %# #6
0.5464 %# logical indexing除法向我们展示了哪里有速度提高：
% withoutJit./withJit
0.0067 %# w/o JIT, the memory allocation is deferred
0.9614 %# no JIT
1.0057 %# no JIT
0.9897 %# no JIT
1.0018 %# no JIT
58.7792 %# numel
149.2010 %# no numel初始化的速度明显加快，因为在关闭JIT的情况下，MATLAB似乎会延迟内存分配，直到它被使用，所以x=zeros(...)实际上什么也做不了。(谢谢，@angainor)。
方法1到4似乎没有从JIT中受益。我猜#4可能会很慢，因为在subsref中进行了额外的输入测试，以确保输入是正确的形式。
numel的结果可能与编译器更难处理不确定的迭代次数有关，也可能与检查循环的边界是否正常(尽管no-JIT测试建议只需~0.1秒)有关。
令人惊讶的是，在我的机器上的R2012b上，逻辑索引似乎比#4慢。
我认为这再次表明，MathWorks在加速代码方面做了大量的工作，如果你试图获得最快的执行时间(至少在目前)，“不要使用循环”并不总是最好的。然而，我发现矢量化通常是一种很好的方法，因为(a) JIT在更复杂的循环上失败，(b)学习矢量化可以让你更好地理解Matlab。
结论:如果你想要速度，使用分析器，如果你切换Matlab版本，重新分析。正如@Adriaan在评论中指出的那样，现在使用timeit()来测量执行速度可能更好。
作为参考，我使用了以下稍微修改过的测试函数
function tt = speedTest
tt = zeros(8,1);
tic; x = zeros(1,1e8); tt(1)=toc;
x(:) = 2;
tic; x(:) = 1; tt(2)=toc;
tic; x(1:end) = 2; tt(3)=toc;
tic; x(1:1e8) = 3; tt(4)=toc;
tic;
id = 1:1e8; % colon(1,1e8);
x(id) = 4;
tt(5)=toc;
tic;
for i=1:numel(x)
x(i) = 5;
end
tt(6)=toc;
tic;
for i=1:1e8
x(i) = 6;
end
tt(7)=toc;
%# logical indexing
tic;
id = true(1e8,1));
x(id)=7;
tt(8)=toc;Stack Overflow用户
发布于 2012-11-15 01:42:04
我没有解决所有问题的答案，但我确实对方法2、3和4有一些精细的推测。
关于方法2和3，似乎MATLAB确实为向量索引分配了内存，并用从1到1e8的值填充它。为了理解它，让我们看看发生了什么。默认情况下，MATLAB使用double作为其数据类型。分配索引数组所需的时间与分配x所需的时间相同
tic; x = zeros(1e8,1); toc
Elapsed time is 0.260525 seconds.目前，索引数组仅包含零。以最佳方式为x向量赋值，就像在方法1中一样，需要花费0.094316秒。现在，必须从内存中读取索引向量，以便在索引中使用它。这是额外的0.094316/2秒。回想一下，在x(:)=1中，向量x必须从内存读取，也必须写入内存。因此，仅阅读它就需要一半的时间。假设这就是在x(1:end)=value中完成的所有工作，那么方法2和3的总时间应该是
t = 0.260525+0.094316+0.094316/2 = 0.402它几乎是正确的，但并不完全正确。我只能推测，但是用值填充索引向量可能是作为额外的步骤完成的，并且需要额外的0.094316秒。因此，t=0.4963或多或少地符合方法2和3的时间。
这些只是推测，但它们似乎确实证实了MATLAB 在执行本机向量索引时显式地创建索引向量。就我个人而言，我认为这是一个性能错误。MATLAB的JIT编译器应该足够聪明，能够理解这个微不足道的结构，并将其转换为对正确内部函数的调用。目前，在内存带宽受限的体系结构上，索引的执行速度大约为理论峰值的20%。
因此，如果您确实关心性能，则必须将x(1:step:end)实现为MEX函数，例如
set_value(x, 1, step, 1e8, value);这在MATLAB中显然是非法的，因为你不允许修改MEX文件中的数组。
编辑关于方法4，可以尝试分析各个步骤的性能，如下所示：
tic;
id = 1:1e8; % colon(1,1e8);
toc
tic
x(id) = 4;
toc
Elapsed time is 0.475243 seconds.
Elapsed time is 0.763450 seconds.第一步，分配和填充索引向量的值与单独使用方法2和3所需的时间相同。这似乎太多了--它最多应该花费分配内存和设置值(0.260525s+0.094316s = 0.3548s)所需的时间，所以在某个地方有额外的0.12秒的开销，这我不能理解。第二部分(x(id) = 4)看起来效率也很低:它需要花费一些时间来设置x的值，读取id向量(0.094316s+0.094316/2s = 0.1415s)以及对id值进行一些错误检查。用C语言编程，这两个步骤如下：
create id 0.214259
x(id) = 4 0.219768使用的代码检查double索引实际上是否表示一个整数，以及它是否适合x的大小：
tic();
id = malloc(sizeof(double)*n);
for(i=0; i<n; i++) id[i] = i;
toc("create id");
tic();
for(i=0; i<n; i++) {
long iid = (long)id[i];
if(iid>=0 && iid<n && (double)iid==id[i]){
x[iid] = 4;
} else break;
}
toc("x(id) = 4");第二步花费的时间比预期的0.1415s要长-这是因为需要对id值进行错误检查。开销对我来说似乎太大了--也许它可以写得更好。不过，所需的时间是0.4340s，而不是1.208419s。MATLAB在幕后做了什么--我不知道。也许有必要这么做，我就是看不出来。
当然，使用doubles作为索引会带来两个额外的开销级别：
double的
- 大小是
uint32的两倍。回想一下，内存带宽是索引
时需要将here.
- doubles转换为整数的限制因素
方法4可以使用整数索引在MATLAB中编写：
tic;
id = uint32(1):1e8;
toc
tic
x(id) = 8;
toc
Elapsed time is 0.327704 seconds.
Elapsed time is 0.561121 seconds.这显然将性能提高了30%，并证明了应该使用整数作为向量索引。然而，开销仍然存在。
正如我现在所看到的，我们不能做任何事情来改善在MATLAB框架内工作的情况，我们必须等到Mathworks修复这些问题。
Stack Overflow用户
发布于 2020-11-01 15:10:02
只需快速说明一下，在8年的发展中，MATLAB的性能特性发生了很大变化。
这是在R2017a上(在OP的帖子发布5年后)：
Elapsed time is 0.000079 seconds. % x = zeros(1,1e8);
Elapsed time is 0.101134 seconds. % x(:) = 1;
Elapsed time is 0.578200 seconds. % x(1:end) = 2;
Elapsed time is 0.569791 seconds. % x(1:1e8) = 3;
Elapsed time is 1.602526 seconds. % id = 1:1e8; x(id) = 4;
Elapsed time is 0.373966 seconds. % for i=1:numel(x), x(i) = 5; end
Elapsed time is 0.374775 seconds. % for i=1:1e8, x(i) = 6; end注意1:numel(x)循环比索引x(1:end)更快，数组1:end似乎仍在创建中，而循环则不是。现在在MATLAB中最好不要矢量化！
(我确实在分配矩阵之后添加了一个赋值x(:)=0，在任何定时区域之外，以实际分配内存，因为zeros只保留内存。)
在MATLAB R2020b (在线)(三年后)上，我看到了这样的情况：
Elapsed time is 0.000073 seconds. % x = zeros(1,1e8);
Elapsed time is 0.084847 seconds. % x(:) = 1;
Elapsed time is 0.084643 seconds. % x(1:end) = 2;
Elapsed time is 0.085319 seconds. % x(1:1e8) = 3;
Elapsed time is 1.393964 seconds. % id = 1:1e8; x(id) = 4;
Elapsed time is 0.168394 seconds. % for i=1:numel(x), x(i) = 5; end
Elapsed time is 0.169830 seconds. % for i=1:1e8, x(i) = 6; endx(1:end)现在与x(:)相同地进行了优化，不再显式创建向量1:end。
https://stackoverflow.com/questions/13382155
复制相似问题