我们需要预先分配.但是MATLAB没有预先分配预分配？

Question

在测试是否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使用的内存时,我可以看到当停止时,它只使用了50%的test所需内存(如果已满).这可以用不同的记忆百分比再现.

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

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

我知道MATLAB不是动态分配和增加test循环的大小,因为这会使结束迭代非常慢(由于需要高memcopys),并且它也会在我提出的最后一次测试中分配整个数组.所以我的问题是:

到底是怎么回事？

有人建议这可能与虚拟内存和物理内存有关,并且与操作系统看待内存的方式有关.不知道如何链接到这里提出的第一个测试.任何进一步的解释都是理想的.

赢得10 x64,MATLAB 2017a

Answer 1

这种行为并不是MATLAB独有的.事实上,MATLAB无法控制它,因为它是导致它的Windows.Linux和MacOS显示相同的行为.

多年前我在C程序中注意到了这一点.事实证明,这是记录良好的行为.这个出色的答案详细解释了内存管理在大多数现代操作系统中的工作原理(感谢Amro分享链接!).如果这个答案没有足够的细节,请阅读它.

首先,让我们重复Ander在C中的实验:

#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代表"Resident set size",它是程序正在使用的物理内存(RAM)的数量.VSZ代表"虚拟大小",它是分配给程序的虚拟内存的大小.两个数量都是KiB.

VSZ列在程序启动时显示4 GiB.我不确定那是什么,它似乎超过顶部.但是这个值在之后malloc和之后calloc都会增长,两次都有大约98,000 KiB(略高于我们分配的1e8字节).

相反,在我们分配1e8字节后,RSS列显示仅增加了16 KiB.写入数组的一半后,我们使用了超过5e7字节的内存,写入完整数组后,我们使用了超过1e8字节.因此,在我们使用它时,内存会被分配,而不是在我们第一次请求它时.接下来,我们使用分配另外的1e8字节calloc,并且看不到RSS的变化.注意,calloc返回一个初始化为0的内存块,就像MATLAB zeros一样.

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

说明:

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

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

有些操作系统,比如Linux,甚至会"过度使用"内存.Linux将为进程分配更多的虚拟内存,而不是它具有放入物理内存的能力,假设这些进程不会使用它们分配的所有内存.这个答案将告诉你更多的过度使用,而不是你想知道的.

那么会发生什么calloc,它会返回零初始化内存？我之前链接的答案也解释了这一点.对于小型数组,malloc并calloc从程序开始时从OS获得的较大池中返回一块内存.在这种情况下,calloc将零写入所有字节以确保它是零初始化.但对于较大的阵列,可直接从OS获取新的内存块.操作系统总是给出被清零的内存(同样,它会阻止一个程序查看来自另一个程序的数据).但是因为在使用之前内存没有被物理分配,所以归零也会延迟,直到将内存页面放入物理内存.

回到MATLAB:

上面的实验表明,可以在恒定时间内获得一个归零的内存块,而无需改变程序内存的物理大小.这就是MATLAB的功能zeros在没有看到MATLAB内存占用的任何变化的情况下分配内存的方式.

该实验还显示zeros分配完整数组(可能通过calloc),并且内存占用量仅在使用此数组时增加,一次一页.

MathWorks的预分配建议指出

您可以通过预分配阵列所需的最大空间来缩短代码执行时间.

如果我们分配一个小数组,然后想要增加它的大小,则必须分配一个新数组并复制数据.数组如何与RAM相关联对此没有影响,MATLAB只能看到虚拟内存,它无法控制(甚至知道？)物理内存(RAM)中存储这些数据的位置.从MATLAB的角度(或任何其他程序的角度)来看,数组的重要性在于该数组是一个连续的虚拟内存块.扩展现有的内存块并不总是(通常不是？),因此可以获得新块并复制数据.例如,请参阅另一个答案中的图表:当数组被放大时(这发生在大的垂直尖峰处),数据被复制; 数组越大,需要复制的数据就越多.

预分配避免了扩大阵列,因为我们使它足够大以便开始.事实上,制作一个对我们需要的太大的数组更有效率,因为我们不使用的数组部分实际上从未真正给予程序.也就是说,如果我们分配一个非常大的虚拟内存块,并且只使用前1000个元素,我们将只使用几页物理内存.

calloc上面描述的行为也解释了zeros函数的另一个奇怪的行为:对于小数组,zeros比大数组更昂贵,因为小数组需要由程序显式归零,而大数组被OS隐式归零.