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

About these ads

About brucedawson

I'm a programmer, working for Valve (http://www.valvesoftware.com/), focusing on optimization and reliability. Nothing's more fun than making code run 5x faster. Unless it's eliminating large numbers of bugs. I also unicycle. And play (ice) hockey. And juggle.
This entry was posted in Programming, Visual Studio and tagged , , , . Bookmark the permalink.

9 Responses to Bit-field Packing with Visual C++

  1. Pingback: Visual C++ Code-gen Deficiencies | Random ASCII

  2. Peter Gasper says:

    Not so efficient storage. Thank you for investigating.

  3. Cort says:

    I have some bit-field code where unsigned ints are used to masquerade as enum types, and I hoped the techniques in this article would let me replace the phony enums with real enums. But I’m running into a problem: despite declaring my enum as an unsigned int, it’s still being sign-extended in the bit-field.

    For example:

    enum TestEnum : unsigned int
    {
    kVal0 = 0,
    kVal1 = 1,
    kVal2 = 2,
    kVal3 = 3,
    };

    struct TestStruct
    {
    TestEnum m_field0 : 2;
    TestEnum m_field1 : 2;
    TestEnum m_field2 : 2;
    TestEnum m_field3 : 2;
    };

    TestStruct ts;
    ts.m_field0 = kVal0;
    if (ts.m_field0 != kVal0) printf(“field 0 is invalid!\n”)
    ts.m_field1 = kVal1;
    if (ts.m_field1 != kVal1) printf(“field 1 is invalid!\n”)
    ts.m_field2 = kVal2;
    if (ts.m_field2 != kVal2) printf(“field 2 is invalid!\n”)
    ts.m_field3 = kVal3;
    if (ts.m_field3 != kVal3) printf(“field 3 is invalid!\n”)

    I’m running this code in VS2010, and would expect nothing to be printed, but instead I see that m_field2 and m_field3 are invalid. If I inspect the ts variable in the Watch window, I see that m_field0 = kVal0 and m_field1 = kVal1 (as expected), but m_field2 = 254 and m_field3 = 255 (wrong!). kVal2 and kVal3 are 10 and 11 in binary, and they’re being sign-extended to 11111110 and 11111111, and then interpreted as unsigned integers instead of the default signed ints.

    Do you know if there’s a way to disable the sign extension and treat the raw bitfield values as unsigned integers? I could just add a bit to each enum field, so the high bit would always be zero, but I’d rather not bloat the data if I can avoid it. Am I screwed?

    • brucedawson says:

      That’s odd. I built your program (I had to replace the smart quotes with normal quotes and put semicolons after the printf calls but that’s it) and it didn’t print anything. The debugger watch window showed m_field2 having the value 4294967294 and m_field3 having the value 4294967295, however the comparison was done in an unsigned manner — nothing was printed.

      I then loaded my project into VS 11 Beta. It gave the same output (nothing) but the watch window showed the values 0, 1, 2, and 3.

      I thought C++ 11 had a standard way of indicating enum types (the VC++ technique is a Microsoft extension) but I can’t find it at this moment.

      • Cort says:

        Uh oh — I think you’ve caught me over-simplifying my test case and not running the final copy before posting :(

        The value discrepancy (254/255 vs. 4294967294/4294967295) and the lack of printfs were caused by ill-conceived last-minute changes to the sample code; I added the comparisons/printfs and changed the enum type from unsigned byte to unsigned int right before posting, for “clarity” (d’oh). Initially, I just saw the wrong values in the watch window and foolishly assumed nothing else would work.

        So, at least the watch window problem in VS2010 is legitimate; that’s annoying, but not a dealbreaker for my purposes (as long as the values are correctly interpreted by the code as unsigned).

        Thanks again for the help! And please forgive me for wasting your time; I’ve been awake far too long today.

  4. Pingback: VC++ 2013 class Layout Change and Wasted Space | Random ASCII

  5. A Guy says:

    If you are using bit field structures across multiple threads you have to remember that you have to protect access to the entire _underlying_ bitfield, not just the named portions of it in the structure.

    For a contrived example:

    struct AtomicAccess
    {
    bool flag1 : 1; // Used by thread one exclusively
    bool flag2 : 1; // shared across threads
    bool flag3 : 1; // used by thread two exclusively
    }

    Logically flag 1 and 3 are only operating on by one thread, and flag2 is operated on by both threads. So logically you may be tempted to just protect access to flag2, but flags 1 through 3 are, as is obvious in this context, really one field. Ergo you have to protect access to all three.

    • brucedawson says:

      Yep, bit-fields and multi-threading can be a dangerous mix. Especially since precisely which set of bit-fields share an underlying char/short/int is up to the compiler so there is no portable way to know which members have to share the lock. The only safe thing to do is to acquire the lock for all contiguous bit-fields.

      When I wrote this I was on a project that used bit-fields extensively. Now I’m back to rarely using them.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s