Mai*_*tor 38 c struct bit-fields
我经常发现自己必须代表一个由非常小的值组成的结构.例如,Foo有4个值a, b, c, d,范围从0 to 3.通常我不在乎,但有时,这些结构是
用于紧密循环;
他们的价值读数十亿次/秒,这是该计划的瓶颈;
整个计划由数十亿美元组成Foo;
在这种情况下,我发现自己无法决定如何Foo有效地表达.我基本上有4种选择:
struct Foo {
int a;
int b;
int c;
int d;
};
struct Foo {
char a;
char b;
char c;
char d;
};
struct Foo {
char abcd;
};
struct FourFoos {
int abcd_abcd_abcd_abcd;
};
它们分别使用128,32,8,8位Foo,从稀疏到密集.第一个例子可能是最语言的例子,但使用它实际上会增加16倍于程序的大小,这听起来不太合适.而且,大部分内存都会被零填充而根本不被使用,这让我想知道这不是浪费.另一方面,密集地打包它们会带来额外的开销来阅读它们.
在结构中表示小值的计算"最快"方法是什么？
dbu*_*ush 34
对于不会产生大量读取开销的密集打包,我建议使用带位域的结构.在您的示例中,您有四个值,范围从0到3,您可以按如下方式定义结构:
struct Foo {
unsigned char a:2;
unsigned char b:2;
unsigned char c:2;
unsigned char d:2;
}
这具有1个字节的大小,并且字段可以简单地访问,即foo.a,foo.b等
通过使您的结构更密集,这应该有助于缓存效率.
编辑:
总结评论:
使用位域仍然有点小问题,但它是由编译器完成的,并且很可能比你手工编写的更有效(更不用说它使你的源代码更简洁,更不容易引入错误).并且考虑到你将要处理的大量结构,使用诸如此类的压缩结构所获得的缓存未命中的减少可能会弥补结构所施加的位操作的开销.
sta*_*ark 20
仅在考虑空间时才打包它们 - 例如,1,000,000个结构的数组.否则,进行移位和屏蔽所需的代码大于数据空间的节省.因此,您在I-cache上比D-cache更容易出现缓存未命中.
Pet*_*ter 11
没有明确的答案,而且您没有提供足够的信息来做出"正确"的选择.有权衡.
您的"主要目标是时间效率"的陈述是不够的,因为您尚未指定I/O时间(例如,从文件读取数据)是否比计算效率更重要(例如,某些计算集需要多长时间)用户点击"开始"按钮后.
因此,将数据写为单个字符(以减少读取或写入的时间),但将其解压缩为四个数组int(因此后续计算更快)可能是合适的.
此外,无法保证a int是32位(在您的语句中假设第一个打包使用128位).一个int可以是16位.
Foo有4个值,a,b,c,d,范围从0到3.通常我不关心,但有时,这些结构是......
还有另一种选择:因为值0 ... 3可能表示某种状态,你可以考虑使用"flags"
enum{
A_1 = 1<<0,
A_2 = 1<<1,
A_3 = A_1|A_2,
B_1 = 1<<2,
B_2 = 1<<3,
B_3 = B_1|B_2,
C_1 = 1<<4,
C_2 = 1<<5,
C_3 = C_1|C_2,
D_1 = 1<<6,
D_2 = 1<<7,
D_3 = D_1|D_2,
//you could continue to ... D7_3 for 32/64 bits if it makes sense
}
这与在大多数情况下使用位域没有太大区别,但可以大大减少条件逻辑.
if ( a < 2 && b < 2 && c < 2 && d < 2) // .... (4 comparisons)
//vs.
if ( abcd & (A_2|B_2|C_2|D_2) !=0 ) //(bitop with constant and a 0-compare)
根据您将对数据执行的操作类型,使用4或8组abcd并根据需要使用0填充结束可能是有意义的.这可以允许最多32个比较用bitop和0-compare代替.例如,如果你想在64位变量中的所有8组4上设置"1位",uint64_t abcd8 = 0x5555555555555555ULL;那么你可以设置所有2位,你abcd8 |= 0xAAAAAAAAAAAAAAAAULL;现在可以将所有值设置为3
附录:进一步考虑,你可以使用union作为你的类型,并使用char和@ dbush的位域进行联合(这些标志操作仍然可以在unsigned char上使用)或者为每个a,b,c,d使用char类型并使用unsigned int将它们联合起来.这将允许紧凑的表示和有效的操作,具体取决于您使用的联合成员.
union Foo {
char abcd; //Note: you can use flags and bitops on this too
struct {
unsigned char a:2;
unsigned char b:2;
unsigned char c:2;
unsigned char d:2;
};
};
甚至进一步扩展
union Foo {
uint64_t abcd8; //Note: you can use flags and bitops on these too
uint32_t abcd4[2];
uint16_t abcd2[4];
uint8_t abcd[8];
struct {
unsigned char a:2;
unsigned char b:2;
unsigned char c:2;
unsigned char d:2;
} _[8];
};
union Foo myfoo = {0xFFFFFFFFFFFFFFFFULL};
//assert(myfoo._[0].a == 3 && myfoo.abcd[0] == 0xFF);
此方法确实引入了一些字节序差异,如果您使用union来覆盖其他方法的任何其他组合,这也会成为一个问题.
union Foo {
uint32_t abcd;
uint32_t dcba; //only here for endian purposes
struct { //anonymous struct
char a;
char b;
char c;
char d;
};
};
您可以使用不同的联合类型和算法进行实验和测量,以查看哪些部分值得保留,然后丢弃那些无用的联合.您可能会发现同时对多个char/short/int类型进行操作会自动优化为AVX/simd指令的某些组合,而使用位域除非您手动展开它们...在测试和测量它们之前无法知道.
在缓存中安装数据集至关重要.较小的总是更好,因为超线程竞争性地共享硬件线程(在Intel CPU上)之间的每核心缓存.对此答案的评论包括一些缓存未命中成本的数字.
在x86上,将带有符号或零扩展的8位值加载到32或64位寄存器(movzx或movsx)中的字面速度与mov字节或32位双字的速度一样快.存储32位寄存器的低字节也没有开销.(请参阅Agner Fog的说明表和C/asm优化指南).
仍然x86特定:[u]int8_t临时也很好,但避免[u]int16_t临时.([u]int16_t在内存中加载/存储是很好的,但是在寄存器中使用16位值会对英特尔CPU上的操作数大小前缀解码造成严重影响.)如果要将它们用作数组索引,32位临时值会更快.(使用8位寄存器不会将高24/56位归零,因此需要额外的指令来进行归零或符号扩展,使用8位寄存器作为数组索引,或者使用更宽类型的表达式(如将其添加到一个int.)
我不确定ARM或其他架构可以做什么,从单字节加载或单字节存储有效的零/符号扩展.
鉴于此,我的建议包括存储,int临时使用.(或者long,这会在x86-64上略微增加代码大小,因为需要REX前缀来指定64位操作数大小.)例如,
int a_i = foo[i].a;
int b_i = foo[i].b;
...;
foo[i].a = a_i + b_i;
打包到位域将有更多的开销,但仍然值得.在字节或32/64位内存块中测试编译时常量位(或多位)的速度很快.如果你真的需要将一些位域解压缩为ints并将它们传递给非内联函数调用或其他东西,那么将需要一些额外的指令来移位和屏蔽.如果这样可以减少缓存未命中数,那么这是值得的.
测试,设置(到1)或清除(到0)一位或一组位可以用OR或有效地完成AND,但是将未知的布尔值分配给位域需要更多的指令来将新位与其他字段的位合并.如果您经常将变量分配给位域,这可能会使代码显着膨胀.因此int foo:6,在结构中使用类似的东西,因为你知道foo不需要前两位,所以不太可能有用.如果你没有保存很多位而不是将每个东西放在它自己的byte/short/int中,那么缓存未命中的减少将不会超过额外的指令(这可能会导致I-cache/uop-cache未命中,以及直接的额外延迟和指令的工作.)
x86 BMI1/BMI2(位操作)指令集扩展将使寄存器中的数据复制到某些目标位(而不会破坏周围的位)更有效.BMI1:Haswell,Piledriver.BMI2:Haswell,挖掘机(未发布).请注意,与SSE/AVX一样,这意味着您需要功能的BMI版本,以及不支持这些指令的CPU的后备非BMI版本.AFAIK,编译器没有选项来查看这些指令的模式并自动使用它们.它们只能通过内在函数(或asm)使用.
Dbush的回答,打包到位域可能是一个不错的选择,这取决于你如何使用你的领域.您的第四个选项(将四个单独的abcd值打包到一个结构中)可能是一个错误,除非您可以使用四个连续abcd值(矢量样式)执行一些有用的操作.
对于您的代码广泛使用的数据结构,设置是有意义的,这样您就可以从一个实现转换到另一个实现,并进行基准测试. 尼尔弗里德曼的回答,有吸气剂/安装者是一个很好的方法.但是,仅使用int临时工作并使用字段作为结构的单独成员应该可以正常工作.对于打包的位域,由编译器生成代码来测试字节的正确位.
如果你有任何代码只检查每个结构的一个或几个字段,尤其是 循环遍历顺序结构值,然后由cmaster给出的数组结构答案将是有用的.x86向量指令具有单个字节作为最小粒度,因此具有单独字节中的每个值的数组结构将允许您快速扫描第一个元素where a == something,using PCMPEQB / PTEST.
首先,通过"最有效"来精确定义您的意思.最佳内存利用率？最棒的表演？
然后以两种方式实现您的算法,并在实际的硬件上实际对其进行概要分析,以便在您交付时打算在其下运行它的实际条件下运行它.
选择一个更符合您"最有效"原始定义的那个.
其他任何东西都只是猜测.无论你选择什么都可以正常工作,但如果没有在你使用软件的确切条件下实际测量差异,你永远不会知道哪种实现会"更有效".
我认为唯一真正的答案可能是通常编写代码,然后使用所有这些编写完整的程序.我认为这不会花费那么多时间,尽管看起来有点尴尬.基本上,我会做这样的事情:
template <bool is_packed> class Foo;
using interface_int = char;
template <>
class Foo<true> {
char m_a, m_b, m_c, m_d;
public:
void setA(interface_int a) { m_a = a; }
interface_int getA() { return m_a; }
...
}
template <>
class Foo<false> {
char m_data;
public:
void setA(interface_int a) { // bit magic changes m_data; }
interface_int getA() { // bit magic gets a from m_data; }
}
如果您只是编写这样的代码而不是暴露原始数据,那么切换实现和配置文件将很容易.函数调用将内联,不会影响性能.请注意,我刚写了setA和getA而不是返回引用的函数,这实现起来比较复杂.