MATLAB如何处理动态数组分配？

Question

我对MATLAB不是很熟悉，想了解它如何在动态内存分配方面处理？

一种主要的方法是分配大块并超出所需量，这样就不必为每个新元素添加而进行分配。在做一些研究时，我看到许多人会自己管理大块分配（假设他们不知道最终大小）或执行创建最大大小，然后再修整等操作。一个例子是Undocumented MATLAB，它建议您自己执行块内存分配。我本以为像MATLAB这样的语言会知道如何自己处理，而我不需要关注此类问题。这意味着，如果您尝试将单个新元素附加到数组上，MATLAB仅为该单个元素分配新的内存，这非常低效。

我的问题有两个：

• 对于动态数组，MATLAB是否分配大块，超出所需量来节省计算效率，还是仅为正在串联的内容分配内存？
• 如果前者是情况，MATLAB选择采用这种设计的原因是什么？

- zephyr

---

这是一个有趣的问题。期待答案的到来。 - rayryeng

一个有趣的问题，但我怀疑你不会得到太多的答案。MathWorks通常不会详细说明MATLAB的内部情况。 - sco1

这是真的，但我本以为有人会知道这个。对于某些算法设计来说，这是一些重要且必要的知识。我想知道是否可以信任MATLAB来处理这个过程，或者我应该自己处理它。 - zephyr

总会有一些白痴提出关闭投票。 - Mad Physicist

@zephyr 如果这是你感兴趣的全部，那么我的回答是：在需要的内存之前预先分配内存总是更好的选择，而不是在循环的每次迭代中增加向量（例如）的大小。 - IKavanagh

Answer 1

我记得在几年前的Matlab Expo上，他们谈到总部正在开发的一些东西之一是 自动预分配 内存。

没有提及何时发布甚至是否会发布...自那以后我从未听说过它...

根据我的经验-我一直自己管理动态分配，并且如果代码的这一部分出现问题（即数组在我认为不应该增长时正在增长...），我总是注意到严重的减速。

因此，我认为您需要自行管理它。

- matlabgui

Answer 2

MATLAB使用固定大小的内存块。当您创建一个新矩阵时，例如使用zeros函数，您只为矩阵及其元数据分配足够的空间。如果您查看MATLAB用于追加到矩阵的符号表示法，它几乎可以自我解释：

>> a = zeros(1, 3)

a =

     0     0     0

>> a = [a 1]

a =

     0     0     0     1

你创建了一个新的矩阵[a 1]（顺便说一下，这是horzcat的别名），然后将其存储在a中。但实际上你不需要将其存回a中，否则你会同时在内存中拥有这两个矩阵。每次连接任意大小的矩阵都会发生这种情况。

另一个指示发生的事情是变量检查器中列出的矩阵大小。如果你注意到，它从来没有声称除了足够存储数据和元数据的空间之外还分配了其他任何空间。

这种设计的目的非常明显。MATLAB使用矩阵。矩阵通常不会发生太大的变化，但它们经常用于创建新矩阵。因此，拥有固定大小的数组和良好的分配机制比预测用户扩展数组的愿望更加重要。如果你尝试将矩阵串联到循环中，MATLAB分析器会告诉你这一点。实验表明，分析器并没有撒谎，这只是语言的主要目的。

所有上述内容也适用于Python中的numpy数组，只不过它更好地记录了文档。

此外，请记住，MATLAB与Java完全集成，因此如果你需要管理良好、可扩展的数组，可以在MATLAB中直接使用java.util.ArrayList。

- Mad Physicist

---

我理解您的观点，即如果在第二个过程之后查看a，MATLAB会将其列为1x4数组，但我认为在幕后它可能已经为潜在的未来连接保留了内存。 - zephyr

为什么？当你添加一些内容时，实际上是创建了一个新的矩阵。MATLAB 的工作假设您希望保留旧的矩阵不变。事实上，即使我在这里写的方式，horzcat 也会返回一个新的矩阵，这意味着在您返回并覆盖 a 之前，旧版本和新版本将同时存在一段时间。 - Mad Physicist

Answer 3

我编写了一个测试函数来推断有关动态分配的一些更具体的细节。该函数位于答案底部。

该函数调用多个位置函数，这些函数从不同长度的对数间隔输入x计算值y。这些函数在循环类型（for和while）和分配方案（动态和预分配）上有所不同。结果来自R2014b。 四个函数的经过时间结果如下所示。

对于低元素计数，运行时间是恒定的；对于高元素计数，所有四个函数都进入具有类似增长率的增长模式。 数据的幂次拟合（即c = ArgMin[c(1)*n^c(2) - time]）返回指数范围为0.93-0.96（线性增长），跨越四个数据集。

我对这些结果感到非常惊讶，因为要么我在测试中漏掉了某些东西，要么Matlab的JIT编译器非常擅长分配数组（可能在幕后使用链表）。 预分配的for循环的运行速度最快，但仅比动态版本快12%。

转向内存消耗，我在数百万元素范围内运行了动态和预分配版本的for循环变体，以进行线性增加的元素计数。Matlab使用的总内存在循环开始和结束时进行采样。结果如下所示。

如图所示，两个函数之间的函数调用起始内存相同（大多数情况下）。预分配版本的内存使用量随着元素计数呈线性增长，这是预期的。但是动态版本使用的内存虽然仍然是分段和趋势线性的，但在几个点上具有内存斜率跳跃。对我来说，这意味着Matlab正在执行某种表格增长（不一定像我认为的Python那样进行表格倍增），以避免在每次迭代中重新分配数组（这确实使我对上面的经过时间讨论中的链表想法产生了疑问）。

---

我发现这些结果很有趣，但除了上面的想法之外，我不能得出更多的结论。 然而，无论如何，在任何数字密集型应用程序中，显式预分配总是更好的，无论是运行时间还是代码维护方面。

当然，欢迎对结果和测试函数提出任何评论（可能讨论这个测试方法有什么问题）。这就是我（我们）学习的方式。

---

function [] = test()

    %   Constants and setup
    funs   = {@forDynamic,@forAllocate,@whileDynamic,@whileAllocate};
    Nfun   = numel(funs)                                            ;
    %
    Nalloc = 2E7                                                    ;
    Nsamp  = 50                                                     ;
    %
    x      = linspace(0,1,Nalloc)                                   ;
    nIndex = round(logspace(1,log10(Nalloc),Nsamp))                 ;
    times  = repmat({zeros(1,Nsamp)},1,Nfun)                        ;

    %   Array growth time-data
    for k = 1:numel(funs)
        f = funs{k};
        for m = 1:Nsamp
            tic;
            f(x(1:nIndex(m)));
            times{k}(m) = toc;
            fprintf(['Iteration ',num2str(m,'%02G'),' of function ',num2str(k),' done.\n']);
        end
    end

    %   Plot
    figure(1);
        args(2:2:2*Nfun) = times;
        args(1:2:2*Nfun) = repmat({nIndex},1,Nfun);
        loglog(args{:});
        legend('Dynamic Allocation (for)','Pre-Allocation (for)','Dyanmic Allocation (while)','Pre-Allocation (while)','Location','Northwest');
        grid('on');
        axis([nIndex(1),nIndex(end),0.95*min([times{:}]),1.05*max([times{:}])]);
        xlabel('Number of Array Elements [-]');
        ylabel('Elasped Time [s]');


    %   Switch to linear scale near allocation max and only look at for-functions
    Nsamp  = 50  ;
    nIndex = round(10.^linspace(log10(Nalloc)-1.5,log10(Nalloc),Nsamp)) ;
    mstart = repmat({zeros(1,Nsamp)},1,Nfun/2)                          ;
    mend   = repmat({zeros(1,Nsamp)},1,Nfun/2)                          ;

    %   Array growth memory-data
    for k = 1:numel(funs)/2
        f = funs{k};
        for m = 1:Nsamp
            [~,mstart{k}(m),mend{k}(m)] = f(x(1:nIndex(m)));
            fprintf(['Iteration ',num2str(m,'%02G'),' of function ',num2str(k),' done.\n']);
        end
    end

    %   Plot
    figure(2);
        mem              = [mstart,mend];
        args(2:2:2*Nfun) = mem          ;
        args(1:2:2*Nfun) = repmat({nIndex},1,Nfun);
        h = plot(args{:});
        set(h([1,2]),'LineStyle','--');
        set(h([1,3]),'Color','k');
        set(h([2,4]),'Color','r');
        legend('Dynamic Allocation Start','Pre-Allocation Start','Dynamic Allocation End','Pre-Allocation End','Location','Northwest');
        grid('on');
        axis([nIndex(1),nIndex(end),0.95*min([mem{:}]),1.05*max([mem{:}])]);
        xlabel('Number of Array Elements [-]');
        ylabel('Matlab Memory Usage [MB]');

end


function y = burden(x)
    y = besselj(0,x);
end

function mem = getMemory()
    mem = memory();
    mem = mem.MemUsedMATLAB/1E6; %[MB]
end

function [y,mstart,mend] = forDynamic(x)

    mstart = getMemory();
    n      = numel(x)   ;
    for k = 1:n
        y(k) = burden(x(k));
    end
    mend = getMemory();

end
function [y,mstart,mend] = forAllocate(x)

    mstart = getMemory();
    n      = numel(x)   ;
    y(1,n) = 0          ;
    for k = 1:numel(x)
        y(k) = burden(x(k));
    end
    mend = getMemory();

end
function [y,mstart,mend] = whileDynamic(x)

    mstart = getMemory();
    n      = numel(x)   ;
    k      = 1          ;
    while k <= n
        y(k) = burden(x(k)) ;
        k    = k + 1        ;
    end
    mend = getMemory();

end
function [y,mstart,mend] = whileAllocate(x)

    mstart = getMemory();
    n      = numel(x)   ;
    k      = 1          ;
    y(1,n) = 0          ;
    while k <= n
        y(k) = burden(x(k)) ;
        k    = k + 1        ;
    end
    mend = getMemory();

end

- TroyHaskin