The cost-benefit analysis of bitfields for a collection of booleans
Consider a class witha bunch of BOOL
members:
// no nitpicking over BOOL vs bool allowed class Pear { … BOOL m_peeled; BOOL m_sliced; BOOL m_pitted; BOOL m_rotten; … };
You might be tempted to convert the BOOL
fieldsinto bitfields:
class Pear { … BOOL m_peeled:1; BOOL m_sliced:1; BOOL m_pitted:1; BOOL m_rotten:1; … };
Since a BOOL
is typedef’d as INT (which onWindows platforms is a signed 32-bit integer),this takes sixteen bytes and packs them into one.That’s a 93% savings!Who could complain about that?
How much did that savings cost you, and how much did you save anyway?
Let’s look at the cost of that savings.Code that updated the plain BOOL
m_sliced
member could do it by simply storing the resultinto the member.Since it was a normal field,this could be accomplished directly:
mov [ebx+01Ch], eax ; m_sliced = sliced
On the other hand, when it’s a bitfield, updating it becomes trickier:
add eax, eax ; shift “sliced” into the correct position xor eax, [ebx+01Ch] ; merge “sliced” with other bits and eax, 2 xor [ebx+01Ch], eax ; store the new bitfield
Exercise: Figure out how the above trick works.
Converting a BOOL
to a single-bit field saved three bytesof data but cost you eight bytes of code when the member is assigneda non-constant value.Similarly, extracting the value gets more expensive.What used to be
push [ebx+01Ch] ; m_sliced call _Something@4 ; Something(m_sliced);
becomes
mov ecx, [ebx+01Ch] ; load bitfield value shl ecx, 30 ; put bit at top sar ecx, 31 ; move down and sign extend push ecx call _Something@4 ; Something(m_sliced);
The bitfield version is bigger by nine bytes.
Let’s sit down and do some arithmetic.Suppose each of these bitfielded fields is accessed six timesin your code, three times for writing and three times for reading.The cost in code growth is approximately 100 bytes.It won’t be exactly 102 bytes because the optimizer may be ableto take advantage of values already in registers for some operations,and the additional instructions may have hidden costs in terms ofreduced register flexibility.The actual difference may be more, it may be less, but for aback-of-the-envelope calculation let’s call it 100.Meanwhile,the memory savings was 15 byte per class.Therefore, the breakeven point is seven.If your program creates fewer than seven instances of this class,then the code cost exceeds the data savings: Your memory optimizationwas a memory de-optimization.
Even if you manage to come out ahead in the accounting ledger,it may be a win of just a few hundred bytes.That’s an awful lot of extra hassle to save a few hundred bytes.All somebody has to do is add an icon to a dialog box and yoursavings will vanish.
When I see people making these sorts ofmicro-optimizations,sometimes I’ll ask them,“How many instances of this class does the program create?”and sometimes the response will be,“Oh, maybe a half dozen. Why do you ask?”
But wait, there’s more.Packing all these members into a bitfield has other costs.You lose the ability to set a hardware write breakpoint on a specific bit,since hardware breakpoints are done at the byte level (at a minimum).You also lose atomicity:An update to m_sliced
will interfere with a simultaneousupdate to m_peeled
on another thread,since the update process merges the two values and stores the resultnon-atomically.(Note that you also lose atomicity if you had used a byte-sizedbool
instead of a 32-bit BOOL
because some CPUarchitectures such as the original Alpha AXP cannot access memoryin units smaller than a DWORD
.)
These are just a few things to take into account when consideringwhether you should change your fields to bitfields.Sure, bitfields save data memory, but you have to balance itagainst the cost in code size, debuggability, and reduced multithreading.If your class is going to be instantiated only a few times(and by “a few” I’m thinking less than a few thousand times),then these costs most likely exceed the savings.
0 comments