C - malloc 一次，然后在结构数组上分配内存

Question

我有一个具有以下内存布局的结构：

uint32_t  
variable length array of type uint16_t
variable length array of type uint16_t

由于数组的长度可变，我有效地指向这些数组

：

struct struct1 {
uint32_t n;
uint16_t *array1;
uint16_t *array2;
};
typedef struct struct1 struct1;

现在，在分配这些结构时，我看到两个选项：

A) malloc 结构本身，然后单独 malloc 数组的空间，并将结构中的指针设置为指向正确的内存位置：

uint32_t n1 = 10;
uint32_t n2 = 20;
struct1 *s1 = malloc(sizeof(struct1));
uint16 *array1 = malloc(sizeof(uint16) * n1));
uint16 *array2 = malloc(sizeof(uint16) * n2));
s1->n = n1;
s1->array1 = array1;
s1->array2 = array2;

B)将所有内存组合在一起，然后将内存"分布"到结构体上：

struct1 *s1 = malloc(sizeof(struct1) + (n1 + n2) * sizeof(uint16_t));
s1->n = n1;
s1->array1 = s1 + sizeof(struct1);
s1->array2 = s1 + sizeof(struct1) + n1 * sizeof(uint16_t);

请注意，array1 和 array2 不会大于几 KB，通常不需要很多结构 1。但是，缓存效率是一个问题，因为数字数据处理是使用此结构完成的。

1. 方法B)是否可能，如果这样，在内存局部性方面比A更好(更快)？
2. 我对 C 不是很熟悉，有没有更好的方法来做 B(或 A)，即使用 memcpy 或 realloc 或其他东西？
3. 在这种情况下，还有什么需要注意的吗？

请注意，现在我在Linux上使用gcc(C89？)，但如有必要，可以使用C99/C11。提前谢谢。

编辑：进一步澄清：数组的大小在创建后永远不会改变。多个 struct1 不会总是一次分配，而是偶尔在程序运行时分配。

Answer 1

我认为您的选项 A 更干净，并且会以更合理的方式扩展。想象一下，当其中一个结构中的数组变大时，必须realloc空间：在选项 A 中，您可以realloc该内存，因为它在逻辑上没有附加到其他任何东西。在选项 B 中，您需要添加其他逻辑以确保不会破坏其他数组。

我也认为(即使在 C89 中，但我可能是错的)这没有错：

struct1 *s1 = malloc(sizeof(struct1));
s1->array1 = malloc(sizeof(uint16) * n1));
s1->array2 = malloc(sizeof(uint16) * n2));
s1->n = n1;

上面去掉了中间人阵列。我认为它更干净，因为您可以立即看到您正在为结构中的指针分配空间。

我之前在 2D 数组中使用过您的选项 B，我只分配一个空格并在代码中使用逻辑规则将其用作 2D 空间。当我希望它是一个矩形 2D 空间时，这很有用，所以当我增加它时，我总是增加每一行或每一列。换句话说，我永远不希望有异构数组大小。

更新："数组的大小永远不会改变">

因为您澄清了您的结构/数组永远不需要重新分配，所以我认为选项 B 不那么糟糕。对于此应用程序，它似乎仍然是比选项 A 更糟糕的解决方案，以下是我考虑的原因：

• malloc经过优化，因此与单独分配空间相比，分配单个空间不会有太多优化。
• 其他工程师查看并立即理解您的代码的能力将会降低。需要明确的是，任何称职的软件工程师都应该能够查看选项B并弄清楚代码编写者在做什么，但这很可能会浪费工程师的大脑周期，并可能导致初级工程师误解代码并产生错误。

所以，如果你彻底地注释代码，并且你的应用程序绝对要求你优化所有可能的东西，以牺牲干净和逻辑上合理的代码(内存空间和数据结构以类似的方式在逻辑上分离)，并且你知道这种优化比一个好的编译器(如 Clang)可以做的更好， 那么选项B可能是更好的选择。

更新：测试

本着自我批评的精神，我想看看我是否可以评估差异。所以我写了两个程序(一个用于选项 A，一个用于选项 B)，并在关闭优化的情况下编译它们。我使用 FreeBSD 虚拟机来尽可能干净地访问环境， 我使用了gcc。

以下是我用来测试这两种方法的程序：

选项A.c：

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define NSIZE   100000
#define NTESTS  10000000
struct test_struct {
int n;
int *array1;
int *array2;
};
void freeA(struct test_struct *input) {
free(input->array1);
free(input->array2);
free(input);
return;
}
void optionA() {
struct test_struct *s1 = malloc(sizeof(*s1));
s1->array1 = malloc(sizeof(*(s1->array1)) * NSIZE);
s1->array2 = malloc(sizeof(*(s1->array1)) * NSIZE);
s1->n = NSIZE;
freeA(s1);
s1 = 0;
return;
}
int main() {
clock_t beginA = clock();
int i;
for (i=0; i<NTESTS; i++) {
optionA();
}
clock_t endA = clock();
int time_spent_A = (endA - beginA);
printf("Time spent for option A: %dn", time_spent_A);
return 0;
}

选项B.c：

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define NSIZE   100000
#define NTESTS  10000000
struct test_struct {
int n;
int *array1;
int *array2;
};
void freeB(struct test_struct *input) {
free(input);
return;
}
void optionB() {
struct test_struct *s1 = malloc(sizeof(*s1) + 2*NSIZE*sizeof(*(s1->array1)));
s1->array1 = s1 + sizeof(*s1);
s1->array2 = s1 + sizeof(*s1) + NSIZE*sizeof(*(s1->array1));
s1->n = NSIZE;
freeB(s1);
s1 = 0;
return;
}
int main() {
clock_t beginB = clock();
int i;
for (i=0; i<NTESTS; i++) {
optionB();
}
clock_t endB = clock();
int time_spent_B = (endB - beginB);
printf("Time spent for option B: %dn", time_spent_B);
return 0;
}

这些测试的结果以时钟形式给出(有关更多信息，请参见时钟(3)。

Series | Option A | Option B
------------------------------
1      | 332      | 158
------------------------------
2      | 334      | 155
------------------------------
3      | 334      | 156
------------------------------
4      | 333      | 154
------------------------------
5      | 339      | 156
------------------------------
6      | 334      | 155
------------------------------
avg    | 336.0    | 155.7
------------------------------

请注意，这些速度仍然非常快，并且在数百万次测试中转化为毫秒。我还发现Clang(cc)在优化方面比gcc更好。在我的机器上，即使在编写了将数据写入数组的方法(以确保它们不会被优化为不存在)之后，我在编译时也没有发现两种方法之间的差异cc.

Answer 2

我建议两者的混合：

1. 在一次调用中分配结构(它现在是一个结构数组);

2. 在一次调用中分配数组，并确保大小包括编译器/平台所需的任何填充;

将

3. 数组分布在结构体上，将同义词计入计数。

但是，malloc已经优化，因此您的第一个解决方案仍然是首选。

注意：正如用户 Greg Schmit 的解决方案所指出的那样，如果需要在运行时更改数组大小，一次分配所有数组将导致困难

Answer 3

由于两个数组具有相同的类型，因此基于对 C99 灵活数组成员的创造性使用，还有比这更多的选项。我建议您仅对第二个数组使用指针，

struct foo {
uint16_t *array2;
uint32_t  field;
uint16_t  array1[];
};

并同时为两者分配内存：

struct foo *foo_new(const size_t length1, const size_t length2)
{
struct foo *result;
result = malloc( sizeof (struct foo)
+ length1 * sizeof (uint16_t)
+ length2 * sizeof (uint16_t) );
if (!result)
return NULL;
result->array2 = result->array1 + length1;
return result;
}

注意，对于struct foo *bar，访问两个数组中的元素i分别使用相同的表示法，bar->array1[i]和bar->array2[i]。

---

在科学计算的背景下，我会考虑完全不同的选择，具体取决于访问模式。例如，如果两个数组是同步访问的(在任何方向上)，我会使用

typedef  uint16_t  pair16[2];
struct bar {
uint32_t  field;
pair16    array[];
};

如果数组很大，那么将它们复制到临时缓冲区(上面的pair16数组，如果以锁步访问)可能会有所帮助，但最多只有几千个条目，它可能不会显着提高速度。

如果访问模式依赖于另一个，但您仍然对每个条目进行了足够的计算，那么尽早计算下一个条目的地址可能会很有用__builtin_prefetch()并使用内置的 GCC 告诉 CPU 您很快就会需要它，然后再对当前条目进行计算。它可以减少数据访问延迟(尽管访问预测器在当前处理器上已经非常好)。

对于 GCC(以及在较小程度上在其他常见编译器(如 Intel Compiler Collection、Portland Group 和 Pathscale C 编译器)上)，我注意到操作指针(而不是数组指针和数组索引)的代码在 x86 和 x86-64 上编译为更好的机器代码。(原因其实很简单：对于数组指针和数组索引，你至少需要两个单独的寄存器，而 x86 的寄存器相对较少。即使是 x86-64 也没有那么多。特别是GCC在优化寄存器使用方面不是很强 - 它现在比版本3时代要好得多--,所以这在某些情况下似乎有很大帮助)。例如，如果要按顺序访问struct foo中的第一个数组，则

void do_something(struct foo *ref)
{
uint16_t       *array1 = ref->array1;
uint16_t *const limit1 = ref->array1 + (number of elements in array1);
for (; array1 < limit1; array1++) {
/* ... */
}
}

Answer 4

方法B是可能的，(你为什么不试试呢？)它更好，不是因为内存局部性，而是因为malloc()成本，所以你调用它的次数越少，你就越好。 (假设"更好"意味着"更快"，诚然，情况并不一定如此。

内存局部性仅略有改善，因为所有内存块很可能在内存中都是连续的(一个接一个)，因此，如果您使用方法A，则数组将仅由块头分隔，这些块头不是很大。(每个大约 32 个字节，可能大一点，但不是很多。 你的块不连续的唯一情况是，如果你以前一直在做malloc()和free()，所以你的内存会碎片化。