问题 C结构中的自动字段重新排序以避免填充


我花了几分钟手动重新排序结构中的字段,以减少填充效果[1],这感觉就像几分钟太多。我的直觉是说我的时间可能更好地花在编写Perl脚本上,或者为我做这种优化。

我的问题是这是否也是多余的;是否已经有一些我不知道的工具,或者我应该能够启用[2]打包结构的一些编译器功能?

由于需要在几种不同的体系结构中一致地优化这一事实,因此问题更加复杂,因此无论使用何种工具都需要能够考虑不同的结构对齐和指针大小。

编辑:快速澄清 - 我想要做的是重新排序源代码中的字段,以避免填充,而不是“填充”结构编译没有填充。

编辑#2:另一个复杂因素:根据配置,某些数据类型的大小也可能会发生变化。显而易见的是针对不同体系结构的指针和指针差异,但也有浮点类型(16,32或64位,取决于'精确性'),校验和(8位或16位取决于“速度”)和一些其他非显而易见的东西。

[1]有问题的结构在嵌入式设备上被实例化了数千次,因此结构的每个4字节减少可能意味着  和 无用的 这个项目。

[2]可用的编译器是GCC 3. *和4. *,Visual Studio,TCC,ARM ADS 1.2,RVCT 3. *以及其他一些更加模糊的编译器。


9540
2018-05-15 07:57


起源

这个结构的实例是否需要跨设备移植,或者每个架构都有自己的包装可以吗? - Alnitak
暂且不说:我认为这是一个有趣的问题,并用谷歌搜索“perl struct reordering”。这是最好的结果。问题只有15分钟! - Paul Dixon
Alnitak - 是的,这实际上是需要非常便携的代码:)每个架构都可以有自己的结构定义 - 但是手工编写特定于架构的定义是不切实际的。 - Christoffer


答案:


如果您可以挤出存储的每个单词都很重要,那么我必须建议手动优化结构。一个工具可以为你最佳地安排成员,但是它不知道,例如,这里你以16位存储的值实际上永远不会超过1024,所以你可以窃取高6位 这个 价值超过 这里...

因此,人类几乎肯定会在这份工作中击败机器人。

[编辑]但似乎你真的不想为每个架构手动优化你的结构。也许你真的有很多架构需要支持?

我认为这个问题不适用于一般解决方案,但您可能能够将您的领域知识编码为自定义Perl / Python / something脚本,为每个体系结构生成结构定义。

此外,如果所有成员的大小都是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
};

6
2018-05-15 08:16



直到有人建立一个更智能的机器人(为这个工作)! - Sandeep Datta
同意;这里涉及很多依赖于上下文的知识。当然,如果你有非常多的结构,并且你可以用工具可以使用的格式嵌入所有这些知识,那么就可以自动化它。 - Steve Melnikoff
感谢您的回答。我对最佳排序有疑问。在你的回答中,你曾提到最佳排序是从最大到最小。关于那个陈述有没有证据?我已经尝试了很多案例,并且所有这些都无法破坏声明,所以我想知道如何证明这一点。非常感谢你。 - yoco
从最大到最小的排序通常不是最佳的。一般情况是垃圾箱包装问题,这是NP难的 - 有一些有趣的结果,如果你好奇,你可以谷歌。仅在特殊情况下,尺寸为2的幂才能完美包装,不留间隙;通过观察这种情况很容易理解为什么。每个大小为2 ^ k的对象在2 ^ k对齐的边界上结束,该边界也是2 ^ k-1对齐的边界,因此“降低”到较小的大小永远不会导致间隙。 - Charlie


有一个名为pstruct的Perl脚本通常包含在Perl安装中。该脚本将转储结构成员偏移量和大小。您可以修改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
}

6
2018-05-15 08:26



好主意,但似乎pstruct与C ++有问题:-( - Jezz


大多数C编译器都不会这样做,因为你可以做一些奇怪的事情(比如在结构中获取一个元素的地址,然后使用指针魔法来访问其余部分,绕过编译器)。一个着名的例子是AmigaOS中的双链表,它使用守护节点作为列表的头尾(这使得在遍历列表时可以避免ifs)。守护者头部节点总是有 pred == null 并且尾节点会有 next == null,开发人员将两个节点分成一个三指针结构 head_next null tail_pred。通过使用的地址 head_next 或者 null 作为头节点和尾节点的地址,它们节省了四个字节和一个内存分配(因为它们只需要整个结构一次)。

因此,最好的办法是将结构编写为伪代码,然后编写一个预处理器脚本,从中创建真实的结构。


2
2018-05-15 08:19



没有C编译器会这样做,因为这会破坏规范,这要求结构的字段按照它们在结构中声明的顺序出现在内存中。 - unwind
不想破坏规格。 - Aaron Digulla
@unwind默认情况下没有完成,但旧版本的gcc有选项 -fipa-struct-reorg 重新排序struct成员 stackoverflow.com/a/28780286/995714 - phuclv


看看#pragma pack。这会更改编译器如何对齐结构中的元素。您可以使用它来强制它们紧密包装在一起,没有空格。

在这里查看更多细节


0
2018-05-15 08:06



默认情况下不会打包结构,因为访问对齐的成员会更有效。重新排序结构可以减小结构的大小,而不会实际破坏任何成员的对齐。 - Artelius
不是他要问的......虽然它会给他最好的包装。 - Dan Olson


它也取决于平台/编译器。如上所述,大多数编译器将所有内容填充到4字节对齐(或更糟!),因此假设一个结构有2个短路和一个长:

short
long
short

将占用12个字节(带有2 * 2个字节的填充)。

重新安排它

short
short
long

仍然会占用12个字节,因为编译器将填充它以使数据访问更快(这是大多数桌面的默认设置,因为他们更喜欢快速访问内存使用)。您的嵌入式系统有不同的需求,因此无论如何都必须使用#pragma pack。

至于重新排序的工具,我只需(手动)重新组织您的结构布局,以便将不同的类型放在一起。首先把所有的短裤放进去,然后把所有的短裤放进去等等。如果你要完成包装,这就是工具无论如何都会做的。在类型之间的转换点,中间可能有2个字节的填充,但我不认为这值得担心。


0
2018-05-15 08:30



很好的建议,但看到最新的编辑... - Christoffer
并认为我删除了有关不同数据类型大小的答案!无论如何,如果将所有相同类型的字段放在一起,无论每个字段有多大,您都将获得最佳包装。 - gbjbaanb
我不确定“4字节对齐的一切”;编译器将确保每个成员满足其最小对齐要求。例如,如果long double需要16字节对齐,则后跟long double的char将留下15个字节的空洞;但是短路通常需要2字节对齐,而后跟短路的字符串留下1个字节的漏洞(整体 - 字符,短 - 后跟长双字节会留下12个字节的漏洞,但后面跟着32位整数在short和int之间不会留下任何漏洞。等等。 - Jonathan Leffler
不,一个字符后跟一个long-double通常会使用1byte + 3padbytes + 16bytes。处理器行对齐的工作方式类似,因此可以在不进行任何位移的情况下提取字符,但您可以告诉它以不同的方式执行,对齐为0而不是4,并且您的应用程序只会执行得更慢。你认为一切都需要通过最大的个人类型来协调。 - gbjbaanb


编译器可能不会通过自己的头重新排序结构中的字段。标准要求字段应按其定义的顺序排列。做其他事可能会以微妙的方式破坏代码。

在编写时,当然完全有可能制作某种代码生成器,以有效的方式在字段周围进行混乱。但我更喜欢手动执行此操作。


0
2018-05-15 10:15





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

从源头获取每个结构的大小是一件痛苦的事。它重叠了编译器已经完成的许多工作。我对ELF不太熟悉,无法准确地说明如何从调试二进制文件中提取结构大小信息,但我知道信息存在是因为调试器可以显示它。或许obudump或binutils包中的其他内容可以为您轻松获取(至少对于使用ELF的平台)。

获得信息后,剩下的就很简单了。将成员从大到小排序,尽可能保持原始结构的排序。使用perl或python,甚至可以很容易地将其与其他源交叉引用,甚至可以保留注释或#ifdef,具体取决于它们的使用方式。最大的痛苦是在整个代码库中更改结构的所有初始化。让人惊讶。

这就是事情。这听起来真的很好,但我不知道有什么 现有 这样做的工具,当你自己编写时......我认为你已经能够手动重新排序程序中的大多数结构。


0
2018-05-15 10:40





我有同样的问题。正如另一个答案中所建议的那样,pstruct可能有所帮但是,它确实提供了我们所需要的。实际上pstruct使用gcc提供的调试信息。我根据同样的想法写了另一个脚本。

您必须使用STUBS调试信息生成程序集文件(-gstubs)。 (有可能从矮人那里获得相同的信息,但我使用的方法与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

0
2017-08-21 14:21