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

64

我发现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

对比:

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

两者产生的结果都是一个1000x1000的全零矩阵,数据类型为double,但是空矩阵乘法的速度快了大约350倍!(使用tictoc以及循环得到了类似的结果)
这是怎么回事?是timeittic,toc在欺骗我们吗?还是我找到了更快的初始化矩阵的方法?(这是在win7-64机器上,使用intel-i5 650 3.2Ghz处理器,matlab 2012a版本下进行的测试)
编辑后:
在阅读了您的反馈后,我仔细研究了这个特殊情况,并在两台不同的计算机上进行了测试(虽然使用的都是2012a版本的matlab)。测试代码检查了运行时间与矩阵大小n的关系,以下是测试结果:

enter image description here

生成这个的代码与之前一样使用了timeit,但是使用tictoc的循环看起来是相同的。因此,对于小尺寸,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),并获得精确的效率概要。

enter image description here

以下是一个例子,说明它如何提高代码效率:

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)相似。

@natan,你可以尝试使用零矩阵的kronecker积。不知何故,它甚至可以达到二次快速。 - Acorbe
1
@bla,我认为赏金应该给Amro的答案。据我所知,他是唯一真正深入了解这个问题的人。 - A. Donda
1
这种行为是由系统管理内存的方式所解释的。在一定大小范围内,分配的内存来自一个更大的池子,并且需要显式地清零。对于较大的尺寸,分配的内存来自一个新的池子,由系统清零,不需要显式清零。看起来,在提出这个问题时,“zeros”总是显式地清零内存,即使不必要。 - Cris Luengo
2
在MATLAB R2017a中,创建数组的这两种方法不再有区别。zeros方法显示了与乘法方法相同的行为。 - Cris Luengo
4个回答

33

很奇怪,我看到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,并查看相应的时间。

编辑 Jan 6, 2013 7:42 EST

我正在远程使用一台机器,所以抱歉图表质量不佳(必须盲目生成它们)。

机器配置:

i7 920. 2.653 GHz. Linux. 12 GB RAM. 8MB cache.

在 i7 920 上生成的图表

看起来即使是我可以访问的机器也显示出这种行为,只不过在更大的尺寸下(大约在 1979 到 2073 之间)。我现在想不出空矩阵乘法在较大尺寸下为什么会更快的原因。

在回来之前,我将进行更多的调查。

编辑 Jan 11, 2013

在 @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(第四列)似乎是最快的方法。它在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()都在使用较小的尺寸(<2048?)的calloc,但是对于较大的尺寸,f()(zeros(m, n))开始使用malloc+memset,而g()(zeros(m, 0)*zeros(0, n))继续使用calloc

因此,这种差异可以通过以下方式解释:

  • 在更大的尺寸上,zeros(..)开始使用不同的(更慢?)方案。
  • calloc的行为也有些出乎意料,导致性能有所提升。

这是在Linux上的行为。是否有人可以在另一台机器上(或许是另一个操作系统)进行相同的实验,以确定实验是否成立?


Pavan,如果您能查看我添加到问题中的编辑并分享您的观点,我将不胜感激。 - bla
1
@natan 看起来我在更大的大小上看到了相同的结果。 - Pavan Yalamanchili
1
@natan 我更新了更多信息。我认为我能够在C++代码中重现这种行为。这可能是由于calloc,这意味着它是系统/操作系统相关的。 - Pavan Yalamanchili
太棒了,如果我可以的话,我会再给你一个+1,但我已经给过你了。我会在Windows机器上尝试这个,看看能否重现这个问题。感谢你的努力,Pavan,我非常感激。 - bla
1
这里有一个详细的解释,为什么callocmalloc+memset更快:https://dev59.com/7XE85IYBdhLWcg3wnU6p#2688522。当然,一旦您开始向每个分配的内存页写入数据,整体性能将会相似(因为您将强制操作系统实际分配零值内存,而不是使用该帖子中提到的`mmap`技巧)。 - Amro
显示剩余3条评论

30

结果可能有点误导性。当你将两个空矩阵相乘时,生成的矩阵不会立即"分配"和"初始化",而是要等到第一次使用它时才进行(有点像懒惰求值)。

索引越界来增加一个变量时,同样适用于此,在数值数组的情况下,会用零填充任何缺失的条目(我随后讨论非数值情况)。当然,这种方式增加矩阵不会覆盖现有元素。

因此,虽然看起来似乎更快,但只是将分配时间推迟到实际首次使用矩阵时。最终,您将具有与从开始进行分配相似的计时。

示例以显示此行为,与几个其他选择进行比较:

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(未初始化单元格),但最后一个单元格包含一个空数值矩阵[]


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

  • 有一些未记录的函数可用于创建未初始化的数组:mxCreateUninitDoubleMatrixmxCreateUninitNumericArraymxCreateUninitNumericMatrix。事实上,File Exchange上有一个提交使用这些函数提供了比zeros函数更快的替代方法。

  • 存在一个名为mxFastZeros的未记录函数。在网上搜索,我发现你也在MATLAB Answers上发布了这个问题,并得到了一些很好的答案。James Tursa(之前的UNINIT作者)给出了一个example,介绍如何使用这个未记录的函数。

  • libmx.dll链接了tbbmalloc.dll共享库。这是Intel TBB可扩展的内存分配器。该库提供了优化并行应用程序的等效内存分配函数(malloccallocfree)。请记住,许多MATLAB函数都是automatically multithreaded,因此当矩阵大小足够大时,我不会感到惊讶,如果zeros(..)是多线程的,并且在使用Intel的内存分配器(这是Loren Shure最近的评论证实了这一事实)。

关于内存分配器的最后一点,您可以编写类似 @PavanYalamanchili 所做的 C/C++ 基准测试,并比较可用的各种分配器。类似于 this。请记住,MEX 文件具有稍高的 内存管理 开销,因为 MATLAB 自动释放使用 mxCallocmxMallocmxRealloc 函数在 MEX 文件中分配的任何内存。值得一提的是,在旧版本中可以更改内部 内存管理器


编辑:

这里有一个更全面的基准测试,用于比较讨论的替代方法。它特别显示一旦您强调使用整个分配的矩阵,所有三种方法都是相等的,差异可以忽略不计。

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

谢谢Amro提供详细的答案(+1)。但为什么当我使用空矩阵预分配时会获得更好的性能,就像我问题的第二个编辑所展示的那样?这个例子既预分配了一个零矩阵并赋值,但是仍然是空矩阵乘法胜过常规的zeros。另外需要注意的是,我需要每秒预分配约100次,以便对图像进行即时数据分析,因此我尽可能地优化我的代码... - bla
@natan: 我认为其他方法并没有真正地将整个矩阵填充为零值,而是延迟到需要时才进行。我猜测MATLAB在mxArray结构中有一种内部标志来指示这种状态。这就是为什么仅仅进行预分配是具有误导性的原因。我刚刚添加了一个更全面的比较,见编辑。 - Amro
2
顺便提一下,如果您需要重复初始化矩阵,可以使用语法M(:)=0;而不是每次重新创建数组M=zeros(..),我认为这样会稍微快一些...但是,请注意过早优化的问题 :) - Amro
1
@natan:刚刚在 undocumentedmatlab.com 上发布了一篇相关文章。 - Amro

27

在进行了一些研究后,我发现这篇文章来自"未记录的Matlab",其中Yair Altman先生已经得出结论,使用zeros(M,N)预分配矩阵的MathWork方式并不是最有效的方法。

他对比了x = zeros(M,N)clear x, x(M,N) = 0,发现后者快了约500倍。根据他的解释,第二种方法仅创建一个M×N矩阵,其元素自动初始化为0。然而,第一种方法首先创建了x(带有自动零元素),然后再将0分配给x中的每个元素,这是一个多余的操作,需要更多的时间。

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


1
感谢您指引我去看Yair Altman的文章!顺便说一下,我也找到了这个FEX文件 http://www.mathworks.com/matlabcentral/fileexchange/31362-uninit-create-an-uninitialized-variable-like-zeros-but-faster ,它可以优化内存预分配... - bla
@EitanT 对于有趣的答案和undoc mat链接点赞。然而,这如何解释显示n>1000时呈现不同行为的图形? - Shai
3
@EitanT - 直到现在我才知道“unbeknownst”这个词...;-) - Shai
@EitanT 我认为这种行为可能与系统有关。我进行了更多的实验并更新了答案。我能够在C++中重现这种行为。 - Pavan Yalamanchili
@Pavan 很棒!你已经得到了我的投票,不幸的是我没有能力再给你一个 :-) - Eitan T

2
有趣的问题,显然有几种方法可以“击败”内置的zeros函数。我唯一猜测这种情况发生的原因可能是它更加节省内存(毕竟,zeros(LargeNumer)很快就会导致Matlab达到内存限制,而不是在大多数代码中形成严重的速度瓶颈),或者在某种程度上更加健壮。
以下是使用稀疏矩阵的另一种快速分配方法,我已将常规的zeros函数添加为基准:
tic; x=zeros(1000,1000); toc
Elapsed time is 0.002863 seconds.

tic; clear x; x(1000,1000)=0; toc
Elapsed time is 0.000282 seconds.

tic; x=full(spalloc(1000,1000,0)); toc
Elapsed time is 0.000273 seconds.

tic; x=spalloc(1000,1000,1000000); toc %Is this the same for practical purposes?
Elapsed time is 0.000281 seconds.

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接