matlab - 我们需要预先分配。但是MATLAB没有预分配预分配？

Question

测试时是否 any()短路(确实如此!)当 preallocating 时，我发现了以下有趣的行为测试变量:

test=zeros(1e7,1);
>> tic;any(test);toc
Elapsed time is 2.444690 seconds.
>> test(2)=1;
>> tic;any(test);toc
Elapsed time is 0.000034 seconds.

但是，如果我这样做:

test=ones(1e7,1);
test(1:end)=0;
tic;any(test);toc
Elapsed time is 0.642413 seconds.
>> test(2)=1;
>> tic;any(test);toc
Elapsed time is 0.000021 seconds.

事实证明，发生这种情况是因为变量在完全填充信息之前并不真正在 RAM 上，因此第一次测试需要更长的时间，因为它需要分配它。我检查的方法是查看 Windows 任务管理器中使用的内存。

虽然这可能有一定道理(在需要之前不要初始化)，但让我更困惑的是以下测试，其中变量被填充到 for 循环中，并在某个时候停止执行。

test=zeros(1e7,1);

for ii=1:1e7
    test(ii)=1;
    if ii==1e7/2
        pause
    end
end

在检查 MATLAB 使用的内存时，我可以看到停止时它仅使用了 test 的 50%。需要的内存(如果已满)。这可以用不同的内存百分比非常可靠地再现。

有趣的是，以下内容也没有分配整个矩阵。

test=zeros(1e7,1);
test(end)=1;

我知道 MATLAB 不会动态分配和增加 test 的大小在循环中，因为这会使结束迭代非常缓慢(由于需要的内存副本很高)，并且它还会在我提议的最后一个测试中分配整个数组。所以我的问题是:

到底是怎么回事？

有人建议这可能与虚拟内存与物理内存有关，也与操作系统如何看待内存有关。不确定如何链接到此处提出的第一个测试。任何进一步的解释都是理想的。

赢 10 x64，MATLAB 2017a

Answer 1

这种行为不是 MATLAB 独有的。事实上，MATLAB 无法控制它，因为它是 Windows 导致的。 Linux 和 MacOS 表现出相同的行为。

多年前，我在 C 程序中注意到了完全相同的事情。事实证明，这是有据可查的行为。 This excellent answer详细解释了大多数现代操作系统中内存管理的工作原理(感谢 Amro 分享链接!)。如果此答案对您来说不够详细，请阅读它。

首先，让我们用 C 语言重复 Ander 的实验:

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>

int main (void) {

   const int size = 1e8;

   /* For Linux: */
   // const char* ps_command = "ps --no-headers --format \"rss vsz\" -C so";
   /* For MacOS: */
   char ps_command[128];
   sprintf(ps_command, "ps -o rss,vsz -p %d", getpid());

   puts("At program start:");
   system(ps_command);

   /* Allocate large chunck of memory */

   char* mem = malloc(size);

   puts("After malloc:");
   system(ps_command);

   for(int ii = 0; ii < size/2; ++ii) {
      mem[ii] = 0;
   }

   puts("After writing to half the array:");
   system(ps_command);

   for(int ii = size/2; ii < size; ++ii) {
      mem[ii] = 0;
   }

   puts("After writing to the whole array:");
   system(ps_command);

   char* mem2 = calloc(size, 1);

   puts("After calloc:");
   system(ps_command);

   free(mem);
   free(mem2);
}

上面的代码适用于符合 POSIX 的操作系统(即除 Windows 之外的任何操作系统)，但在 Windows 上你可以使用 Cygwin成为(主要)符合 POSIX 的。您可能需要更改 ps命令语法取决于您的操作系统。编译 gcc so.c -o so , 运行 ./so .我在 MacOS 上看到以下输出:

At program start:
   RSS      VSZ
   800  4267728
After malloc:
   RSS      VSZ
   816  4366416
After writing to half the array:
   RSS      VSZ
 49648  4366416
After writing to the whole array:
   RSS      VSZ
 98476  4366416
After calloc:
   RSS      VSZ
 98476  4464076

有两列显示，RSS 和 VSZ。 RSS 代表“常驻集大小”，它是程序使用的物理内存 (RAM) 量。 VSZ 代表“Virtual size”，它是分配给程序的虚拟内存的大小。两个数量都以 KiB 为单位。

VSZ 列在程序启动时显示 4 GiB。我不确定那是什么，它似乎超出了顶部。但值在 malloc 之后增长之后又是 calloc ，两次都大约为 98,000 KiB(略超过我们分配的 1e8 字节)。

相比之下，RSS 列显示在我们分配 1e8 字节后仅增加了 16 KiB。写入一半数组后，我们有超过 5e7 字节的内存在使用，写入完整数组后，我们有超过 1e8 字节的内存在使用。因此，内存在我们使用时分配，而不是在我们第一次请求时分配。接下来，我们使用 calloc 再分配 1e8 个字节。 ，并且在 RSS 中没有看到任何变化。请注意 calloc返回一个初始化为 0 的内存块，就像 MATLAB 的 zeros做。

我说的是 calloc因为很可能是 MATLAB 的 zeros通过 calloc 实现.

说明:

现代计算机体系结构独立 虚拟内存 (进程看到的内存空间)来自 物理内存 .进程(即程序)使用指针来访问内存，这些指针是虚拟内存中的地址。这些地址由系统翻译成物理地址 使用时 .这有许多优点，例如，一个进程不可能寻址分配给另一个进程的内存，因为它可以生成的地址都不会被转换为未分配给该进程的物理内存。它还允许操作系统换出空闲进程的内存，让另一个进程使用该物理内存。请注意，连续虚拟内存块的物理内存不需要是连续的!

关键是上面加粗斜体的文字: 使用时 .分配给进程的内存可能实际上不存在，直到进程尝试读取或写入它。这就是为什么在分配大数组时我们看不到 RSS 的任何变化。使用的内存分配给页面中的物理内存(块通常为 4 KiB，有时高达 1 MiB)。因此，当我们写入新内存块的一个字节时，只会分配一页。

一些操作系统，比如 Linux，甚至会“过度使用”内存。 Linux 将分配给进程的虚拟内存多于它可以放入物理内存的容量，前提是这些进程无论如何都不会使用它们分配的所有内存。 This answer会告诉你比你想知道的更多的过度使用。

那么 calloc 会发生什么？ ，它返回零初始化内存？这也在 the answer I linked earlier 中有解释.对于小型阵列 malloc和 calloc从程序开始时从操作系统获得的更大池中返回一块内存。在这种情况下， calloc将向所有字节写入零以确保它是零初始化的。但是对于更大的数组，直接从操作系统获取新的内存块。操作系统总是提供归零的内存(同样，它会阻止一个程序查看另一个程序的数据)。但是因为内存在使用之前不会被物理分配，清零也会延迟，直到内存页面被放入物理内存。

回到 MATLAB:

上面的实验表明，在不改变程序内存的物理大小的情况下，可以在恒定时间内获得清零的内存块。这就是 MATLAB 的函数 zeros分配内存，而您看不到 MATLAB 内存占用的任何变化。

实验还表明 zeros分配整个数组(可能通过 calloc )，并且内存占用只会随着使用该数组而增加，一次一页。

The preallocation advice by the MathWorks指出

you can improve code execution time by preallocating the maximum amount of space required for the array.

如果我们分配一个小数组，然后想要增加它的大小，则必须分配一个新数组并复制数据。数组如何与 RAM 相关联对此没有影响，MATLAB 只看到虚拟内存，它无法控制(甚至不知道？)这些数据存储在物理内存 (RAM) 中的位置。从 MATLAB 的观点(或任何其他程序的观点)来看，对于数组而言，所有重要的是数组是一个连续的虚拟内存块。扩大现有内存块并不总是(通常不可能？)，因此获得一个新块并复制数据。例如，参见 the graph in this other answer :当阵列被放大时(这发生在大的垂直尖峰)数据被复制；数组越大，需要复制的数据就越多。

预分配避免扩大数组，因为我们使它足够大开始。事实上，创建一个对于我们需要的数组来说太大的数组更有效，因为我们不使用的数组部分实际上从未真正提供给程序。也就是说，如果我们分配一个非常大的虚拟内存块，并且只使用前 1000 个元素，我们将只使用几页物理内存。
calloc的行为上面描述的也解释了 this other strange behavior of the zeros function :对于小阵列， zeros比大数组更昂贵，因为小数组需要由程序显式清零，而大数组由操作系统隐式清零。