通过空矩阵乘法更快地初始化数组的方法？(Matlab的)

Question

我偶然发现了Matlab处理空矩阵的奇怪方式(在我看来).例如,如果两个空矩阵相乘,则结果为:

zeros(3,0)*zeros(0,3)
ans =

 0     0     0
 0     0     0
 0     0     0

现在,这已经让我感到惊讶,然而,快速搜索让我进入上面的链接,我得到了解释为什么会发生这种情况的一些扭曲的逻辑.

但是,没有任何事情让我为以下观察做好准备 我问自己,这种类型的乘法与使用zeros(n)函数的效率有多高,比如初始化的目的？我以前timeit回答这个问题:

f=@() zeros(1000)
timeit(f)
ans =
    0.0033

VS:

g=@() zeros(1000,0)*zeros(0,1000)
timeit(g)
ans =
    9.2048e-06

两者都有1000x1000类零的矩阵相同的结果double,但空矩阵乘法1的速度快〜350倍!(使用ticand toc和循环发生类似的结果)

怎么会这样？是timeit或是tic,toc虚张声势还是我找到了一种更快速的方法来初始化矩阵？(这是用matlab 2012a完成的,在win7-64机器上,intel-i5 650 3.2Ghz ...)

编辑:

在阅读了您的反馈之后,我更仔细地研究了这个特性,并在2台不同的计算机上进行了测试(同样的matlab ver,尽管2012a),这是一个检查运行时间与矩阵n大小的代码.这就是我得到的:

生成此代码的代码与timeit之前一样使用,但循环使用tic并且toc看起来相同.因此,对于小尺寸,zeros(n)是可比的.然而,围绕n=400空矩阵乘法的性能有所提升.我用来生成该图的代码是:

n=unique(round(logspace(0,4,200)));
for k=1:length(n)
    f=@() zeros(n(k));
    t1(k)=timeit(f);

    g=@() zeros(n(k),0)*zeros(0,n(k));
    t2(k)=timeit(g);
end

loglog(n,t1,'b',n,t2,'r');
legend('zeros(n)','zeros(n,0)*zeros(0,n)',2);
xlabel('matrix size (n)'); ylabel('time [sec]');

你们中的任何人都有这种经历吗？

编辑#2:

顺便提一下,不需要空矩阵乘法来获得这种效果.人们可以简单地做到:

z(n,n)=0;

其中n>在前一个图中看到的某个阈值矩阵大小,并获得与空矩阵乘法一样的精确效率曲线(再次使用timeit).

这是一个提高代码效率的例子:

n = 1e4;
clear z1
tic
z1 = zeros( n ); 
for cc = 1 : n
    z1(:,cc)=cc;
end
toc % Elapsed time is 0.445780 seconds.

%%
clear z0
tic
z0 = zeros(n,0)*zeros(0,n);
for cc = 1 : n
    z0(:,cc)=cc;
end
toc % Elapsed time is 0.297953 seconds.

但是,使用z(n,n)=0;相反的结果会产生类似的结果zeros(n).

Answer 1

这很奇怪,我看到f越快,而g慢于你所看到的.但是他们两个对我来说都是一样的.也许是不同版本的MATLAB？

>> g = @() zeros(1000, 0) * zeros(0, 1000);
>> f = @() zeros(1000)
f =     
    @()zeros(1000)
>> timeit(f)  
ans =    
   8.5019e-04
>> timeit(f)  
ans =    
   8.4627e-04
>> timeit(g)  
ans =    
   8.4627e-04

编辑你可以为f和g的结尾添加+ 1,并查看你得到的时间.

编辑2013年1月6日美国东部时间7点42分

我正在远程使用一台机器,所以抱歉低质量的图表(不得不盲目生成).

机器配置:

i7 920. 2.653 GHz.Linux操作系统.12 GB RAM.8MB缓存.

看起来甚至我可以访问的机器都显示出这种行为,除了更大的尺寸(1979年到2073年之间).我现在没有理由认为空矩阵乘法在较大尺寸时更快.

我会在回来之前稍微调查一下.

编辑2013年1月11日

在@ EitanT的帖子之后,我想做更多的挖掘.我写了一些C代码来看看matlab如何创建一个零矩阵.这是我使用的c ++代码.

int main(int argc, char **argv)
{
    for (int i = 1975; i <= 2100; i+=25) {
    timer::start();
    double *foo = (double *)malloc(i * i * sizeof(double));
    for (int k = 0; k < i * i; k++) foo[k]  = 0;
    double mftime = timer::stop();
    free(foo);

    timer::start();
    double *bar = (double *)malloc(i * i * sizeof(double));
    memset(bar, 0, i * i * sizeof(double));
    double mmtime = timer::stop();
    free(bar);

    timer::start();
    double *baz = (double *)calloc(i * i, sizeof(double));
    double catime = timer::stop();
    free(baz);

    printf("%d, %lf, %lf, %lf\n", i, mftime, mmtime, catime);
    }
}

结果如下.

$ ./test
1975, 0.013812, 0.013578, 0.003321
2000, 0.014144, 0.013879, 0.003408
2025, 0.014396, 0.014219, 0.003490
2050, 0.014732, 0.013784, 0.000043
2075, 0.015022, 0.014122, 0.000045
2100, 0.014606, 0.014480, 0.000045

正如你所看到的calloc(第4栏)似乎是最快的方法.它在2025年到2050年之间也明显加快了(我假设它会在2048年左右？).

现在我回到matlab检查一下.结果如下.

>> test
1975, 0.003296, 0.003297
2000, 0.003377, 0.003385
2025, 0.003465, 0.003464
2050, 0.015987, 0.000019
2075, 0.016373, 0.000019
2100, 0.016762, 0.000020

看起来f()和g()都使用calloc较小的尺寸(<2048？).但是在较大的尺寸下,f()(零(m,n))开始使用malloc+ memset,而g()(零(m,0)*零(0,n))继续使用calloc.

因此,分歧由以下解释

• 零(...)开始在较大的尺寸上使用不同的(较慢的？)方案.
• calloc 也表现得有些出乎意料,导致性能提升.

这是Linux上的行为.有人可以在不同的机器(也许是不同的操作系统)上进行相同的实验,看看实验是否成立？

Answer 2

结果可能有点误导.当你将两个空矩阵相乘时,得到的矩阵不会立即"分配"和"初始化",而是推迟到你第一次使用它时(有点像懒惰的评估).

这同样适用时,索引出界于成长的变量,这在数字阵列的情况下填写用零任何缺少的条目(我后来讨论非数字的情况下).当然,以这种方式增长矩阵不会覆盖现有元素.

因此,虽然它看起来更快,但您只是在实际首次使用矩阵之前延迟分配时间.最后,您将有类似的时间,就像从一开始就进行分配一样.

与其他一些替代方案相比,显示此行为的示例:

N = 1000;

clear z
tic, z = zeros(N,N); toc
tic, z = z + 1; toc
assert(isequal(z,ones(N)))

clear z
tic, z = zeros(N,0)*zeros(0,N); toc
tic, z = z + 1; toc
assert(isequal(z,ones(N)))

clear z
tic, z(N,N) = 0; toc
tic, z = z + 1; toc
assert(isequal(z,ones(N)))

clear z
tic, z = full(spalloc(N,N,0)); toc
tic, z = z + 1; toc
assert(isequal(z,ones(N)))

clear z
tic, z(1:N,1:N) = 0; toc
tic, z = z + 1; toc
assert(isequal(z,ones(N)))

clear z
val = 0;
tic, z = val(ones(N)); toc
tic, z = z + 1; toc
assert(isequal(z,ones(N)))

clear z
tic, z = repmat(0, [N N]); toc
tic, z = z + 1; toc
assert(isequal(z,ones(N)))

结果显示,如果您在每种情况下对两个指令的经过时间求和,则最终会得到类似的总计时:

// zeros(N,N)
Elapsed time is 0.004525 seconds.
Elapsed time is 0.000792 seconds.

// zeros(N,0)*zeros(0,N)
Elapsed time is 0.000052 seconds.
Elapsed time is 0.004365 seconds.

// z(N,N) = 0
Elapsed time is 0.000053 seconds.
Elapsed time is 0.004119 seconds.

其他时间是:

// full(spalloc(N,N,0))
Elapsed time is 0.001463 seconds.
Elapsed time is 0.003751 seconds.

// z(1:N,1:N) = 0
Elapsed time is 0.006820 seconds.
Elapsed time is 0.000647 seconds.

// val(ones(N))
Elapsed time is 0.034880 seconds.
Elapsed time is 0.000911 seconds.

// repmat(0, [N N])
Elapsed time is 0.001320 seconds.
Elapsed time is 0.003749 seconds.

这些测量值在毫秒内太小而且可能不是很准确,因此您可能希望在循环中运行这些命令几千次并取平均值.有时运行保存的M函数比运行脚本或命令提示符更快,因为某些优化只会以这种方式发生......

无论哪种方式分配通常都进行一次,所以谁在乎它是否需要额外的30ms :)

使用单元阵列或结构数组可以看到类似的行为.请考虑以下示例:

N = 1000;

tic, a = cell(N,N); toc
tic, b = repmat({[]}, [N,N]); toc
tic, c{N,N} = []; toc

这使:

Elapsed time is 0.001245 seconds.
Elapsed time is 0.040698 seconds.
Elapsed time is 0.004846 seconds.

请注意,即使它们都相等,它们也会占用不同的内存量:

>> assert(isequal(a,b,c))
>> whos a b c
  Name         Size                  Bytes  Class    Attributes

  a         1000x1000              8000000  cell               
  b         1000x1000            112000000  cell               
  c         1000x1000              8000104  cell               

事实上,这里的情况有点复杂,因为MATLAB可能为所有单元共享相同的空矩阵,而不是创建多个副本.

单元格数组a实际上是一个未初始化的单元格数组(一个NULL指针数组),b而是一个单元格数组,其中每个单元格都是一个空数组[](内部和由于数据共享,只有第一个单元格b{1}指向,[]而其他所有单元格都有对第一个单元格的引用).最后一个数组c类似于a(未初始化的单元格),但最后一个数组包含一个空数字矩阵[].

我查看了libmx.dll(使用Dependency Walker工具)导出的C函数列表,我发现了一些有趣的东西.

• 有用于创建初始化数组无证功能:mxCreateUninitDoubleMatrix,mxCreateUninitNumericArray,和mxCreateUninitNumericMatrix.事实上,File Exchange上的提交使用这些功能来提供更快的zeros功能替代方案.

• 存在一个名为的未记录的函数mxFastZeros.谷歌搜索在线,我可以看到你在MATLAB答案上交叉发布这个问题,并在那里有一些很好的答案.James Tursa(以前的UNINIT的同一作者)举了一个关于如何使用这个未记录的函数的例子.

• libmx.dll与tbbmalloc.dll共享库链接.这是Intel TBB可扩展内存分配器.该库提供等效内存分配函数(malloc,calloc,free),用于并行应用进行了优化.请记住,许多MATLAB函数都是自动多线程的,所以如果zeros(..)多线程并且在矩阵大小足够大时使用Intel的内存分配器,我不会感到惊讶(这是Loren Shure最近的评论证实了这一点).

关于内存分配器的最后一点,您可以在C/C++中编写类似于@PavanYalamanchili所做的类似基准,并比较可用的各种分配器.像这样的东西.请记住,MEX-文件有一个略高的内存管理开销,因为MATLAB自动释放所有正在使用中MEX-文件分配的任何内存mxCalloc,mxMalloc或mxRealloc功能.对于它的价值,过去可以更改旧版本的内部内存管理器.

编辑:

这是一个更彻底的基准,用于比较讨论的替代方案.它特别表明,一旦你强调使用整个分配的矩阵,所有三种方法都是平等的,差异可以忽略不计.

function compare_zeros_init()
    iter = 100;
    for N = 512.*(1:8)
        % ZEROS(N,N)
        t = zeros(iter,3);
        for i=1:iter
            clear z
            tic, z = zeros(N,N); t(i,1) = toc;
            tic, z(:) = 9; t(i,2) = toc;
            tic, z = z + 1; t(i,3) = toc;
        end
        fprintf('N = %4d, ZEROS = %.9f\n', N, mean(sum(t,2)))

        % z(N,N)=0
        t = zeros(iter,3);
        for i=1:iter
            clear z
            tic, z(N,N) = 0; t(i,1) = toc;
            tic, z(:) = 9; t(i,2) = toc;
            tic, z = z + 1; t(i,3) = toc;
        end
        fprintf('N = %4d, GROW  = %.9f\n', N, mean(sum(t,2)))

        % ZEROS(N,0)*ZEROS(0,N)
        t = zeros(iter,3);
        for i=1:iter
            clear z
            tic, z = zeros(N,0)*zeros(0,N); t(i,1) = toc;
            tic, z(:) = 9; t(i,2) = toc;
            tic, z = z + 1; t(i,3) = toc;
        end
        fprintf('N = %4d, MULT  = %.9f\n\n', N, mean(sum(t,2)))
    end
end

以下是在增加矩阵大小方面平均超过100次迭代的时序.我在R2013a进行了测试.

>> compare_zeros_init
N =  512, ZEROS = 0.001560168
N =  512, GROW  = 0.001479991
N =  512, MULT  = 0.001457031

N = 1024, ZEROS = 0.005744873
N = 1024, GROW  = 0.005352638
N = 1024, MULT  = 0.005359236

N = 1536, ZEROS = 0.011950846
N = 1536, GROW  = 0.009051589
N = 1536, MULT  = 0.008418878

N = 2048, ZEROS = 0.012154002
N = 2048, GROW  = 0.010996315
N = 2048, MULT  = 0.011002169

N = 2560, ZEROS = 0.017940950
N = 2560, GROW  = 0.017641046
N = 2560, MULT  = 0.017640323

N = 3072, ZEROS = 0.025657999
N = 3072, GROW  = 0.025836506
N = 3072, MULT  = 0.051533432

N = 3584, ZEROS = 0.074739924
N = 3584, GROW  = 0.070486857
N = 3584, MULT  = 0.072822335

N = 4096, ZEROS = 0.098791732
N = 4096, GROW  = 0.095849788
N = 4096, MULT  = 0.102148452

Answer 3

在做了一些研究之后,我在"未记载的Matlab"中找到了这篇文章,其中Yair Altman先生已经得出结论,MathWork使用预分配矩阵的方式确实不是最有效的方法.zeros(M, N)

他x = zeros(M,N)与时间相比clear x, x(M,N) = 0,发现后者快了约500倍.根据他的解释,第二种方法只是创建一个M-by-N矩阵,其元素被自动初始化为0.然而,第一种方法创建x(x具有自动零元素),然后为每个元素分配一个零.x再次,这是一个需要更多时间的冗余操作.

在空矩阵乘法的情况下,例如您在问题中显示的内容,MATLAB期望乘积为M×N矩阵,因此它分配M×N矩阵.因此,输出矩阵自动初始化为零.由于原始矩阵是空的,因此不执行进一步的计算,因此输出矩阵中的元素保持不变并且等于零.