分配连续内存以包含具有灵活数组成员的多个结构
Allocating contiguous memory to contain multiple structs with flexible array members
考虑一个包含灵活数组成员的结构,如下所示:
typedef struct {
size_t len;
char data[];
} Foo;
我有一个未知数量的 Foos,每个 Foos 的大小都是未知的,但是我可以确定我所有的 Foos 加起来正好是 1024 字节。
在不知道每个Foo的长度之前,如何为一个Foos的数组分配1024字节,然后在后面填充数组的成员?
类似这样的东西,尽管它会引发段错误:
Foo *array = malloc(1024);
int array_size = 0;
Foo foo1;
strcpy(foo1.data, "bar");
array[0] = foo1;
array_size++;
Foo foo2;
strcpy(foo2.data, "bar");
array[1] = foo2;
array_size++;
for (int i = 0; i < array_size; i++)
puts(array[i].data);
想要这样做的原因是为了 CPU 缓存友好性,将所有 Foos 保存在连续的内存区域中。
你不能有一个 foo 数组,因为 foo 没有固定的大小,而数组的定义特征是每个对象都有固定的大小从其索引可计算的基础的大小和偏移量。对于你想要的工作,索引 array[n]
必须知道 foo[0]
、foo[1]
、...、foo[n-1]
的完整大小,这是不可能的,因为语言不知道这些尺寸;实际上,灵活的数组成员只是被排除在大小之外,所以 foo[1]
将 "overlap" 与 foo[0]
的数据。
如果您需要能够以数组的形式访问这些对象,则需要放弃在每个对象中放置一个灵活的数组成员。相反,您可以将所有数据放在末尾,并在每个数据中存储一个指向数据的指针或偏移量。如果您不需要能够将它们作为数组访问,则可以在分配的内存中构建一种链表,将下一个条目的偏移量存储为每个条目的成员。 (例如,请参阅 struct dirent
如何在大多数 Unice 上与 getdents
一起使用。)
正如其他人所指出的,您不能拥有 Foo
的 C 数组。但是,假设您愿意不定期地存储它们并且只需要知道需要多少 space 即可。这个答案表明。
设 N 为 Foo
个对象的数量。
设 S 为 sizeof(Foo)
,这是 Foo
对象的大小,data
.[=44= 为零字节]
设 A 为 _Alignof(Foo)
.
每个 Foo
对象必须从与 A 字节对齐的地址开始。设为 A。填充的最坏情况是 data
数组是一个字节,需要在下一个 Foo
.[= 开始之前跳过 A−1 个字节。 44=]
因此,除了Foo
对象(包括它们的data
)消耗的1024字节,我们可能还需要(N−1)• (A−1) 个字节用于此填充。 (N−1 是因为在最后一个 Foo
之后不需要填充字节。)
如果每个Foo
至少有一个字节data
,最多N可能是floor(1024/( S+1)), 因为我们知道所有 Foo
个对象及其数据最多使用 1024 个字节。
因此 1024 + floor(1024/(S+1)−1)*(A−1) 字节就够了—1024实际数据的字节和 floor(1024/(S+1)−1)*(A−1) 的填充。
注意上面假设每个Foo
至少有一个字节data
。如果一个或多个 Foo
有 data
的零字节,N 可能大于 floor(1024/(S +1))。但是,在任何这样的 Foo
之后,不需要填充,并且 N 对于每个这样的 Foo
不能增加超过 1(因为减少 space 一个字节使用不能超过一个 Foo
)。因此,这样的 Foo
可以在需要 A−1 字节填充的地方再给我们一个 Foo
,但它本身不需要填充,所以总所需的填充量不能增加。
因此,为 Foo
个对象分配内存的计划是:
- 分配1024 + floor(1024/(S+1)−1)*(A−1)字节。
- 将第一个
Foo
放在分配内存的开头。
- 将每个连续的
Foo
放在前一个 Foo
结束后的下一个 A 对齐地址(包括它的 data
) .
当然,这不会产生数组,只是分配的 space 中的大量 Foo
个对象。您将需要指针或其他方式来解决它们。
根据 C 2018 7.22.3.4 2:
The malloc
function allocates space for an object whose size
is specified by size and whose value is indeterminate.
因此,以不规则的方式将 malloc
返回的 space 切碎以用于多个对象并不适合该规范。我会留给其他人讨论,但我没有观察到 C 实现有问题。
考虑一个包含灵活数组成员的结构,如下所示:
typedef struct {
size_t len;
char data[];
} Foo;
我有一个未知数量的 Foos,每个 Foos 的大小都是未知的,但是我可以确定我所有的 Foos 加起来正好是 1024 字节。 在不知道每个Foo的长度之前,如何为一个Foos的数组分配1024字节,然后在后面填充数组的成员?
类似这样的东西,尽管它会引发段错误:
Foo *array = malloc(1024);
int array_size = 0;
Foo foo1;
strcpy(foo1.data, "bar");
array[0] = foo1;
array_size++;
Foo foo2;
strcpy(foo2.data, "bar");
array[1] = foo2;
array_size++;
for (int i = 0; i < array_size; i++)
puts(array[i].data);
想要这样做的原因是为了 CPU 缓存友好性,将所有 Foos 保存在连续的内存区域中。
你不能有一个 foo 数组,因为 foo 没有固定的大小,而数组的定义特征是每个对象都有固定的大小从其索引可计算的基础的大小和偏移量。对于你想要的工作,索引 array[n]
必须知道 foo[0]
、foo[1]
、...、foo[n-1]
的完整大小,这是不可能的,因为语言不知道这些尺寸;实际上,灵活的数组成员只是被排除在大小之外,所以 foo[1]
将 "overlap" 与 foo[0]
的数据。
如果您需要能够以数组的形式访问这些对象,则需要放弃在每个对象中放置一个灵活的数组成员。相反,您可以将所有数据放在末尾,并在每个数据中存储一个指向数据的指针或偏移量。如果您不需要能够将它们作为数组访问,则可以在分配的内存中构建一种链表,将下一个条目的偏移量存储为每个条目的成员。 (例如,请参阅 struct dirent
如何在大多数 Unice 上与 getdents
一起使用。)
正如其他人所指出的,您不能拥有 Foo
的 C 数组。但是,假设您愿意不定期地存储它们并且只需要知道需要多少 space 即可。这个答案表明。
设 N 为 Foo
个对象的数量。
设 S 为 sizeof(Foo)
,这是 Foo
对象的大小,data
.[=44= 为零字节]
设 A 为 _Alignof(Foo)
.
每个 Foo
对象必须从与 A 字节对齐的地址开始。设为 A。填充的最坏情况是 data
数组是一个字节,需要在下一个 Foo
.[= 开始之前跳过 A−1 个字节。 44=]
因此,除了Foo
对象(包括它们的data
)消耗的1024字节,我们可能还需要(N−1)• (A−1) 个字节用于此填充。 (N−1 是因为在最后一个 Foo
之后不需要填充字节。)
如果每个Foo
至少有一个字节data
,最多N可能是floor(1024/( S+1)), 因为我们知道所有 Foo
个对象及其数据最多使用 1024 个字节。
因此 1024 + floor(1024/(S+1)−1)*(A−1) 字节就够了—1024实际数据的字节和 floor(1024/(S+1)−1)*(A−1) 的填充。
注意上面假设每个Foo
至少有一个字节data
。如果一个或多个 Foo
有 data
的零字节,N 可能大于 floor(1024/(S +1))。但是,在任何这样的 Foo
之后,不需要填充,并且 N 对于每个这样的 Foo
不能增加超过 1(因为减少 space 一个字节使用不能超过一个 Foo
)。因此,这样的 Foo
可以在需要 A−1 字节填充的地方再给我们一个 Foo
,但它本身不需要填充,所以总所需的填充量不能增加。
因此,为 Foo
个对象分配内存的计划是:
- 分配1024 + floor(1024/(S+1)−1)*(A−1)字节。
- 将第一个
Foo
放在分配内存的开头。 - 将每个连续的
Foo
放在前一个Foo
结束后的下一个 A 对齐地址(包括它的data
) .
当然,这不会产生数组,只是分配的 space 中的大量 Foo
个对象。您将需要指针或其他方式来解决它们。
根据 C 2018 7.22.3.4 2:
The
malloc
function allocates space for an object whosesize
is specified by size and whose value is indeterminate.
因此,以不规则的方式将 malloc
返回的 space 切碎以用于多个对象并不适合该规范。我会留给其他人讨论,但我没有观察到 C 实现有问题。