MATLAB迭代添加数组元素：时间行为

Question

我知道这不是推荐的技术（预分配更好），但我对这种计时行为非常好奇；我很想知道在幕后可能发生了什么。

在我的脑海中，向数组添加一个元素可能会导致内存中出现几种不同的合理行为，具体取决于实现：（1）平摊，添加一个元素的时间就像在链表中保持对最后一个元素的指针一样需要相同的时间，（2）偶尔会花费大量时间来预先分配足够的内存，例如当前列表的两倍（类似于Java数组），（3）比我能想到的更聪明的事情。

MATLAB似乎进行了某些奇怪的操作，我还没有完全理解。似乎成本呈线性增长，并偶尔出现峰值。有什么猜测（或智能解释）它可能正在做什么吗？我通过模拟进行了平均处理（我认为可能隐藏了一些有趣的模式）。

这是当您迭代地将一个元素添加到初始为空的列表的末尾时会发生的情况。为什么成本呈线性增加？那些看似周期性的峰值有没有酷炫的原因？

我用来生成它的代码：

% for averaging over
num_averages = 100000;
% number of simulations
num_sims = 10000;
% the time it takes to add one more item, array
time_store = nan(num_sims, num_averages);

% averaging count
for i = 1:num_averages

    % an array that grows with every loop
    building_array = [];

    for j = 1:num_sims
        tic;
        building_array = [building_array 1];
        time_store(j, i) = toc;
    end
end

plot(mean(time_store, 2)); hold all;
xlabel('Element num'); ylabel('Time');

- Peter Barrett Bryan

Answer 1

这真的很有趣！峰值之间间隔很规律，且曲线在两者之间基本平坦。每个峰值后，曲线会上升一点。不错！我认为这与缓存行有关。您正在测量复制数组的成本，这可能与读写缓存行的成本有关。

如果您替换掉那一行

building_array = [building_array 1];

随着

building_array(end+1) = 1;

那么在每次迭代循环时，您不会复制数据，而是向数组添加一个元素。通过这种改变，我得到了一条基本平直的线，峰值随着对数增加而增加（高度也随之对数增加），这与需要时加倍数组大小的常识实现相一致：

再解释一下：building_array = [building_array 1]会创建一个新的数组，比building_array多一个元素，并将building_array和1复制到其中。然后将其分配给building_array。似乎 MATLAB 的 JIT 还没有为这种代码模式进行优化！

- Cris Luengo

---

希望有人能解释一下这些“spikes”。我理解什么是“plateaus”，但不理解它们之间的这些“spikes”。 - Cris Luengo

有趣的想法。我们应该能够通过尝试malloc实验来看到是否获得相同的对数行为。虽然大小加倍非常规律。-哦，等等，你是指OP的图表吗？每个增量都有一个复制，只是在某些特定大小上，复制操作比附近大小的复制操作需要更长时间。这是一种非常奇怪的行为！ - Cris Luengo

不，我的意思是你在答案中的图表。我不是malloc专家，但这可能与malloc实现如何根据大小将其空闲内存区域组织成“bin”有关。在一个几乎没有其他大块连续内存分配的进程中，数组可以在原地扩展，直到达到bin大小限制，然后它必须移动到更大的bin（即你的峰值），而bin的大小增加约为8的幂。（至少在glibc中，我想是这样的。）它看起来像是“倍增扩展”的向量行为。我不知道OP的图表出了什么问题。 - Andrew Janke

我认识的一位MathWorker说，Matlab确实会在数组末尾分配额外的空间，类似于std::vector的方式，而不仅仅依赖于这种malloc行为，因此(end+1)会向已经分配的内存添加内容，直到达到容量限制时需要重新扩展它，但我还没有能够独立证实这一点。 - Andrew Janke

@AndrewJanke 我花了一些时间才找到这个，一开始使用了所有错误的关键词。但不知何故我记得 MathWorks 的某个人写过一篇关于此事的博客文章。这个优化是在10年前引入的。https://blogs.mathworks.com/steve/2011/05/16/automatic-array-growth-gets-a-lot-faster-in-r2011a/ - Cris Luengo