#62584 - kevinc - Fri Dec 02, 2005 6:26 pm
Hi. I need to write a function for a program that I'm doing, that reads from a file a bunch of "commands" as integers. The commands are very varied, like pause, push something the stack, pop it, add stuff on the stack, and so on.
The thing is: what is the fastest way of reading the command and choosing what is to be done?
I'm using a big switch list:
switch(commandId) {
case 1: doThis;
case 2: doThat;
...
},
but search is done in linear time (I think) and it's not exactly fast (50+ commands), it's taking about 10% of the time in simple files. And I don't think compiling it in runtime is a good idea (stuff is a little high level, like adding strings) - or secure. I was thinking of creating a function for each command, then put those functions in an array and then call them as:
functionArray[commandId]();
or something like that (if that's even possible).
Any ideas?
#62587 - kusma - Fri Dec 02, 2005 6:33 pm
switch-statements are optimized by the compiler. in this case, you'd basicly get a jump-table.
#62589 - tepples - Fri Dec 02, 2005 6:56 pm
| kevinc wrote: |
The thing is: what is the fastest way of reading the command and choosing what is to be done?
I'm using a big switch list:
switch(commandId) {
case 1: doThis;
case 2: doThat;
...
},
but search is done in linear time (I think) |
Sometimes switch is optimized to a jump table, which is done in constant time (apart from cache effects).
| Quote: |
I was thinking of creating a function for each command, then put those functions in an array and then call them as:
functionArray[commandId](); |
That's called a jump table, and it's very doable. However, if it turns out that GCC is using a jump table for your big switch, then you don't need to make an explicit jump table.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.
#62651 - MrD - Sat Dec 03, 2005 9:24 pm
Be careful, sometimes large switches can cause your code to not compile.
_________________
Not active on this forum. For Lemmings DS help see its website.
#62756 - kevinc - Mon Dec 05, 2005 2:04 pm
Thanks, I'll start researching jump tables :)
#62771 - Vich - Mon Dec 05, 2005 4:54 pm
Yeah, you should choose the array solution! Something like:
Like:
| Code: |
union FunctionArgument
{
int i;
float f;
char c;
};
typedef ArgumentList vector<FunctionArgument> arguments;
std::vector<void (*)(ArgumentList)> functions; // list of function pointers where the functions accept an ArgumentList as argument
void PushFunction(ArgumentList list)
{
// push code here
}
void PopFunction(ArgumentList list)
{
// pop code here
}
void RegisterFunctions()
{
functions.push_back(PushFunction);
functions.push_back(PopFunction);
}
int main()
{
RegisterFunctions();
ArgumentList no_arguments; // Create an empty arguments list
functions[0](no_arguments); // Call PushFunction without arguments
}
|
The above code might not be perfect, but I'll try to remember to post some working code later. Hell, I'll even code the system myself, since it's very handy to have :)
#62786 - sajiimori - Mon Dec 05, 2005 7:11 pm
Wow, that's ridiculously inefficient. :P In real life, you'll want to reuse a single stack to pass arguments instead of creating a new dynamically allocated array for every call.
#62790 - Vich - Mon Dec 05, 2005 7:23 pm
| sajiimori wrote: |
| Wow, that's ridiculously inefficient. :P In real life, you'll want to reuse a single stack to pass arguments instead of creating a new dynamically allocated array for every call. |
Of course, but I just created a quick sample that was obvious and simple ;) I didn't have time to think this through, since my boss would have gone like: "shouldn't you be working?".
#62798 - sajiimori - Mon Dec 05, 2005 8:31 pm
Psh, real life has no place in video game programming! =P
#62840 - Vich - Tue Dec 06, 2005 9:44 am
| sajiimori wrote: |
| Psh, real life has no place in video game programming! =P |
My life(and my job) ?s video game programming ;)
(I'm gameplay programmer, but in my spare time, I like to do some tech code too)
#62864 - kevinc - Tue Dec 06, 2005 4:04 pm
Hmm, now that you mentioned it, which is more practical? A stack using std classes or implement a simpler one?
I also have to handle a map and I've been wondering whether to use std::map (which uses black/red trees but too many templates to count) or create my simple own using AVL trees :P. Is it worth it?
#62922 - sajiimori - Tue Dec 06, 2005 11:12 pm
| Quote: |
| My life(and my job) ?s video game programming ;) |
Cool, me too. :)
| Quote: |
| Hmm, now that you mentioned it, which is more practical? A stack using std classes or implement a simpler one? |
You mean like std::stack? Totally depends on the situation. Some implementations use a singly linked list and dynamically allocate every link as it's pushed and deallocate it when it's popped. In code that isn't speed-critical, that might be okay. The standard interface doesn't seem to include a reserve() method, so there will be allocation every time it grows, regardless of the underlying implementation.
For anything speed-critical, always check how the standard library stuff is implemented, and replace it if it isn't good enough.
| Quote: |
| I also have to handle a map and I've been wondering whether to use std::map (which uses black/red trees but too many templates to count) or create my simple own using AVL trees :P. Is it worth it? |
My approach has been the following. Step 1: See if something simpler than an associative container can be used, and whether the simpler approach is better. Step 2: Try std::map and see if it's good enough. Step 3: Replace it if necessary.