Wednesday, August 20, 2008

More screen size and premature optimization

Donald Knuth was right. Optimizations I had done for the gba are killing me. And it all has to do with screen size.

See, my engine wasn't designed to properly handle rooms that were smaller than the screen. The camera's position in the room is stored by a number that I assumed was always positive, because, being equal to or smaller than the room itself, I never had to go negative, or outside the bounds of the room. But now with the bigger screen, the camera is often outside of the bounds of the room. So I need to handle all these special cases where the rooms are smaller than the screen. Two things need to happen: first, it needs to just work right. Second, smaller rooms should be centered horizontally on the screen, (unlike the picture in my last post, which looks goofy being shoved up to the left), and bottom-aligned with the screen, so there is less overlap between the HUD and the game. So I've got that to do, which I've started on, but is messy.

A big chunk of the problem was because of stupid optimizations that I (needlessly) did. See, the gba and ds don't have floating point units. And can't do divides with any reasonable speed. But in unsigned binary, bit shifting right by 3 is the same as dividing by 8. And because the tiles are all 8 pixels, I'm dividing by 8 all over the place. So instead of telling it to divide, I bit shifted, to make sure it was fast. Now this was stupid, because a good compiler (which gcc most certainly is) will do this optimization for me. But I figured it wouldn't hurt to make it obvious that it was happening, and thus prevent the compiler from randomly deciding NOT to bit shift and do a slow division. BUT that doesn't work if your number is signed, which mine now is. This is because negative numbers are represented in two's complement. You can still do fast divides with clever bit-shifting, but not as simply as just shifting right 3 bits. So now I need to go change all those places where I was trying to be clever back to actually using a normal divide, and let the compiler do the optimization.

Lesson of the day: my compiler is smarter than me. Let it do the clever stuff.

1 comment:

cearn said...

"BUT that doesn't work if your number is signed, which mine now is. This is because negative numbers are represented in two's complement. You can still do fast divides with clever bit-shifting, but not as simply as just shifting right 3 bits."

Actually division-by-shift works just as well for signed numbers, if you actually declare the variable as signed. 'int' is sign-extended, 'unsigned int' is zero-extended.

The only issue with normal division and shifts is the rounding for negative numbers. (-1)/8 gives 0, whereas (-1)>>3 gives -1. But since you might actually want the latter result (because otherwise there's be no difference between -1/8 and +1/8), using shifts might actually be the right thing to do here.

And for the record, GCC will indeed change a division by a shift, but for signed ints will also add addition instructions to keep the rounding in accordance to regular division.

Optimization and C

Starting this next game in C, I've known there will be places where C isn't fast enough, and I'd have to drop to assembly to ...