next »

[Will Vale]

Or just packing things into memory efficiently:

Code:

enum EntityFlag
{
    ALIVE   = (1<<0),
    FROZEN  = (1<<1),
    NEWBORN = (1<<2),
    HIDDEN  = (1<<3),

    // space for more!
};

bool Entity::IsSet(EntityFlag flag)    { return (m_flags & flag) != 0; }

32 boolean flags in the space of one bool, plus you can manipulate them neatly:

Code:

uint32 changed_flags = new_flags ^ old_flags;
if ( changed_flags )
{
   // At least one flag has changed. Imagine what that'd look like testing 32 boolean flags!
}

Not bad

Bitfields are good when you want different numbers of bits per item, such as (as you suggest) compressing state in network packets. You can write the code for the packing and unpacking (shifts and masks) yourself, but the compiler will do it for you if you use bitfields.

Will

[Average Software]

I may be wrong, but it looks like you might be confusing the concept that people call "bitfields" (packing information using bitops) with the actual language feature called "bitfields."  I was talking about the language feature, which I've never seen used outside of very low-level code like the Linux kernel.

The code I posted is the language feature, which allows you to specify bit widths for members of a struct, usually so you can map it directly to hardware bits.  You can also do empty padding bits, I think it looks like this:

Code:

struct SomeBitfield
{
    unsigned first_bit : 1;
    unsigned second_bit : 1;
    unsigned : 4;  // 4 bits of padding.
    unsigned third_bit : 1
};

This is the sort of thing I was referring to, not the general practice of packing flags into a single variable.  Stroustrup barely mentions these in his book, and in the K&R C book they get less than a page of treatment.  It's one of the few language features I've never had a use for.

Now I believe you could rewrite your EntityFlag like so:

Code:

struct EntityFlags
{
    bool alive : 1;
    bool frozen : 1;
    bool newborn : 1;
    bool hidden : 1;
};

void do_something(EntityFlags flags)
{
    if (flags.newborn)
    {
        //stuff
    }
}

This saves you the time of writing the bitops, the compiler will do it all for you.  I'm not sure how wise this is though, the little that I've seen about bitfields seems to imply that there is a lot of implementation dependent magic involved, so I'm not sure what utility they would have outside of the most low-level of code.

[ham and brie]

They're used quite often where I work (mainstream console game team). Packing data not just to reduce total memory use, but more to make better use of cache (cache misses are expensive in terms of cycles). Also network packets.

I don't think this is rare practice in game development. As an example in open source code, you can see it used in some structs (rcSpan, rcCompactCell, rcCompactSpan) here in recast, a nav mesh library.

[Will Vale]

I may be wrong, but it looks like you might be confusing the concept that people call "bitfields" (packing information using bitops) with the actual language feature called "bitfields."

That wasn't what I was intending to say (I do understand the difference) but I agree the way I laid out the post was confusing. I was intending to reply to the claim by peous and rivon that "if you use C++ you don't get involved with bits" with an example of why that might be useful.

The note about bitfields (final para) was an addition specifically about the language feature. You're right that you could implement the flags with bitfields, personally I wouldn't because it can be useful to do things with multiple flags like:

Code:

void Entity::SetAll(uing32 flags) { m_flags |= flags; }
bool Entity::AreAnySet(uint32 flags) { return (m_flags & flags) != 0; }
bool Entity::AreAllSet(uint32 flags) { return (m_flags & flags) == flags; }

I tend to keep bitfields for situations when the field widths differ.

Will

[peous]

As an example in open source code, you can see it used in some structs (rcSpan, rcCompactCell, rcCompactSpan) here in recast, a nav mesh library.

Yes, it can be useful, but when optimizing your module on a final phase, and this involves adding a lot of tests to check value ranges. At least, Recast defines some constants related the the fact they store their values on 13 bits. This is a good thing, and for sure useful for the programmer who uses this structure.

Code:

static const int RC_SPAN_HEIGHT_BITS = 13;
static const int RC_SPAN_MAX_HEIGHT = (1<<RC_SPAN_HEIGHT_BITS)-1;
struct rcSpan { unsigned int smin : 13; unsigned int smax : 13; unsigned int area : 6; }

Note, about gaining memory, that after optimizing some bits on their struct, the line below defines arbitrary blocks of 2048 elements of this structure

And you have to know that using "rcSpan.smax" anywhere will involve a bit shift and a "and' mask. Optimization has a cost...

[Will Vale]

And you have to know that using "rcSpan.smax" anywhere will involve a bit shift and a "and' mask. Optimization has a cost...

Absolutely, but if it means spending a couple of cycles to shift and mask and avoiding hundreds of cycles of cache miss that can be a big win. Totally depends on the circumstances, but as a rule of thumb smaller is better. But then faster is also better

Will

[peous]

Smaller is better. But then faster is also better

and also stronger

Prodigy.

[Will Vale]

Note, about gaining memory, that after optimizing some bits on their struct, the line below defines arbitrary blocks of 2048 elements of this structure

Aah, I missed that comment earlier. I think a bit of explanation might be required as to why this is actually a good thing:

The big (but not huge - only 16KB) blocks of 2048 rcSpans help because they ensure related spans are allocated close together in memory and tightly packed with no heap block overhead. This actually *saves* space.

The small rcSpan size (8 bytes) helps because it divides evenly into a cache line, and a single load (assuming 64 byte cache lines) will fetch 8 spans for the price of one. Loading a cache line is expensive, this helps make accessing spans cheaper. In combination with the big blocks, there's a good chance that loading one span will have some other related spans in the cache ready for you to work on straight away.

Both sizes are the way they are because Recast assumes you'll be working with a decent amount of data at a time. It uses that assumption to lay the data out in a way that will save space and make it fast to load.

That's the only way to go IMO - there's little point optimising for a trivial amount of data because that's going to be fast anyway.

You might want to read Tony Albrecht's slides for a bit more background on this.

Cheers,

Will

[peous]

Nice doc, thanks. Doesn't surprise me that it's from PS3 team ^^, as cache misses are really expensive on PS3 (compared to processor power).
But of course everything is applicable on all platforms.

However, I usually don't design my code architecture with this in mind. I better design something, and then profile it and refactor things to have it cache/branch friendly, when it's needed. Because optimizations usually make code... less readable. So I usually keep optimization for the end.

This way of doing is not applicable to SPU, though. With this little Sony wonder, you have to know the processor, then begin thinking ^^

Edit: Just watched your website Will, I understand better you way of thinking ! Seems to be a quite nice job, optimization master ^^