Bit-field Packing with Visual C++

I’ve been spending too much time lately working with bit-fields and learning how they work. The C++ standard gives implementers a lot of latitude in how bit-fields should be laid out, and the VC++ documentation doesn’t go into a lot of details. It turns out that the rules are fairly simple and I thought I’d share my findings here.

But first, a few puzzles. How big will these structures be if compiled by Visual C++ for x86 (32-bit)?

enum EValues
{
val1,
val2,
val3
};

struct ManyTypes
{
int field1 : 4;
unsigned field2 : 4;
long field3 : 4;
unsigned long field4 : 4;
size_t field5 : 4;
ptrdiff_t field6 : 4;
EValues field7 : 4;
DWORD field8 : 4;
};

enum TrueFalse
{
False,
True
};

struct BoolTypes
{
bool flag1 : 1;
BOOL flag2 : 1;
bool flag3 : 1;
TrueFalse flag4 : 1;
};

The ManyTypes structure contains eight different types – well, seven actually once you realize that DWORD is just a typedef for unsigned long. You could easily think that the compiler might refuse to pack all of those bit-fields together compactly – especially the enum. However the 32-bits of bit-field data (eight member variables, four bits each) actually pack perfectly and the size of the structure is four bytes.

The BoolTypes structure contains three different types, all of which are essentially true/false types. You might expect that the 4-bits of bit-field data (four member variables, one bit each) would pack together into a single byte, or perhaps at worst four bytes. However these types pack pathologically badly and the size of the structure is actually sixteen bytes!

So, how come the first structure is 100% efficient, and the second structure is just 3.125% efficient? What are the rules?

The rules used by Visual C++, as far as I can tell from the tests I have run, are that same-sized types can be merged together as long as there’s enough room left. That’s it. When compiling for x86 (32-bits) all seven types used in ManyTypes are 32-bit types so they can all merge together into a single 32-bit block of data. Even the enum is a 32-bit type so it merges in neatly. If we compiled for x64 (64-bits) then size_t and ptrdiff_t would become 64-bit types, so I wouldn’t recommend using them in bit-fields, but when compiling for 32-bits they are fine.

Conversely, if adjacent types being used in bit-fields are of different sizes then they are not merged together, no matter how many bits this wastes. Now sizeof(bool) == 1 for Visual C++, sizeof(BOOL) == 4, and sizeof(enum) == 4, so you can see that we have a problem. The combination of bitfield merging and structure member alignment rules gives most unsatisfactory results. The compiler starts by allocating one byte of space in the structure for a bit-field, and allocates one bit within that for flag1. Then it sees the BOOL bit-field. It closes off the previous bit-field that it started because the sizes don’t match and it allocates four bytes of space in the structure for another bit-field. However the default alignment for 32-bit values, even 32-bit bit-fields, is 32-bit alignment, so it inserts three bytes of padding. Then it sees flag3, a bool bit-field, and it can’t merge it with flag2 because they are different sizes, so it allocates another one-byte bit-field. Finally it sees flag4, which is of type enum, and it can’t merge so it inserts three more bytes of padding and allocates 32-bits for the remaining bit. The structure looks like this:

struct BoolTypes
{
bool flag1 : 1;
// 7 bits unused in the 8-bit bit-field
// 3 bytes of padding so that flag2 is 4-byte aligned
BOOL flag2 : 1;
// 31 bits unused in the 32-bit bit-field
bool flag3 : 1;
// 7 bits unused in the 8-bit bit-field
// 3 bytes of padding so that flag2 is 4-byte aligned
TrueFalse flag4 : 1;
// 31 bits unused in the 32-bit bit-field
};

If the two bool bit-fields were placed adjacent at the beginning or at the end of the structure then the size would drop to eight bytes, which is a huge improvement, but which is still ridiculously huge for a structure that stores just four bits.

The structure above has other problems as well. BOOL on Windows is a typedef for int, which means it is an signed type. Enums are also ints, so also signed. It is a curious property of one-bit signed numbers that the only two values they can store are zero and negative one. Meanwhile ‘true’, ‘True’, and the Windows define ‘TRUE’ are all defined as being one, so any check for flag2==TRUE or flag4 == True will always be false. If you assign TRUE or True to flag2 or flag4 and then retrieve the value it will be changed, from one to negative one. The only reason this isn’t instantly fatal is because “if (flag2)” and “if (flag4)” still works, but the lack of positive one is enough reason to avoid BOOL and TrueFalse enum bit-fields.

When storing a lot of flags it is often most convenient to use bool bit-fields, but that can be a problem when mixing in other data. Using signed char and unsigned char types can help, but then you have to worry about spillover. Look at this structure for an example:

struct SpillOver
{
bool flag1 : 1;
bool flag2 : 1;
bool flag3 : 1;
unsigned char value1 : 6;
unsigned char value2 : 7;
};

This structure declares sixteen bits worth of data, but the size of the structure ends up being three bytes (twenty-four bits). That’s because when the compiler tries to allocate space for value1 it finds that there isn’t room in the existing 8-bit bitfield, so it closes it off and starts a brand new one – wasting the five unused bits. In this particular case the solution is simple – just swap flag3 and value1 and the structure size drops to two bytes. Or, use 16-bit types for all of the bit-field variables so that there is no spillover.

One technique that is occasionally useful when using bit-fields and enums is changing the enum type. Visual C++ lets you define that type with this syntax:

enum FlagTypes : unsigned char
{
False2,
True2
};

This lets you create a better behaved Boolean type, although I’m not sure why you would ever do that. This can be used to make bit-fields that are 8-bits or 16-bits so that they can pack in more easily with similarly sized data.

Bit-fields can be a useful technique to save memory – if you layout your structures carefully. However you can see that if they are used carelessly they can actually increase the size of your structures. Also beware that while bit-fields can make your structures smaller, they actually make your code larger and slower – it takes more instructions to read and write bit-fields than ordinary member variables. So, only use bit-fields for types that you will be allocating a lot of.

The sizes of all of the structures used above were verified using the C++0x static_assert keyword, newly available in Visual C++ 2010. This allows structure sizes to be verified without even running the generated code. These are the statements I used.

static_assert(sizeof(ManyTypes) == 4, “All 32-bit types can be merged”);
static_assert(sizeof(BoolTypes) == 16, “bool and BOOL cannot be merged”);
static_assert(sizeof(SpillOver) == 3, “value1 spills over into the next byte”);

The static_assert evaluates the expression on the left, and if it isn’t true it prints out the message on the right and halts with a fatal error. Very handy.

While static_assert requires Visual C++ 2010, the packing rules apply to all versions of Visual C++. The rules are unlikely to ever be changed because that would cause millions of existing data structures, some of which are used for binary serialization or interop between DLLs, to change and become incompatible.

The official Visual C++ documentation, that covers other aspects of bit-fields, can be found here: http://msdn.microsoft.com/en-us/library/ewwyfdbe.aspx

See also this other blog post: https://randomascii.wordpress.com/2013/12/01/vc-2013-class-layout-change-and-wasted-space/

Also, when investigating structure layout it can be handy to use these undocumented VC++ compiler flags: /d1reportSingleClassLayoutVirtualVecOne and /d1reportAllClassLayout.