C动态分配速度问题

我正在使用此代码动态创建一个2d数组：

char **FileTables;
int rows = 1000;
int i;
FileTables = (char**)malloc(rows * sizeof(char));
for (i = 0; i < rows; i++) {
    FileTables[i] = (char*)malloc(256 * sizeof(char));
}

问题是1000行，可能还有更多，分配所有内存需要几秒钟的时间。有什么更快/更好的方法可以做到这一点吗？

编辑：除了明显更简单的代码之外，使用其中一种方法比使用另一种方法有优势吗？

char **FileTables;
int rows = 1000;
int i;
FileTables = malloc(rows * sizeof(char*));
FileTables[0] = malloc(rows * 256 * sizeof(char));
for (i = 0; i < rows; i++) {
    FileTables[i] = FileTables[0] + i * 256;
}

而且。。

char (*FileTables)[256];
int rows = 1000;
FileTables = malloc(rows * sizeof(*FileTables));

(是的，我修复了不必要的铸造(

您只需要两个分配和一些指针运算：

int rows = 1000;
int cols = 256;
char *data;
char **FileTables;
int i;
data = malloc(rows * cols);
FileTables = malloc(rows * sizeof(char*));
for (i = 0; i < rows; i++) {
    FileTables[i] = data + i * cols;
}

还要注意，我修复了malloc(rows * sizeof(char))中的一个错误(sizeof(char)应该是sizeof(char*)，因为您正在为char分配指针的数组(。

只要列的数量是恒定的，或者如果您使用C99，您就可以使用单个malloc，而不必自己进行难看的行/列寻址算法：

char (*FileTables)[256] = malloc(rows * sizeof *FileTables);

如果数组的大小始终为row×256，那么您可以考虑一维数组malloc(row * 256)，并逐步访问它：

char get(unsigned i, unsigned j, char * array) { return array[j + 256 * i]; }
void set(char value, unsigned i, unsigned j, char * array) { array[j + 256 * i] = value; }

这样可以避免多次分配，并提供更好的内存局部性。除此之外，您还可以选择行或列排序进行微优化。

char **FileTables; 
int rows = 1000; 
int i; 
FileTables = (char**)malloc(rows * sizeof(char *)); 
char *data = (char *)malloc(256 * 1000 * sizeof(char));
for (i = 0; i < rows; ++i) { 
    FileTables[i] = data;
    data += 256 * sizeof(char);
}

应该是一个更好的解决方案。

我不相信你会接近秒。在我的机器上，将行数增加到1000万仍然不到一秒钟。

然而，如果你想尽量减少分配，你只需要一个。

FileTables = (char**) malloc(rows * (sizeof(char *) + 256*sizeof(char)));
FileTables[0] = (char *) &FileTables[rows];
for (i = 1; i < rows; i++) {
    FileTables[i] = FileTables[i-1] + 256 * sizeof (char);
}
free(FileTables);

一种更有效的方法是避免第二级的间接性。

typedef char chars[256];
int main(int argc, char** argv) {
    chars* FileTables;
    int rows = 100000000;
    int i;
    FileTables = (chars*) malloc(rows * sizeof (chars));
    free(FileTables);
    return (EXIT_SUCCESS);
}

这避免了指针查找，因为C可以计算其余部分。

首先，你确定是内存分配问题吗？分配1000个内存块通常不需要几秒钟。

如果您有特殊需求，您可以研究替代malloc实现(例如，如果您在线程中分配内存，则可以使用谷歌的tcmalloc(。

否则，malloc真正"慢"的部分实际上是从操作系统中获取内存(使用sbrk((或mmap(((，大多数malloc实现都会一次获取一大块内存，并将其以较小的部分返回，因此这里没有1000个调用来分配每个1k，可能有60个调用可以分配16k。在strace或类似情况下运行程序可能会让您了解实际进行了多少缓慢的系统调用。。您可以自己实现类似的行为，只需进行一次调用来分配256K，并将其细分为更小的块。您可以尝试分配一大块内存，然后立即释放((，并希望库malloc保留该内存，不再返回操作系统获取更多内存。

这看起来确实是过早的优化；因为，你要求更快，但你还没有指出有多快就足够快。不过，如果你真的需要这样做。。。

加快分配的提示：

减少分配
进行较小的分配

正如您所看到的，如果您需要分配10M，这些提示很快就会发生冲突。为了在较小和较少的分配之间确定正确的平衡，on需要进行分析。

查看您的内存块大小，并一次分配整页内存。这是一个旧的硬件破解，但它确实保证了你不会一次要求多页连续内存(这加快了从空闲页面列表中选择的速度(，而且它还确保了你不会因为要求内存管理器的块保留子系统已经保留的地址而浪费一些周期的地址空间。

如果这不能为您提供所需的性能，那么重写代码，使其不需要按照呈现的方式进行分配。

无论哪种方式，如果不详细了解计算机上的内存管理子系统的实际设计，都不可能保证最佳分配速度。

相关内容

最新更新

热门标签：