在动态分配的二维数组中使用realloc()函数是一个好主意吗？

Question

我主要关心缩小这样一个数组的可行性。

我正在开发一个项目，其中我使用单个malloc()调用来创建各自具有适度大的2D数组。（每个数组最多只有几十MiB。）问题是，在数组的生命周期内，其内容会显著缩小（超过一半）。显然，我可以在程序的生命周期内保持数组大小不变。 （在可用GiB内存的系统上仅为x MiB。）但是，我们谈论的是分配空间的一半以上在程序终止之前就处于未使用状态，并且由于我正在使用数组的方式，所有幸存下来的数据都保存在一组连续的行中（在块的开头）。如果我真的不需要它，保留所有那些RAM似乎是一种浪费。

虽然我知道realloc()可以用于缩小动态创建的数组，但2D数组更加复杂。我认为我理解它的内存布局（因为我实现了构造它的函数），但这将推动我的语言和编译器工作原理的理解的极限。显然，我必须处理行（并处理行指针），而不仅仅是字节，但我不知道所有这些的结果有多可预测。

是的，我需要使用单个malloc()创建数组。涉及的对象有数百万行。我尝试使用循环单独malloc()每一行，但程序总是在大约100,000次malloc()处冻结。

背景：我用来构建这些数组的源代码如下：

char ** alloc_2d_arr(int cnum, int rnum) {
        /* ((bytes for row pointers + (bytes for data)) */
        char **mtx = malloc(rnum * sizeof (char *) + rnum * cnum * sizeof (char));

        /* Initialize each row pointer to the first cell of its row */
        char *p = (char *) (mtx + rnum);
        for (int i = 0; i < rnum; i++) {
                mtx[i] = p + i * cnum;
        }

        return mtx;
}

- CircleSquared

---

realloc 不适合用于如此大的表格，可以看看“avl”和“红黑树”。 - David Ranieri

“如果我真的不需要那么多RAM，把它留着好像有点浪费。” - 第一个profile。其次，重新分配内存很可能会触发将所有仍在内部的数据复制到不同页面的高风险，这是您为了尝试节省RAM而承担的非微不足道的费用。这里唯一的胜利场景是realloc保持与您的内存基础相同的区域头，而尾页被返回供其他用途使用；realloc无法保证这一点... - WhozCraig

你是否考虑过只进行2（或3或4等）次分配，记住最终保留哪些分配，并在事件发生后释放不再需要的分配？也就是说，“保留”的矩阵一半在第一个分配中，另一半在另一个分配中，最终只需释放第二个分配。 - WhozCraig

如果您不知道，如果您愿意稍微重构代码，那么指针的前导块是不必要的。通过摆脱它，您可以节省很多空间。 - M.M

Answer 1

使用多维数组，可以使用指向可变长度数组的指针或不使用指针来完成此操作。由于您可能不希望分配任何额外的内存，因此这将在原地完成。

首先分配一个20乘10的数组：

int ( *array )[10] = malloc( sizeof(int ) * 20 * 10 );
for( size_t i = 0 ; i < 20 ; i++ )
    for( size_t j = 0 ; j < 10 ; j++ )
          array[i][j] = i * 100 + j;

如果你想改变行数，不需要移动任何元素，只需要进行重新分配内存即可。将行数更改为15是很简单的：

array = realloc( array , sizeof( int ) * 15 * 10 );

如果要更改列数，那么元素将需要被移动。由于我们不需要复制第一列，所以复制从第二列开始。使用函数memmove来避免内存重叠，在这种情况下不会发生，但如果新的列数更大，则可能会发生。 还可以避免别名问题。请注意，仅因为我们正在使用分配的内存，才定义了此代码。让我们将列数更改为3：

int (*newarray)[3] = ( int(*)[3] )array;
for( size_t j = 1 ; j < 15 ; j++ )
    memmove( newarray[j] , array[j] , sizeof( int ) * 3 );
newarray = realloc( array , sizeof( int ) * 15 * 3 );

示例：https://ideone.com/JMdJO0

如果新列数比旧列数大，则首先必须重新分配内存（仅为获取更多空间），然后进行列复制，从最后一列开始。

- 2501

---

我很惭愧地承认，我对int(*array)[10] = malloc(...);的理解有困难。根据我对C语言的显然不足的理解，这看起来像是用解引用指针作为标识符初始化新创建的变量。如果将malloc()输出解引用三级指针（两次）并将其赋值给该指针，那就没问题了，但在前面放一个类型，看起来就像是使用RAM地址作为符号（这是没有意义的）。我感觉在学习C语言时见过这个东西，但搜索相关术语显然会得到污染的结果。 - CircleSquared

@CircleSquared 它是一个指向多维数组的指针。在我的例子中有两个维度。像这样：int a[7][9]; int(*pa)[9]=a;，除了在我的例子中我没有将该指针指向自动数组，而是指向已分配的内存。 - 2501

谢谢您向我展示了一种更高效的动态分配多维数组的方法，除了简单地回答我的问题。因此，这是一个安全的方法，但这是设置数组的更好方法。 - CircleSquared