When is it worthwhile to use bit fields?

Question

Is it worthwhile using C's bit-field implementation? If so, when is it ever used?

I was looking through some emulator code and it looks like the registers for the chips are not being implemented using bit fields.

Is this something that is avoided for performance reasons (or some other reason)?

Are there still times when bit-fields are used? (ie firmware to put on actual chips, etc)

Solution 1

Bit-fields are typically only used when there's a need to map structure fields to specific bit slices, where some hardware will be interpreting the raw bits. An example might be assembling an IP packet header. I can't see a compelling reason for an emulator to model a register using bit-fields, as it's never going to touch real hardware!

Whilst bit-fields can lead to neat syntax, they're pretty platform-dependent, and therefore non-portable. A more portable, but yet more verbose, approach is to use direct bitwise manipulation, using shifts and bit-masks.

If you use bit-fields for anything other than assembling (or disassembling) structures at some physical interface, performance may suffer. This is because every time you read or write from a bit-field, the compiler will have to generate code to do the masking and shifting, which will burn cycles.

Solution 2

One use for bitfields which hasn't yet been mentioned is that unsigned bitfields provide arithmetic modulo a power-of-two "for free". For example, given:

struct { unsigned x:10; } foo;

arithmetic on foo.x will be performed modulo 2¹⁰ = 1024.

(The same can be achieved directly by using bitwise & operations, of course - but sometimes it might lead to clearer code to have the compiler do it for you).

Solution 3

FWIW, and looking only at the relative performance question - a bodgy benchmark:

#include <time.h>
#include <iostream>

struct A
{
    void a(unsigned n) { a_ = n; }
    void b(unsigned n) { b_ = n; }
    void c(unsigned n) { c_ = n; }
    void d(unsigned n) { d_ = n; }
    unsigned a() { return a_; }
    unsigned b() { return b_; }
    unsigned c() { return c_; }
    unsigned d() { return d_; }
    volatile unsigned a_:1,
                      b_:5,
                      c_:2,
                      d_:8;
};

struct B
{
    void a(unsigned n) { a_ = n; }
    void b(unsigned n) { b_ = n; }
    void c(unsigned n) { c_ = n; }
    void d(unsigned n) { d_ = n; }
    unsigned a() { return a_; }
    unsigned b() { return b_; }
    unsigned c() { return c_; }
    unsigned d() { return d_; }
    volatile unsigned a_, b_, c_, d_;
};

struct C
{
    void a(unsigned n) { x_ &= ~0x01; x_ |= n; }
    void b(unsigned n) { x_ &= ~0x3E; x_ |= n << 1; }
    void c(unsigned n) { x_ &= ~0xC0; x_ |= n << 6; }
    void d(unsigned n) { x_ &= ~0xFF00; x_ |= n << 8; }
    unsigned a() const { return x_ & 0x01; }
    unsigned b() const { return (x_ & 0x3E) >> 1; }
    unsigned c() const { return (x_ & 0xC0) >> 6; }
    unsigned d() const { return (x_ & 0xFF00) >> 8; }
    volatile unsigned x_;
};

struct Timer
{
    Timer() { get(&start_tp); }
    double elapsed() const {
        struct timespec end_tp;
        get(&end_tp);
        return (end_tp.tv_sec - start_tp.tv_sec) +
               (1E-9 * end_tp.tv_nsec - 1E-9 * start_tp.tv_nsec);
    }
  private:
    static void get(struct timespec* p_tp) {
        if (clock_gettime(CLOCK_REALTIME, p_tp) != 0)
        {
            std::cerr << "clock_gettime() error\n";
            exit(EXIT_FAILURE);
        }
    }
    struct timespec start_tp;
};

template <typename T>
unsigned f()
{
    int n = 0;
    Timer timer;
    T t;
    for (int i = 0; i < 10000000; ++i)
    {
        t.a(i & 0x01);
        t.b(i & 0x1F);
        t.c(i & 0x03);
        t.d(i & 0xFF);
        n += t.a() + t.b() + t.c() + t.d();
    }
    std::cout << timer.elapsed() << '\n';
    return n;
}

int main()
{
    std::cout << "bitfields: " << f<A>() << '\n';
    std::cout << "separate ints: " << f<B>() << '\n';
    std::cout << "explicit and/or/shift: " << f<C>() << '\n';
}

Output on my test machine (numbers vary by ~20% run to run):

bitfields: 0.140586
1449991808
separate ints: 0.039374
1449991808
explicit and/or/shift: 0.252723
1449991808

Suggests that with g++ -O3 on a pretty recent Athlon, bitfields are worse than a few times slower than separate ints, and this particular and/or/bitshift implementation's at least twice as bad again ("worse" as other operations like memory read/writes are emphasised by the volatility above, and there's loop overhead etc, so the differences are understated in the results).

If you're dealing in hundreds of megabytes of structs that can be mainly bitfields or mainly distinct ints, the caching issues may become dominant - so benchmark in your system.

update from 2021 with an AMD Ryzen 9 3900X and -O2 -march=native:

bitfields: 0.0224893
1449991808
separate ints: 0.0288447
1449991808
explicit and/or/shift: 0.0190325
1449991808

Here we see everything has changed massively, the main implication being - benchmark with the systems you care about.

---

UPDATE: user2188211 attempted an edit which was rejected but usefully illustrated how bitfields become faster as the amount of data increases: "when iterating over a vector of a few million elements in [a modified version of] the above code, such that the variables do not reside in cache or registers, the bitfield code may be the fastest."

template <typename T>
unsigned f()
{
    int n = 0;
    Timer timer;
    std::vector<T> ts(1024 * 1024 * 16);
    for (size_t i = 0, idx = 0; i < 10000000; ++i)
    {
        T& t = ts[idx];
        t.a(i & 0x01);
        t.b(i & 0x1F);
        t.c(i & 0x03);
        t.d(i & 0xFF);
        n += t.a() + t.b() + t.c() + t.d();
        idx++;
        if (idx >= ts.size()) {
            idx = 0;
        }
    }
    std::cout << timer.elapsed() << '\n';
    return n;
}

Results on from an example run (g++ -03, Core2Duo):

 0.19016
 bitfields: 1449991808
 0.342756
 separate ints: 1449991808
 0.215243
 explicit and/or/shift: 1449991808

---

Of course, timing's all relative and which way you implement these fields may not matter at all in the context of your system.

Solution 4

I've seen/used bit fields in two situations: Computer Games and Hardware Interfaces. The hardware use is pretty straight forward: the hardware expects data in a certain bit format you can either define manually or through pre-defined library structures. It depends on the specific library whether they use bit fields or just bit manipulation.

In the "old days" computers games used bit fields frequently to make the most use of computer/disk memory as possible. For example, for a NPC definition in a RPG you might find (made up example):

struct charinfo_t
{
     unsigned int Strength : 7;  // 0-100
     unsigned int Agility : 7;  
     unsigned int Endurance: 7;  
     unsigned int Speed : 7;  
     unsigned int Charisma : 7;  
     unsigned int HitPoints : 10;    //0-1000
     unsigned int MaxHitPoints : 10;  
     //etc...
};

You don't see it so much in more modern games/software as the space savings has gotten proportionally worse as computers get more memory. Saving a 1MB of memory when your computer only has 16MB is a big deal but not so much when you have 4GB.

Solution 5

The primary purpose of bit-fields is to provide a way to save memory in massively instantiated aggregate data structures by achieving tighter packing of data.

The whole idea is to take advantage of situations where you have several fields in some struct type, which don't need the entire width (and range) of some standard data type. This provides you with the opportunity to pack several of such fields in one allocation unit, thus reducing the overall size of the struct type. And extreme example would be boolean fields, which can be represented by individual bits (with, say, 32 of them being packable into a single unsigned int allocation unit).

Obviously, this only makes sense in situation where the pros of the reduced memory consumption outweigh the cons of slower access to values stored in bit-fields. However, such situations arise quite often, which makes bit-fields an absolutely indispensable language feature. This should answer your question about the modern use of bit-fields: not only they are used, they are essentially mandatory in any practically meaningful code oriented on processing large amounts of homogeneous data (like large graphs, for one example), because their memory-saving benefits greatly outweigh any individual-access performance penalties.

In a way, bit-fields in their purpose are very similar to such things as "small" arithmetic types: signed/unsigned char, short, float. In the actual data-processing code one would not normally use any types smaller than int or double (with few exceptions). Arithmetic types like signed/unsigned char, short, float exist just to serve as "storage" types: as memory-saving compact members of struct types in situations where their range (or precision) is known to be sufficient. Bit-fields is just another step in the same direction, that trades a bit more performance for much greater memory-saving benefits.

So, that gives us a rather clear set of conditions under which it is worthwhile to employ bit-fields:

1. Struct type contains multiple fields that can be packed into a smaller number of bits.
2. The program instantiates a large number of objects of that struct type.

If the conditions are met, you declare all bit-packable fields contiguously (typically at the end of the struct type), assign them their appropriate bit-widths (and, usually, take some steps to ensure that the bit-widths are appropriate). In most cases it makes sense to play around with ordering of these fields to achieve the best packing and/or performance.

---

There's also a weird secondary use of bit-fields: using them for mapping bit groups in various externally-specified representations, like hardware registers, floating-point formats, file formats etc. This has never been intended as a proper use of bit-fields, even though for some unexplained reason this kind of bit-field abuse continues to pop-up in real-life code. Just don't do this.

View more solutions

Comments

[zwol]

Looks like this was done to pack the structure into exactly one 32-bit machine word, probably for atomicity. Boost folken know exactly what they're doing and don't tend to explain themselves in enough detail for people who don't, which unfortunately means copying Boost logic can very easily end in tears -- for instance, there's a reason exclusive and upgrade aren't bool, but do you know what it is?

[Steve Townsend]

The logic uses compare-and-swap to avoid kernel locks unless essential. I am sure that's why it's done this way.

[Matthieu M.]

It's worth noting that it is likely here that sizeof(foo) == sizeof(unsigned), ie you're not saving any memory, you're just having a nicer syntax.

[Matthieu M.]

Note: bitfields on bool and MSVC don't mix, for compatibility with MSVC you need to use some unsigned.

[Matthieu M.]

regarding the "burning cycles" issue, I have found that it was indeed faster to use the smallest integer type possible rather than using bitfields. Except for boolean flags (for which masking is easy and no shifting is required), I therefore agree with you :)

[Oliver Charlesworth]

@Matthieu: I would imagine that in most circumstances, using int would be fastest, because it's the platform's native width. The exception to this would be if doing everything as int makes your data structures significantly bigger, causing cache misses, etc.

[MSalters]

I wouldn't assume that sizeof(foo)==sizeof(unsigned) when sizeof(unsigned)==4

[zwol]

Yet another reason to avoid MSVC then :-(

[supercat]

How should one best write such a library? One approach in C++ would be to define a property which would take an address and bit range and yield a modifiable integer lvalue, and then do something like "#define UART3_BAUD_RATE_MODE MOD_BITFIELD(UART3_CONTROL,12,4)". I would expect one could arrange things so that reads and writes would be inlined (rather than generating function calls) but I don't know how best to arrange for the Boolean-logical-assignment operators (|= etc.) to work efficiently and/or atomically.

[Exectron]

Computers may have more RAM these days, but keeping memory usage lower can help to keep it within the CPU memory cache, which would increase performance. On the other hand, bitfields require more instructions to access them, which decreases performance. Which is more significant?

[ZijingWu]

@caf, You can also do it without bitfields without two much trouble. Just calculate the result and &(2^n - 1)

[ZijingWu]

@OliCharlesworth, the network little-endian or big-endian issue will make your using bit-field pass packet header failed. And the C++ standard also doesn't define the how bit-field stored, it is implement specific. And base on the performance of bit-field is not good, bit-field is useless.

[caf]

@ZijingWu: Yes, that's what I was referring to in the last paragraph.

[pattivacek]

@ZijingWu, "Implementation-specific" (or "platform/compiler-dependent") does not make something useless. It just means that there are limited applications and you have to be careful.

[EvilTeach]

I have used a 3 bit value in a for loop to cycle 0 .. 7 over and over again.

[Exectron]

@Pharap: Yes, comparing the instructions needed to read/write bitfields vs plain int struct members. It is worth considering in code aiming for high execution speed more than memory savings.

[underscore_d]

@ZijingWu While I would not say "useless", bitfields are certainly of very limited use given that - as you say - their implementation-defined packing makes them of little or very non-portable utility for representing specific bitwise formats. So in Oliver's example here, one would have to determine (A) how their implementation packed IP header bits and (B) that this matched the target's way of doing things. It's often much more reliable to code your own bitwise handlers to do this in a totally predictable way - that doesn't at least demand comments saying 'only compile with xcc on yarch'

[underscore_d]

As mentioned elsewhere, this use for hardware interfaces is highly non-portable and depends upon the implementation and architecture of the machine being used. It's often easier to just do this stuff manually.

[M.M]

In my code I use bit-shift macros to pack small fields like that. This avoids the implementation-defined aspects of bit-fields. (Not sure whether OP was asking specifically about using C's bit-field syntax; or about the concept of packing smaller-than-a-byte fields in general)

[AnT stands with Russia]

@Matthieu M.: Hmm.... In my experience MSVC never had any problems with using any integer types with bit-fields.

[Tom]

On many platforms the bit-field structs and the custom mask&shift struct are 4 byte in size whereas the non-bitfield struct is 16 bytes. So performance/size is about equal for the bitfield and separate implementation (it's a tradeoff for you to decide on) whereas the performance/size ratio of the custom mask&shift struct is lower than the others but at least it's platform independent.

[Tim Seguine]

I am somehow surprised that there even WAS a C compiler for the TRS80 in the 70s

[EvilTeach]

Two of them actually, though i mostly did hand coded z80.

[underscore_d]

I don't get this. Why would "you have to mask and unmask things all the time to actually use the values"? Isn't the point that the compiler handles all that for you?

[underscore_d]

That enum could hold <= 256 codes, not less than 255. For C++, nowadays we would just use the ability to specify the underlying type and a sized type from <cstdint>. Also, not only bools and enums: small integral values of known bounds could also benefit from being able to save space. However, the reason not to use bitfields is if the objects simply are not plentiful enough, or the other members are so aligned as to nullify any purpose of bitfields, that the extra verbosity added is not worthwhile; using bitfields usually isn't recommended as a default, & there's good reason for it

[underscore_d]

I think @zwol's point was that the 1-bit wide parts of this are not typed as bools because that could (unless bool is a typedef to unsigned, which is unlikely in any barely modern or space-saving code) result in beginning a new allocation unit due to the type boundary, thus defeating the point of trying to pack those bits together with other values.

[zwol]

@underscore_d Yes, that's what I had in mind for the "reason exclusive and upgrade aren't bool". (Gosh, I'd forgotten I wrote that comment.)

[zwol]

@underscore_d I wish C would adopt that underlying-type-of-a-bitfield feature. It is valuable in several other contexts, such as controlling your library ABI, for which plain C is still commonly used.

[einpoklum]

Shouldn't you be compiling with -march=native?

[Oskar Holmkratz]

Modern computer-games also use bitfields if they want to maximize performance for some types of operations. Mostly filters. That would be f.ex., if A can interact with B,C and E, but not D, F and G -- then all of those checks can be performed with one bit-wise operation. When A needs to be checked for interactions with E, their interaction bitfields are compared using an & operation. If there is a result, an interaction has occured. This also has the good side-effect that asymmetric interactions can be done.

[Gabriel Staples]

You're talking about "burning cycles" during compile-time here, NOT run-time, right? This is because every time you read or write from a bit-field, the compiler will have to generate code to do the masking and shifting, which will burn cycles.

[Gabriel Staples]

where each byte represents a bit--that would create a huge waste in RAM, no?--using 8 bits to represent each 1 bit you actually need.

[WaltK]

No, you don't use instances of the structure to store the data, just to define the layout and size of the bit fields. The example Bf_format structure above defines 3 bit fields that fit in 4 8-bit bytes.