logo标签列表

C结构体中自动重新排序字段以避免填充。

cdata-structuresmemory-optimization
14

我手动花费几分钟重新排列一个结构体的字段，以减少填充效应[1]，但感觉这样做浪费了时间。我的直觉告诉我，我可能最好编写Perl脚本或其他程序来为我执行这种优化工作。

我的问题是，这是否也是多余的; 是否已经有我不知道的一些工具或者一些编译器特性可以帮助我对结构体进行打包[2]？

问题更加复杂的是，这需要在几个不同的架构中进行一致的优化，因此使用的任何工具都需要能够考虑不同的结构对齐和指针大小。

编辑：快速澄清 - 我想做的是重新排列源代码中的字段，以避免填充，而不是”打包”结构，在编译时没有填充。

编辑#2：另一个问题是，根据配置，一些数据类型的大小也可能会发生变化。显而易见的是，指针和指针差异对于不同的架构是不同的，但还有浮点数类型（16、32或64位，取决于“精度”）、校验和（8或16位，取决于“速度”）以及一些其他非明显的内容。

[1] 相关的结构体在嵌入式设备上被实例化成千上万次，因此每减少4个字节的结构体可能意味着该项目的成功或失败。

[2] 可用的编译器包括GCC 3.*和4.*，Visual Studio，TCC，ARM ADS 1.2，RVCT 3.*和其他一些更加晦涩的编译器。

1
这个结构体的实例需要在设备之间可移植吗？还是每个架构都有自己的打包方式也可以？ - Alnitak
1
仅仅是顺便一提：我觉得这是一个有趣的问题，然后搜索了“perl struct reordering”。结果就是这个。这个问题只有15分钟的历史！ - Paul Dixon
1
Alnitak - 是的，这实际上是需要极其便携的代码 :) 每个体系结构都有自己的结构定义也是可以接受的 -- 但手工编写特定于体系结构的定义是不切实际的。 - Christoffer
9个回答
10
如果您需要尽可能地利用存储空间中的每个单词，那么我建议手动优化结构体。虽然工具可以为您安排最佳成员顺序，但它不知道例如您在16位中存储的这个值实际上从不超过1024，因此您可以在这里从这个值中窃取上6位来存储这里的值...
因此，人类几乎肯定会比机器更擅长这项工作。
[编辑] 但是看起来您真的不想为每个架构手动优化结构体。也许您确实要支持很多架构？
我认为这个问题不适合一般性解决方案，但您可能能够将领域知识编码到自定义的Perl/Python/某些脚本中，以为每个架构生成结构体定义。
此外，如果所有成员的大小都是2的幂次方，那么通过按大小排序成员（从最大开始），您将获得最佳的打包效果。在这种情况下，您只需使用老式的基于宏的结构体构建方法-类似于以下内容：
#define MYSTRUCT_POINTERS      \
    Something*  m_pSomeThing;  \
    OtherThing* m_pOtherThing; 

#define MYSTRUCT_FLOATS        \
    FLOAT m_aFloat;            \
    FLOAT m_bFloat;

#if 64_BIT_POINTERS && 64_BIT_FLOATS
    #define MYSTRUCT_64_BIT_MEMBERS MYSTRUCT_POINTERS MYSTRUCT_FLOATS
#else if 64_BIT_POINTERS
    #define MYSTRUCT_64_BIT_MEMBERS MYSTRUCT_POINTERS
#else if 64_BIT_FLOATS
    #define MYSTRUCT_64_BIT_MEMBERS MYSTRUCT_FLOATS
#else
    #define MYSTRUCT_64_BIT_MEMBERS
#endif

// blah blah blah

struct MyStruct
{
    MYSTRUCT_64_BIT_MEMBERS
    MYSTRUCT_32_BIT_MEMBERS
    MYSTRUCT_16_BIT_MEMBERS
    MYSTRUCT_8_BIT_MEMBERS
};
直到有人制造出更聪明的机器人（来做这份工作）！ - Sandeep Datta
同意；这里涉及到很多依赖于上下文的知识。当然，如果你有大量的结构，并且你可以将所有的知识嵌入到一个工具可以使用的格式中，那么自动化可能是可行的。 - Steve Melnikoff
谢谢你的回答。我有一个关于最优排序的问题。在你的回答中，你提到最优排序是从大到小排序。这个说法有什么证明吗？我尝试了很多情况，但都无法打破这个说法，所以我想知道如何证明它。非常感谢。 - yoco
2
从大到小排序通常不是最优的。一般情况下是二进制装箱问题，这是NP难问题 - 如果你好奇，可以在谷歌上找到一些有趣的结果。只有在大小为2的幂的特殊情况下，它才能完美地打包，不留任何间隙；仅仅通过观察这种情况就很容易看出原因。每个大小为2^k的对象都以2^k对齐的边界结束，这也是2^k-1对齐的边界，因此“向下跨步”到较低的大小永远不会导致间隙。 - Charlie
按大小排序，以2的最大幂因子为关键因素，同时保留原始位置，这是二进制计算机（即现今几乎所有计算机）在没有特殊知识的情况下所能做到的最好的排序方式。因为所需和最佳对齐方式总是2的幂次方和尺寸的除数。当然，如果常见的初始序列或第一个成员很重要，则需要额外小心处理。 - Deduplicator
8

通常情况下，Perl安装包中都会包含一个名为pstruct的脚本。该脚本可以输出结构体成员的偏移量和大小。你可以修改pstruct脚本，或者以其输出作为起点，制作一个按照你想要的方式打包结构体的工具。

$ cat foo.h 
struct foo {
    int x;
    char y; 
    int b[5];
    char c;
};

$ pstruct foo.h
struct foo {
  int                foo.x                      0       4
  char               foo.y                      4       1
                     foo.b                      8      20
  char               foo.c                     28       1
}
好主意，但似乎pstruct在C++中有问题 :-( - Jérôme Pouiller
4
大多数C编译器不会这样做，因为您可以做一些奇怪的事情（例如获取结构体中元素的地址，然后使用指针技巧访问其余部分，绕过编译器）。一个著名的例子是AmigaOS中使用守护节点作为列表的头和尾的双向链表（这使得在遍历列表时可以避免ifs）。守护头节点始终具有pred == null，而尾节点则具有next == null，开发人员将两个节点合并为单个三指针结构head_next null tail_pred。通过使用head_next的地址或null作为头和尾节点的地址，他们节省了四个字节和一个内存分配（因为他们只需要整个结构一次）。
因此，您最好将结构编写为伪代码，然后编写预处理程序脚本从中创建真实结构。
2
没有任何 C 编译器会这样做，因为那样会违反规范，规范要求结构体中的字段必须按照声明的顺序出现在内存中。 - unwind
不想拆开规格。 - Aaron Digulla
默认情况下，@unwind不会执行此操作，但旧版本的gcc有选项“-fipa-struct-reorg”来重新排序结构成员。https://dev59.com/wWUq5IYBdhLWcg3wPd-r#28780286 - phuclv
1

这也取决于平台/编译器。正如所指出的那样，大多数编译器将所有内容填充到4字节对齐（或更糟！），因此假设一个包含2个short和1个long的结构体：

short
long
short

将占用12个字节（带有2个2字节的填充）。

重新排序为

short
short
long

由于编译器会填充数据以提高数据访问速度（这是大多数台式机的默认设置，它们更喜欢快速访问而不是内存使用），所以该结构体仍将占用12个字节。你的嵌入式系统有不同的需求，因此你必须使用#pragma pack。

至于重新排序的工具，我会手动重新组织结构体布局，使不同类型的数据相邻。先放所有的shorts，然后放所有的longs等。如果您要进行打包，那么工具也会这样做。在类型之间的过渡点可能会有2字节的填充，但我认为这不值得担心。

想想我刚刚删除了关于不同数据类型大小的答案！无论如何，如果将相同类型的所有字段放在一起，无论每个字段有多大，都会获得最佳的打包效果。 - gbjbaanb
我对“将所有内容对齐到4字节”不太确定；编译器会确保每个成员满足其最小对齐要求。例如，如果long double需要16字节对齐，那么char后面跟着一个long double会留下15字节的空隙；但是short通常需要2字节对齐，char后面跟着一个short会留下1字节的空隙（而char、short组合后跟着long double会留下12字节的空隙，但是跟着32位int会在short和int之间不留空隙）。等等。 - Jonathan Leffler
不，一个 char 后跟 long-double 通常会使用 1 个字节+3 个填充字节+16 个字节。处理器行对齐的工作就像这样，因此可以提取 char 而无需任何位移，但您可以告诉它以不同的方式进行对齐，将其对齐到 0 而不是 4，这样您的应用程序只会执行得更慢。您认为所有内容都需要按最大的个人类型进行对齐。 - gbjbaanb
1
0

请看 #pragma pack。这可以更改编译器对结构中元素的对齐方式。您可以使用它来强制将它们紧密地打包在一起，而无需空格。

在此处查看更多详细信息

2
结构体默认情况下不会进行紧凑排列，因为访问对齐成员更加高效。重新排序结构体可以减小结构体的大小，而不会破坏任何成员的对齐方式。 - Artelius
1
不是他所问的...尽管这将为他提供最佳的打包方案。 - Dan Olson
0
编译器可能不会自行重新排列结构体中的字段。标准规定字段应按定义顺序排列。做其他事情可能会以微妙的方式破坏代码。
当然，您可以编写某种代码生成器以高效地重排字段，但我更喜欢手动完成此操作。
0

思考如何制作这样的工具...我认为我会从调试信息开始。

从源代码中获取每个结构的大小很麻烦。它重叠了编译器已经完成的大量工作。我对 ELF 不够熟悉，无法确定如何从调试二进制文件中提取结构大小信息，但我知道信息存在，因为调试器可以显示它。也许 objdump 或 binutils 包中的其他工具可以轻松地为您获取此信息（至少适用于使用 ELF 的平台）。

在获取信息之后，其余部分就相当简单了。将成员按从大到小的顺序排序，尽可能保持原始结构的排序。使用 Perl 或 Python，甚至可以轻松地与源代码的其余部分进行交叉引用，甚至根据使用情况清晰度来保留注释或 #ifdefs。最大的痛点将是更改整个代码库中结构的所有初始化。天哪。

事实上，听起来很不错，但我不知道是否有任何现有的工具可以做到这一点，而且等你自己写完了...我认为你已经能够手动重新排列程序中的大多数结构了。

0

我曾经遇到过同样的问题。正如另一个答案所建议的那样，pstruct可能会有所帮助。但是，它并没有给出我们需要的完全信息。实际上，pstruct使用了gcc提供的调试信息。我基于同样的想法编写了另一个脚本。

您必须使用STUBS调试信息（-gstubs）生成汇编文件。（虽然可以从dwarf中获取相同的信息，但我使用了与pstruct相同的方法）。一种不修改编译过程的好方法是将"-gstubs -save-temps=obj"添加到编译选项中。

下面的脚本读取汇编文件，并检测结构体中是否添加了额外的字节：

    #!/usr/bin/perl -n

    if (/.stabs[\t ]*"([^:]*):T[()0-9,]*=s([0-9]*)(.*),128,0,0,0/) {
       my $struct_name = $1;
       my $struct_size = $2;
       my $desc = $3;
       # Remove unused information from input
       $desc =~ s/=ar\([0-9,]*\);[0-9]*;[-0-9]*;\([-0-9,]*\)//g;
       $desc =~ s/=[a-zA-Z_0-9]+://g;
       $desc =~ s/=[\*f]?\([0-9,]*\)//g;
       $desc =~ s/:\([0-9,]*\)*//g;
       my @members = split /;/, $desc;
       my ($prev_size, $prev_offset, $prev_name) = (0, 0, "");
       for $i (@members) {
          my ($name, $offset, $size) = split /,/, $i;
          my $correct_offset = $prev_offset + $prev_size;
          if ($correct_offset < $offset) {
             my $diff = ($offset - $correct_offset) / 8;
             print "$struct_name.$name looks misplaced: $prev_offset + $prev_size = $correct_offset < $offset (diff = $diff bytes)\n";
          }
          # Skip static members
          if ($offset != 0 || $size != 0) {
            ($prev_name, $prev_offset, $prev_size) = ($name, $offset, $size);
          }
       }
    }

调用它的好方法：

find . -name *.s | xargs ./detectPaddedStructs.pl | sort | un
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接