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 的零矩阵 class double,但空矩阵乘法一要快约 350 倍!tic(使用andtoc和循环会产生类似的结果)

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

编辑:

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

在此处输入图像描述

生成它的代码timeit和以前一样使用,但是带有ticand的循环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)案例类似的结果。

4

4 回答 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,看看你得到了什么时间。

编辑 2013 年 1 月 6 日 7:42 EST

我正在远程使用一台机器,很抱歉低质量的图表(不得不盲目地生成它们)。

机器配置:

i7 920。2.653 GHz。Linux。12 GB 内存。8MB 缓存。

在 i7 920 上生成的图表

看起来即使是我可以访问的机器也显示了这种行为,除了更大的尺寸(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() (zeros(m, n)) 开始使用malloc+ memset,而 g() (zeros(m, 0) * zeros(0, n)) 继续使用calloc

所以分歧由以下解释

  • zeros(..) 开始使用更大尺寸的不同(更慢?)方案。
  • calloc也表现得有些出乎意料,从而提高了性能。

这是 Linux 上的行为。有人可以在不同的机器(可能还有不同的操作系统)上做同样的实验,看看实验是否成立?

于 2013-01-05T07:05:41.477 回答
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 函数比运行脚本或在命令提示符下更快,因为某些优化只会以这种方式发生......

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


在元胞数组或结构数组中可以看到类似的行为。考虑以下示例:

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 函数列表,发现了一些有趣的东西。

  • 有用于创建未初始化数组的未记录函数:mxCreateUninitDoubleMatrixmxCreateUninitNumericArraymxCreateUninitNumericMatrix. 事实上有一个关于File Exchange的提交利用了这些功能来提供更快的替代zeros功能。

  • 存在一个未记录的函数,称为mxFastZeros. 在网上搜索,我可以看到你也在 MATLAB Answers 上交叉发布了这个问题,那里有一些很好的答案。James Tursa(以前是 UNINIT 的同一作者)举例说明了如何使用这个未记录的函数。

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

关于内存分配器的最后一点,您可以在 C/C++ 中编写类似的基准测试,类似于@PavanYalamanchili所做的,并比较各种可用的分配器。像这样的东西。请记住,MEX 文件的内存管理开销稍高,因为 MATLAB 使用mxCallocmxMalloc或函数自动释放在 MEX 文件中分配的任何内存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
于 2013-08-13T19:51:40.230 回答
27

经过一番研究,我在“Undocumented Matlab”中找到了这篇文章,其中Yair Altman 先生已经得出结论,MathWork 使用预分配矩阵的方式确实不是有效的方式。zeros(M, N)

x = zeros(M,N)他对 vs.计时clear x, x(M,N) = 0,发现后者要快 500 倍。根据他的解释,第二种方法只是创建一个 M×N 矩阵,其元素自动初始化为 0。然而,第一种方法创建xx具有自动零元素),然后将零分配给x再次,这是一个需要更多时间的冗余操作。

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

于 2013-01-07T11:48:08.223 回答
2

有趣的问题,显然有几种方法可以“击败”内置zeros功能。对于为什么会发生这种情况,我唯一的猜测是它可能会更有效地使用内存(毕竟,它zeros(LargeNumer)会更快地导致 Matlab 达到内存限制,而不是在大多数代码中形成破坏性的速度瓶颈),或者以某种方式更健壮。

这是另一种使用稀疏矩阵的快速分配方法,我添加了常规零函数作为基准:

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.
于 2013-01-11T10:23:44.067 回答