为什么重塑如此之快?(剧透:写时复制) [英] Why is reshape so fast? (Spoiler: Copy-on-Write)

问题描述

我有一个大矩阵 A，它是 1GB 的双值，当我将它重塑为不同的维度时，速度非常快.

A=rand(128,1024,1024);tic;B=reshape(A,1024,128,1024);toc经过的时间是 0.000011 秒.

怎么会这么快?另一个观察结果是，在运行该代码并存储两个 1GB 矩阵后，MATLAB 使用的内存少于应有的内存:MATLAB 使用的内存:1878 MB(1.969e+09 字节)

解决方案

良好表现的说明

Matlab 尽可能使用 copy-on-write.如果您编写类似 B=A 的表达式，MATLAB 不会复制 A，而是变量 A 和 B 都是对同一数据结构的引用.只有当两个变量之一被修改时，MATLAB 才会创建一个副本.

现在是 reshape 的特殊情况.这里看起来 A 和 B 不一样，但在内存中它们是.保存数据的底层数组不受 reshape 操作的影响，无需移动任何内容:all(A(:)==B(:)).MATLAB 在调用 reshape 时要做的一切就是创建一个新的引用并用矩阵的新维度对其进行注释.重塑矩阵无非是创建对输入数据的新引用，并使用新维度进行注释.reshape 的运行时间小于 1µs，大约是 B=A 等两个简单赋值所需的时间.对于所有实际应用，零时间操作.

<代码>>>tic;for i=1:1000;B=reshape(A,1024,128,1024);end;toc经过的时间是 0.000724 秒.>>抽动；对于 i=1:1000；B=A；结束；toc经过的时间是 0.000307 秒.

不知道这样的引用到底有多大，但我们可以假设它在几个字节之内.

其他零成本运营

已知几乎为零成本的函数(运行时和内存):

• B=reshape(A,sz)
• B=A(:)
• B=A.' - 仅用于向量
• B=A' - 仅适用于实数向量，没有complex 属性.改用 .'.
• B=permute(A,p) - 仅适用于 all(A(:)==B(:)).¹
• B=ipermute(A,p) - 仅适用于 all(A(:)==B(:)).¹
• B=squeeze(A) ¹
• shiftdim - 仅适用于 all(A(:)==B(:)) 的情况，即:¹
  • 用于删除前导单一维度.
  • 与负的第二个输入一起使用
  • 在没有第二个输入参数的情况下使用.

昂贵"的函数，不管它们不触及内存中的表示这一事实(all(A(:)==B(:)) 为真)>

• 左侧索引:B(1:numel(A))=A; ²
• 除(:)之外的右侧索引，包括B=A(1:end);和B=A(:,:,:); ²

¹ 运行时间比 reshape 慢得多，介于 1µs 和 1ms 之间.可能是因为一些恒定的计算开销.内存消耗几乎为零，运行时间与输入大小无关.没有此注释的操作的运行时间低于 1µs，大致相当于 reshape.

² OCTAVE 零成本

最初在撰写本文时使用 MATLAB 2013b.用 MATLAB 2019b 确认数字.

I have a big matrix A which is 1GB of double values, when I reshape it to different dimensions, it's incredible fast.

A=rand(128,1024,1024);
tic;B=reshape(A,1024,128,1024);toc

Elapsed time is 0.000011 seconds.

How can it be that fast? Another observation, MATLAB uses less memory than it should after running that code and storing two matrices of 1GB each: Memory used by MATLAB: 1878 MB (1.969e+09 bytes)

解决方案

Explanation of the good performance

Matlab uses copy-on-write whenever possible. If you write expressions like B=A, MATLAB does not copy A, instead both variables A and B are references to the same data structure. Only if one of the two variables will be modified, MATLAB will create a copy.

Now to the special case of reshape. Here it looks like A and B are not the same, but in memory they are. The underlying array which holds the data is unaffected by the reshape operation, nothing has to be moved: all(A(:)==B(:)). Everything MATLAB has to do when calling reshape is to create a new reference and annotate it with the new dimensions of the matrix. Reshaping a matrix is nothing more than creating a new reference to the input data, which is annotated with the new dimensions. The runtime of reshape is less than 1µs or roughly the time two simple assignments like B=A require. For all practical applications a zero time operation.

>> tic;for i=1:1000;B=reshape(A,1024,128,1024);end;toc
Elapsed time is 0.000724 seconds.
>> tic;for i=1:1000;B=A;end;toc
Elapsed time is 0.000307 seconds.

It is unknown how large such a reference really is, but we can assume it to be within a few bytes.

Other zero cost operations

Functions known to have practically zero cost (both runtime and memory):

• B=reshape(A,sz)
• B=A(:)
• B=A.' - only for Vectors
• B=A' - only for Vectors of real numbers, without the attribute complex. Use .' instead.
• B=permute(A,p) - only for the cases where all(A(:)==B(:)).¹
• B=ipermute(A,p) - only for the cases where all(A(:)==B(:)).¹
• B=squeeze(A) ¹
• shiftdim - only for the cases where all(A(:)==B(:)), which are:¹
  • used to remove leading singleton dimensions.
  • used with negative second input
  • used without second input argument.

Functions which are "expensive", regardless of the fact that they don't touch the representation in memory (all(A(:)==B(:)) is true)

• Left sided indexing: B(1:numel(A))=A; ²
• Right sided indexing other than (:), including B=A(1:end); and B=A(:,:,:); ²

¹ Significantly slower runtime than reshape between 1µs and 1ms. Probably because of some constant computation overhead. Memory consumption is practically zero and the runtime is independent from the input size. Operations without this annotation have a runtime below 1µs and roughly equivalent to reshape.

² Zero cost in OCTAVE

Originally used MATLAB 2013b when writing this post. Confirmed the numbers with MATLAB 2019b.

这篇关于为什么重塑如此之快?(剧透:写时复制)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！