c - What is the most efficient way to represent small values in a struct?

Question

Often I find myself having to represent a structure that consists of very small values. For example, Foo has 4 values, a, b, c, d that, range from 0 to 3. Usually I don't care, but sometimes, those structures are

1. used in a tight loop;

2. their values are read a billion times/s, and that is the bottleneck of the program;

3. the whole program consists of a big array of billions of Foos;

In that case, I find myself having trouble deciding how to represent Foo efficiently. I have basically 4 options:

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;
};

They use 128, 32, 8, 8 bits respectively per Foo, ranging from sparse to densely packed. The first example is probably the most linguistic one, but using it would essentially increase by 16 times the size of the program, which doesn't sound quite right. Moreover, most of the memory will be filled with zeroes and not be used at all, which makes me wonder if this isn't a waste. On the other hands, packing them densely brings an additional overhead for of reading them.

What is the computationally 'fastest' method for representing small values in a struct?

question from:https://stackoverflow.com/questions/31731684/what-is-the-most-efficient-way-to-represent-small-values-in-a-struct

Answer 1

For dense packing that doesn't incur a large overhead of reading, I'd recommend a struct with bitfields. In your example where you have four values ranging from 0 to 3, you'd define the struct as follows:

struct Foo {
    unsigned char a:2;
    unsigned char b:2;
    unsigned char c:2;
    unsigned char d:2;
}

This has a size of 1 byte, and the fields can be accessed simply, i.e. foo.a, foo.b, etc.

By making your struct more densely packed, that should help with cache efficiency.

Edit:

To summarize the comments:

There's still bit fiddling happening with a bitfield, however it's done by the compiler and will most likely be more efficient than what you would write by hand (not to mention it makes your source code more concise and less prone to introducing bugs). And given the large amount of structs you'll be dealing with, the reduction of cache misses gained by using a packed struct such as this will likely make up for the overhead of bit manipulation the struct imposes.