Counter-intuitive optimization

Sometimes I run into an optimization problem that is somewhat counter intuitive. With experience I have gotten reasonably good at knowing what kind of code the gcc optimizer will like and what it won’t like, but sometimes what seems intuitive turns out to be counter-intuitive.

The last such example I ran into was accessing bitmaps. For example you would expect the following macro to be pretty fast:

#define UTL_BITMAP_SET_BIT_IN_POINTER2(pucMacroBitmap, uiMacroBit) \
{ \
ASSERT((pucMacroBitmap) != NULL); \
unsigned char *pucMacroBytePtr = (pucMacroBitmap) + ((uiMacroBit) / 8); \
switch ( (uiMacroBit) % 8 ) { \
case 0: *pucMacroBytePtr |= 0x01; break; \
case 1: *pucMacroBytePtr |= 0x02; break; \
case 2: *pucMacroBytePtr |= 0x04; break; \
case 3: *pucMacroBytePtr |= 0x05; break; \
case 4: *pucMacroBytePtr |= 0x10; break; \
case 5: *pucMacroBytePtr |= 0x20; break; \
case 6: *pucMacroBytePtr |= 0x40; break; \
case 7: *pucMacroBytePtr |= 0x80; break; \
} \
}

The code is a little ugly but it should not be too difficult to follow. Basically what happens is that we work out which byte the bit is in and then set the bit using the case statement. Pretty simple, no heavy computes, just a comparison, a set and a break.

Well it turns out that this is all pretty expensive.

This code looks more expensive than the code above because it works out where to set the bit dynamically, but when you profile it, it is cheaper to run:

#define UTL_BITMAP_SET_BIT_IN_POINTER1(pucMacroBitmap, uiMacroBit) \
{ \
ASSERT((pucMacroBitmap) != NULL); \
unsigned char *pucMacroBytePtr = (pucMacroBitmap) + ((uiMacroBit) / 8); \
*pucMacroBytePtr |= (1 << ((uiMacroBit) % 8)); \
}

All this to show that sometimes what looks cheaper to run is not necessarily the case.

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: