Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Switch Statements and Branch Tables

Name: Anonymous 2012-04-10 13:55

So let's say I'm making a game, and each monster in it follows a separate movement pattern. For each step of gameplay, each monster must have its movement routine called. Instead of evaluating a conditional to determine which movement pattern a monster should use, I could solve this problem easily by enumerating the movement patterns, and using this value as an index into a jump table.

My first instinct would be to write this (in C) literally as an array of function pointers. The end result would look something like:
for all monsters
    *(movfunctions + monster.movementpattern)(&monster) // call a movement pattern function


Alternatively, I could write a single movement function with a massive switch statement instead:
case MONSTER_KNIGHT: // MONSTER_KNIGHT being #define'd to a constant
    // chase the player
    break;
case MONSTER_BUG:
    // hug the walls
    break;


Now, I get that the entire purpose of a switch statement is to facilitate the creation of jump tables. Could I then assume that the compiled results of both methods would be similar?

Name: Anonymous 2012-04-10 18:40

>>5,7
just store a function pointer 
The architecture I'm working with (ARM) uses a 32-bit address space. I'm assuming that a function pointer is stored like any other memory address, therefore taking up 4 bytes.
The system I'm working on (Nintendo DS) has only 4 MiB of RAM (even less of which is available, due to the C standard library and libnds taking up more than 0 bytes). Honestly, every byte counts here. When 1 byte is more than enough to denote every possible movement pattern, I can't in good conscience use 3 whole bytes for the same effect.

Of course, using jump tables just moves those pointers from the monster type entries into a table. We're only really saving code size if numerous monsters reuse a few movement patterns, and even then the savings would be negligible.

The real reason not to store function pointers in the monster type: You aren't considering that I may need to do something with a monster's movement pattern type than just use it to call a movement function. Perhaps a certain item or action only affects monsters with a certain movement pattern. Whatever the reason, it's a whole lot easier to compare enumerated movement patterns than it is to compare function pointers.
For example, if there are 4 closely related movement patterns that an action will affect in the same way (for example, 4 non-aggressive monsters that move in different ways, but become aggressive if attack), you could easily compare the enumerators like so:
if (monster.movpattern > MOV_PASSIVE_STATIONARY && monster.movpattern < MOV_PASSIVE_CHASE)
With a bunch of function pointers, you'd have no guarantee of what order the movement functions would be arranged in, so you'd have to manually check each possible case.
Not to mention that it'd be much easier to make a mistake when comparing function pointers than with comparing enumerated values.

blah blah blah implementation defined can't assume
Ok, if you want to be pedantic, I know that the C standard leaves the implementation of these details up to the compiler vendor, and we're talking about what an up-to-date GCC ARM cross compiler does.

can't do pointer arithmetic on function pointers in standards-compliant C
Didn't know that, but what I wrote in >>1 was just pseudocode. Everyone writes function pointer tables as, well, arrays of function pointers, and would use the movement type as an index to the array. I'm pretty sure this is standards compliant.

define is retarded
1) Enumerated types don't actually have any real type safety in C.
2) You can't specify the size of an enumerated type in C.
3) You can just as easily write (raises no errors with -Wall -Werror -pedantic):
enum fruits {APPLES, ORANGES, POSTER_NO_EIGHT};
uint8_t = APPLES;

as you could with #define

If C had type-safe enumerated types whose size I could specify (enum uint8_t fruits {...}; enum uint8_t dinner = APPLES;, for example), I'd love to use them. Because I'd have to write my code as I did in 3) to get byte-wide enumerated values, however, I'm not really seeing a meaningful difference versus using a big block of #defines.

>>8
Stop wasting my time and suck my cock, dude.

Anyways, I'll get to the point. I'm going to assume that GCC's optimizations for switch statements are relatively straightforward, and guess that:
1) The array of function pointers works as expected, creating a jump table to a bunch of separate subroutines. The important part being that there are multiple subroutines created, and (here it is!) I have no idea what the binary overhead is for a function entry (I'm guessing that, at the bare minimum, at the start of every function are a few instructions, depending on architecture, for pushing the registers onto the stack, and that, the more functions you have, the more times these instructions have to be duplicated).

2) The single move function with a switch statement will create a giant function with a jump table to the relevant action for each movement type.

What I was really trying to ask, then, is if:
1) Are my assumptions on GCC's optimizations for switch statements and function pointer arrays well founded?
2) If so, what is the potential impact of each method on performance (don't forget about cache misses, the ARM9 has both instruction and data caches) and code size (perhaps more important, given the limitations that 4 MiB of RAM impose)?

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List