有什么工具可以优化C语言的结构大小吗?

Question

寻找一种以C结构为输入并输出最小尺寸结构的工具。

例如，给定一个只有3个成员的初始结构

struct Book {
char  title[50];
char  author[25];
int   book_id;
};

有6种排列

struct Book1 {
char  title[50];
char  author[25];
int   book_id;
};
struct Book2 {
char  title[50];
int   book_id;
char  author[25];   
};
struct Book3 {
char  author[25];     
char  title[50];
int   book_id; 
};
struct Book4 {
char  author[25];     
int   book_id; 
char  title[50];   
};
struct Book5 {
int   book_id; 
char  author[25];     
char  title[50];   
};
struct Book6 {
int   book_id; 
char  title[50];     
char  author[25];     
};

输出显示80字节是最小值

Book1 = 80
Book2 = 84
Book3 = 80
Book4 = 84
Book5 = 80
Book6 = 80

我工作的几个项目包含10+成员的结构(3628800个排列)并且由不熟悉结构打包复杂性的程序员不断地添加新成员。

是否有可能有一个工具将结构重构成最佳的最小尺寸?

Answer 1

假设任何成员的大小是其对齐要求的倍数，即2的幂，则可以通过将具有最严格对齐的成员放在首位来找到最佳布局。成员之间没有内部填充。结构体的总大小将是其所有成员的和，四舍五入到第一个成员的最严格对齐方式，这是一个下界。

Answer 2

只要您的结构包含本机类型并且没有复合结构，那么就有一个非常好的启发式(当然是最优的)来解决这个问题:根据字段的对齐约束按降序排序。原生类型的对齐约束应该是它的大小，而数组的对齐约束是项目类型的大小(例如:1表示字符数组)。我认为这种启发式方法对于具有2次方大小的复合结构，或者如果您的所有子结构的大小在64位平台上是8的倍数(除了最后一个无关紧要)，也肯定是最佳的。例如，假设int在4字节上对齐，那么它将被放在第一位，然后是两个数组，无论项目的数量如何(两者的总体大小相同)。

对于复合结构，我认为这个问题更难解决。它类似于分配器算法用于将数据打包到堆中(以便最小化空间开销)。分配器具有相同的约束:分配的类型必须遵循对齐约束，同时最小化总体空间，尽管它们通常还具有额外的约束:速度快。aligned_alloc函数就是一个很好的例子。许多算法使用桶策略来有效地解决这个问题，尽管解决方案可能不是最优的。

请注意，像GCC这样的编译器有扩展来打包数据结构，但它们不符合C标准。