using bitfields as a sorting key in modern C (C99/C11 union)

Question

Requirement:

For my tiny graphics engine, I need an array of all objects to draw. For performance reasons this array needs to be sorted on the attributes. In short:

1. Store a lot of attributes per struct, add the struct to an array of structs
2. Efficiently sort the array
3. walk over the array and perform operations (modesetting and drawing) depending on the attributes

Approach: bitfields in a union (i.e.: let the compiler do the masking and shifting for me)

I thought I had an elegant plan to accomplish this, based on this article: http://realtimecollisiondetection.net/blog/?p=86. The idea is as follows: each attribute is a bitfield, which can be read and written to (step 1). After writing, the sorting procedure look at the bitfield struct as an integer, and sorts on it (step 2). Afterwards (step 3), the bitfields are read again.

Sometimes code says more than a 1000 words, a high-level view:

union key {
    /* useful for accessing */
    struct {
        unsigned int some_attr : 2;
        unsigned int another_attr : 3;
        /* ... */
    } bitrep;

    /* useful for sorting */
    uint64_t intrep;
};

I would just make sure that the bit-representation was as large as the integer representation (64 bits in this case). My first approach went like this:

union key {
    /* useful for accessing */
    struct {
        /* generic part: 11 bits */
        unsigned int layer : 2;
        unsigned int viewport : 3;
        unsigned int viewportLayer : 3;
        unsigned int translucency : 2;
        unsigned int type : 1;

        /* depends on type-bit: 64 - 11 bits = 53 bits */
        union {
            struct {
                unsigned int sequence : 8;
                unsigned int id : 32;
                unsigned int padding : 13;
            } cmd;
            struct {
                unsigned int depth : 24;
                unsigned int material : 29;
            } normal;
        };
    };

    /* useful for sorting */
    uint64_t intrep;
};

Note that in this case, there is a decision bitfield called type. Based on that, either the cmd struct or the normal struct gets filled in, just like in the mentioned article. However this failed horribly. With clang 3.3 on OSX 10.9 (x86 macbook pro), the key union is 16 bytes, while it should be 8.

Unable to coerce clang to pack the struct better, I took another approach based on some other stack overflow answers and the preprocessor to avoid me having to repeat myself:

/* 2 + 3 + 3 + 2 + 1 + 5 = 16 bits */
#define GENERIC_FIELDS \
 unsigned int layer : 2; \
 unsigned int viewport : 3; \
 unsigned int viewportLayer : 3; \
 unsigned int translucency : 2; \
 unsigned int type : 1; \
 unsigned int : 5;

/* 8 + 32 + 8 = 48 bits */
#define COMMAND_FIELDS \
 unsigned int sequence : 8; \
 unsigned int id : 32; \
 unsigned int : 8;

/* 24 + 24 = 48 bits */
#define MODEL_FIELDS \
 unsigned int depth : 24; \
 unsigned int material : 24;

struct generic {
    /* 16 bits */
    GENERIC_FIELDS
};

struct command {
    /* 16 bits */
    GENERIC_FIELDS

    /* 48 bits */
    COMMAND_FIELDS
} __attribute__((packed));

struct model {
    /* 16 bits */
    GENERIC_FIELDS

    /* 48 bits */
    MODEL_FIELDS
} __attribute__((packed));

union alkey {
    struct generic gen;
    struct command cmd;
    struct model mod;
    uint64_t intrep;
};

Without including the __attribute__((packed)), the command and model structs are 12 bytes. But with the __attribute__((packed)), they are 8 bytes, exactly what I wanted! So it would seems that I have found my solution. However, my small experience with bitfields has taught me to be leery. Which is why I have a few questions:

My questions are:

• Can I get this to be cleaner (i.e.: more like my first big union-within-struct-within-union) and still keep it 8 bytes for the key, for fast sorting?
• Is there a better way to accomplish this?
• Is this safe? Will this fail on x86/ARM? (really exotic architectures are not much of a concern, I'm targeting the 2 most prevalent ones). What about setting a bitfield and then finding out that an adjacent one has already been written to. Will different compilers vary wildly on this?
• What issues can I expect from different compilers? Currently I'm just aiming for clang 3.3+ and gcc 4.9+ with -std=c11. However it would be quite nice if I could use MSVC as well in the future.

Related question and webpages I've looked up:

• Variable-sized bitfields with aliasing
• Unions within unions
• for those (like me) scratching their heads about what happens with bitfields that are not byte-aligned and endianness, look no further: http://mjfrazer.org/mjfrazer/bitfields/

Sadly no answer got me the entirety of the way there.

EDIT: While experimenting, setting some values and reading the integer representation. I noticed something that I had forgotten about: endianness. This opens up another can of worms. Is it even possible to do what I want using bitfields or will I have to go for bitshifting operations?

Answer 1

The layout for bitfields is highly implementation (=compiler) dependent. In essence, compilers are free to place consecutive bitfields in the same byte/word if it sees fit, or not. Thus without extensions like the packed attribute that you mention, you can never be sure that your bitfields are squeezed into one word.

Then, if the bitfields are not squeezed into one word, or if you have just some spare bits that you don't use, you may be even more in trouble. These so-called padding bits can have arbitrary values, thus your sorting idea could never work in a portable setting.

For all these reasons, bitfields are relatively rarely used in real code. What you can see more often is the use of macros for the bits of your uint64_t that you need. For each of your bitfields that you have now, you'd need two macros, one to extract the bits and one to set them. Such a code then would be portable on all platforms that have a C99/C11 compiler without problems.

Minor point:

In the declaration of a union it is better to but the basic integer field first. The default initializer for a union uses the first field, so this would then ensure that your union would be initialized to all bits zero by such an initializer. The initializer of the struct would only guarantee that the individual fields are set to 0, the padding bits, if any, would be unspecific.