我们需要进行预分配。但是MATLAB不会预分配预分配空间?

18

在测试any()是否短路(它确实会!)时,我发现了以下有趣的行为,当预分配测试变量时:

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的大小,因为这会使得最后几个迭代非常慢(由于需要进行高速内存复制),并且还会在我提出的最后一个测试中分配整个数组。所以我的问题是:

到底发生了什么?

有人建议这可能与虚拟内存和物理内存有关,并与操作系统如何看待内存有关。不确定这与此处提出的第一个测试有何关联。更详细的解释将是理想的。

Win 10 x64, MATLAB 2017a


3
相关链接:https://dev59.com/O2Ij5IYBdhLWcg3wsnCn - Cris Luengo
1
链接的重复内容有非常详细的低级别“魔法”解释。这解释了在这篇文章中所能看到的一切。 - Ander Biguri
@rahnema1,最终你需要达到这个细节水平才能理解,但这不是一本书,而是另一个SO答案。如果我有时间,我会考虑撰写一个简短的回答,描述为什么会发生这种情况,并提供链接到那个答案。我编辑了代码,因为它在某个时候被错误地编辑了(由我)。 - Ander Biguri
1个回答

17

这种行为不仅仅出现在MATLAB中。事实上,MATLAB无法控制它,因为这是由Windows引起的。Linux和MacOS表现出相同的行为。

很多年前,我在一个C程序中也注意到了这个问题。事实证明,这是一种被广泛记录的行为。这个优秀的答案详细解释了大多数现代操作系统中内存管理的工作原理(感谢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代表“虚拟大小”,它是分配给程序的虚拟内存的大小。两个量都以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会为进程分配更多的虚拟内存,超出了放入物理内存的容量,假设那些进程不会使用它们被分配的所有内存。这个答案将告诉您有关过度分配的更多内容,远远超过您想知道的范围。

那么 calloc 会发生什么情况呢?它返回零初始化的内存。这也在我之前链接的答案中有所解释。对于小数组, malloc 和 calloc 从程序开始时从更大的池中返回一个内存块。在这种情况下, calloc 将写入所有字节的零,以确保它是零初始化的。但对于较大的数组,则直接从操作系统中获取新的内存块。操作系统始终提供已清零的内存(同样,它可以防止一个程序看到另一个程序的数据)。但由于内存直到使用时才被物理分配,因此清零也会延迟,直到将内存页面放入物理内存为止。
回到MATLAB:
上面的实验表明,可以在恒定时间内获得清零的内存块,并且不改变程序内存的物理大小。这就是MATLAB函数 zeros 分配内存的方式,而您不会看到MATLAB内存占用的任何更改。
实验还显示, zeros 分配了完整的数组(可能通过 calloc ),并且随着逐页使用该数组,内存占用量仅逐页增加。 MathWorks 的预分配建议 指出:
引用:

您可以通过为数组预分配所需的最大空间来提高代码执行时间。

如果我们分配了一个小数组,然后想增加它的大小,就必须分配一个新数组并复制数据。数组如何与RAM关联对此没有影响,MATLAB只看到虚拟内存,它无法控制(甚至不知道?)这些数据在物理内存(RAM)中的存储位置。从MATLAB(或任何其他程序)的角度来看,唯一重要的是数组是一个连续的虚拟内存块。扩大现有的内存块并不总是(通常不是吗?)可能的,因此需要获取新的块并复制数据。例如,请参见在另一个答案中的图表:当数组被扩大时(这发生在大的垂直尖峰处),数据被复制;数组越大,需要复制的数据就越多。
预分配避免了扩大数组的情况,因为我们使其足够大以开始使用。实际上,更有效的方法是制作比我们所需更大得多的数组,因为我们不使用的数组部分实际上从未真正提供给程序。也就是说,如果我们分配了一个非常大的虚拟内存块,并且仅使用了前1000个元素,则我们只会真正使用几个页面的物理内存。
上述calloc的行为也解释了zeros函数的这种奇怪行为:对于小数组,zeros比大数组更昂贵,因为程序需要显式地将小数组清零,而操作系统会隐式地将大数组清零。

1
@Hadi:我不认为MATLAB会做任何这样的事情。我在这里描述的都在操作系统的控制下。操作系统将页面分配给MATLAB,当MATLAB试图使用它们时。MATLAB不需要聪明地使用内存,它只需分配完整数组并像在RAM中一样使用它。操作系统会在使用时将其部分放入RAM中。 - Cris Luengo
2
@Hadi:MATLAB为整个数组分配内存,但在数据被写入之前,操作系统不会向MATLAB分配任何RAM。这就是虚拟内存和物理内存之间的区别。正如我所做的实验所示,当我调用'malloc'时,虚拟内存大小增加了,但直到我向该数组写入数据时,物理内存大小才会增加。 - Cris Luengo
1
@LuisMendo:我已经编辑了答案的最后一部分,现在更清晰了吗? - Cris Luengo
1
@TomMozdzen 我认为你在谈论内存映射文件。你也可以在MATLAB中实现这一点,参见文档。此外,考虑使用高大数组 - Cris Luengo
1
@TomMozdzen 如果您只读取数据一次,内存映射文件不会比您目前的方法更有效。它只是一种在内存中部分加载非常大的数据,或者高效重复读取小文件的方式。您可以使用fread和您的块大小一次性读取一块数据。fseek将移动下一次读取将开始的位置,以便您可以无序地读取块。我建议您发布一个描述您的情况的问题,也许有人有类似问题的经验,并能帮助您找到一个高效的解决方案。 - Cris Luengo
显示剩余10条评论

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