C动态分配速度问题

Question

我使用这段代码动态创建一个二维数组：

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));

（是的，我修复了不必要的演员）

Answer 1

您只需两次分配和一些指针算术即可逃脱：

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）。

Answer 2

只要列数不变，或者如果您使用的是 C99，您就可以使用单个 malloc ，而不必自己执行丑陋的行/列寻址算术：

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

Answer 3

如果数组的大小始终为 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; }

这可以避免多次分配并提供更好的内存局部性。最重要的是，您可以选择行或列顺序进行微观优化。

Answer 4

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);
}

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

Answer 5

我不相信你能达到接近秒的速度。在我的机器上将行数增加到 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 可以计算其余部分。

Answer 6

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

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

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

Answer 7

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

加快分配速度的提示：

1. 减少分配 减少
2. 分配

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

查看内存块大小并立即分配整页内存。这是一个古老的硬件黑客，但它确实保证您不会一次请求多个连续内存页（这可以加快从空闲页列表中的选择速度），并且它还保证您不会浪费一些周期地址通过请求内存管理器的块保留子系统已保留的地址来分配空间。

如果这不能让您获得所需的性能，请重写代码以不需要按照其呈现的方式进行分配。

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