CODEWITHSUNDEEP
c++optimizationconditional-statements
Jeremy Friesner
Jeremy Friesner

Reputation: 73041

Is there a way to avoid branching/conditional-logic in this function?

I have this simple function in my program:

enum {
   TABLE_INDEX_TYPE_UINT8 = 0,
   TABLE_INDEX_TYPE_UINT16,
   TABLE_INDEX_TYPE_UINT32,
};

// inline method
uint8_t MyTable :: GetTableIndexTypeForTableSize(uint32_t tableSize) const
{
   // Deliberately testing for strictly-less-than-255/65535 here, 
   // because 255 and 65535 are used as special sentinel values
   return (tableSize < 255) ? TABLE_INDEX_TYPE_UINT8 
        : ((tableSize < 65535) ? TABLE_INDEX_TYPE_UINT16 : TABLE_INDEX_TYPE_UINT32);
}

In the current version of my program, I call this method whenever tableSize changes, and store the result in a member-variable for quick re-use, and that works fine.

However, today I am experimenting with reducing sizeof(MyTable), and one way to do that is to get rid of unnecessary member-variables. Since the cached result of the above function is always re-computable (based on the current value of the tableSize member-variable), I modified the code to just call GetTableIndexTypeForTableSize(tableSize) whenever it needs to instead.

That also works fine (and allows me reduce sizeof(MyTable) by 4 bytes, yay), but it leads to a measurable (~5%) decrease in performance in my performance-benchmark test -- I believe that is because the current implementation of GetTableIndexForTableSize() includes two branch-operations.

So my question is, is there a clever way to reimplement the above function such that it doesn't require any branching, and thus avoid the 5% slowdown? (I presume using a lookup-table would be a bad idea, since I'd be replacing branch-misprediction delays with RAM-access delays, making things even slower)

Upvotes: 2

Views: 299

Answers (1)

robthebloke
robthebloke

Reputation: 9672

If you choose your enum values carefully, it should be possible to bitwise or yourself to the right enum value. I doubt it will be much that quicker though.

#include <cstdint>
enum {
  TABLE_INDEX_TYPE_UINT8 = 0,
  TABLE_INDEX_TYPE_UINT16 = 1,
  TABLE_INDEX_TYPE_UINT32 = 3
};

uint8_t MyTable::GetTableIndexTypeForTableSize(uint32_t tableSize) const
{
  return (tableSize >= 255) | ( (tableSize >= 65535) << 1 );
}

Upvotes: 6

Related Questions