c++ - 多维数组的动态内存分配背后的算法是什么？

Question

有一次我在编写一个应用程序时，我认为由于索引的缘故，使用 3 维动态分配数组对我来说会很方便。但是我无法使用它，因为它占用的内存比我预期的要多得多。请有人向我解释这背后的算法是什么。为什么在下面的例子中 var2 需要大约。 640 MB 内存而不是 256 MB。在 Dev-C++ 5.11 64 位中测试

#include <iostream>
#include <conio.h>
#include <windows.h>

int main(void)
{
    using namespace std ;

    MEMORYSTATUS memInfo ;
    memInfo.dwLength = sizeof(memInfo) ;

    unsigned char *var0 ;
    unsigned char **var1 ;
    unsigned char ***var2 ;

    GlobalMemoryStatus(&memInfo) ;
    cout << "Free memory:\t" << (memInfo.dwAvailPhys / 1024 / 1024) << " MB" << endl ;

    var0 = new unsigned char[1024 * 1024 * 256] ;
    for(int aa = 0; aa < 1024 * 1024 * 256; aa++)
    var0[aa] = 0x00 ;

    GlobalMemoryStatus(&memInfo) ;
    cout << "Free memory:\t" << (memInfo.dwAvailPhys / 1024 / 1024) << " MB" << endl ;

    delete[] var0 ;

    cout << endl ;

    GlobalMemoryStatus(&memInfo) ;
    cout << "Free memory:\t" << (memInfo.dwAvailPhys / 1024 / 1024) << " MB" << endl ;

    var1 = new unsigned char*[128 * 1024] ;
    for(int aa = 0; aa < 128 * 1024; aa++)
    var1[aa] = new unsigned char[1024] ;

    for(int aa = 0; aa < 128 * 1024; aa++)
    for(int bb = 0; bb < 1024; bb++)
    var1[aa][bb] = 0x00 ;

    GlobalMemoryStatus(&memInfo) ;
    cout << "Free memory:\t" << (memInfo.dwAvailPhys / 1024 / 1024) << " MB" << endl ;

    delete[] var1 ;

    cout << endl ;

    GlobalMemoryStatus(&memInfo) ;
    cout << "Free memory:\t" << (memInfo.dwAvailPhys / 1024 / 1024) << " MB" << endl ;

    var2 = new unsigned char**[16 * 1024] ;
    for(int aa = 0; aa < 16 * 1024; aa++)
    var2[aa] = new unsigned char*[1024] ;
    for(int aa = 0; aa < 16 * 1024; aa++)
    for(int bb = 0; bb < 1024; bb++)
    var2[aa][bb] = new unsigned char[16] ;

    for(int aa = 0; aa < 16 * 1024; aa++)
    for(int bb = 0; bb < 1024; bb++)
    for(int cc = 0; cc < 16; cc++)
    var2[aa][bb][cc] = 0x00 ;

    GlobalMemoryStatus(&memInfo) ;
    cout << "Free memory:\t" << (memInfo.dwAvailPhys / 1024 / 1024) << " MB" << endl ;

    // Why does var2 takes approx. 640 MB of memory ?. 16 *1024 * 1024 * 16 = 256 MB

    cout << "\nPress a key to exit." << endl ;
    getch() ;
    return 0 ;
}

Answer 1

有两个问题，一个是内存管理器的开销。您正在分配大量小块。另一个是指针的大小。

var2 = 新的无符号字符**[16 * 1024] ;

这会分配一 block 足够大的内存来存储 16x1024 个指针。你说你使用的是 64 位编译器，所以每个指针都是 8 个字节。所以这分配了一个 128 KB 的 block 。这是微不足道的，我们不会进一步考虑。

for(int aa = 0; aa < 16 * 1024; aa++) var2[aa] = new unsigned char*[1024] ;

这分配了 16384 个 block ，每个 block 都足够容纳 1024 个指针。因此每个 block 的大小为 8 KB。总共 128 兆字节。

for(int aa = 0; aa < 16 * 1024; aa++) for(int bb = 0; bb < 1024; bb++) var2[aa][bb] = new unsigned char[16] ;

这分配了 16777216 个 block ，每个 block 大小为 16 字节。总共 256 兆字节。

因此，如果内存管理器的开销为零，您将分配大约 384 兆字节。所以我们还有 256 兆字节需要考虑。

当内存管理器分配一个 block 时，会有一些开销来存储有关分配的元数据。具体多少取决于内存管理器的实现。在您的情况下，内存管理器看起来每次分配有 16 个字节(相当于 2 个指针)的开销。

那么现在我们知道问题是什么了，我们可以做些什么呢？

我们可以通过在更大的 block 中分配内存并进行一些指针运算来消除大部分内存管理器开销。

size_t dim1 = 16 * 1024;
size_t dim2 = 1024;
size_t dim3 = 16;
var2 = new unsigned char**[dim1] ;
unsigned char ** tmpa = new unsigned char*[dim1*dim2] ;
for(int aa = 0; aa < dim1; aa++) {
  var2[aa] = tmpa;
  tmpa += dim2;
}
unsigned char * tmpb = new unsigned char[dim1*dim2*dim3];
for(int aa = 0; aa < dim1; aa++) {
  for(int bb = 0; bb < 1024; bb++) {
    var2[aa][bb] = tmpb;
    tmpb += dim3;
  }
}

减少指针的开销是一个技巧。如果您事先对维度的相对大小有所了解，一种选择可能是重新调整阵列设计，使最后一个维度不会那么小。