有没有工具可以优化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种排列方式）的结构，并且不熟悉结构打包复杂性的开发人员会不断添加新成员。

问题

是否可能有一个工具来重构结构以获得最佳的最小尺寸？

- vengy

---

相关问题：https://dev59.com/EnNA5IYBdhLWcg3wrf83 - Aziz

虽然成员有3,628,800种排列方式，但由于许多成员具有相同的内存布局（大小、对齐和步幅），因此很多排列方式在内存布局方面是等效的。因此，实际的排列方式数量不是numberOfMembers!，而是numberOfMembersWithUniqueLayout!。此外，不需要使用蛮力算法。您可以使用一种懒惰算法，按照从大到小的顺序排列成员，并可靠地获得最佳结果。 - Alexander

@JérômeRichard，我认为这个问题可以通过动态规划来解决，通过计算将成员子集（编码为整数的位）映射到最小偏移量的函数来实现。 - tstanisl

请参阅结构体打包的失落艺术。 - Ouroborus

如果考虑位域，这个问题就变得非常有趣了。 - tstanisl

Answer 1

假设任何成员的大小都是其对齐需求的倍数，这些需求都是2的幂，则可以通过首先放置具有最严格对齐要求的成员来找到最佳布局。成员之间不会有内部填充。结构体的总大小将是其成员的总和，舍入到具有最严格对齐要求的第一个成员的对齐方式，无论如何这是下限。

- tstanisl

Answer 2

只要你的结构包含原生类型，并且没有复合结构，那么有一个非常好的启发式方法（肯定是最优的）来解决这个问题：根据它们的对齐约束，按照递减顺序对字段进行排序。原生类型的对齐约束应该是其大小，而对于数组来说，它是项类型的大小（例如，char数组为1）。我认为，对于具有二次幂大小的复合结构，或者如果所有子结构的大小在64位平台上都是8的倍数（除了最后一个无关紧要），这种启发式方法也肯定是最优的。例如，假设int在4字节上对齐，那么它将被放在第一位，然后是两个数组，无论项数是多少（两者结果的总体大小相同）。

对于复合结构，我认为解决这个问题会稍微困难一些。它类似于分配器算法在堆中打包数据以最小化空间开销时使用的方法。分配器具有相同的约束：分配的类型必须遵循对齐约束，同时尽量减少整体空间，尽管它们通常还有一个额外的约束：速度要快。一个很好的例子是aligned_alloc函数。许多算法使用桶策略来高效解决这个问题，尽管解决方案可能不是最优的。

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

- Jérôme Richard