jump tables (-Edit- Eliminating conditional statements :-))

[bloodline]

Is there any "nice" way to do this in C, pointer magic etc?

Imagine I have an array of pointers to allow me to jump to a subroutine based on the index stored in a variable:

int* jump[3];

jump[0]= &task1;
jump[1]= &task2;
jump[2]= &task3;

a=user_input(); // where the user could enter 1, 2 or 3

Goto jump(a);
task_return:


task1:
Do Something;
goto task_return;

task2:
Do Something else;
goto task_return;

task3:
Do Something different;
goto task_return;


I have no idea why I'm asking this... :crazy:

[bloodline]

Piru wrote:
I won't give you the exact solution, but this should help still:

Code: [Select]


#include <stdio.h>

typedef int (*funcptr_t)(int, char *);

int func1(int x, char *str);
int func2(int x, char *str);
int func3(int x, char *str);

int main(void)
{
  funcptr_t funcarray[3] =
  {
    func1,
    func2,
    func3
  };
  int i;

  for (i = 0; i < 3; i++)
  {
    int ret;

    ret = funcarray[i](i*i, &quot;moo&quot;);
    printf(&quot;ret %d\n&quot;, ret);
  }

  return 0;
}

int func1(int x, char *str)
{
  printf(&quot;func1 x=%d, str=<%s>\n&quot;, x, str);
  return 1;
}

int func2(int x, char *str)
{
  printf(&quot;func2 x=%d, str=<%s>\n&quot;, x, str);
  return 2;
}

int func3(int x, char *str)
{
  printf(&quot;func3 x=%d, str=<%s>\n&quot;, x, str);
  return 3;
}


Hmmm, yeah that actually makes more sense than what I was trying to achive!! Cheers :-D

[bloodline]

Karlos wrote:
@bloodline

Of course C++ virtual functions are a bit nicer to use ;-)

Que?

[bloodline]

Hmmm, But I can't see how virtual functions are applicable to my initial problem, which is to speed up a conditional path... (I've only realised that is what I was trying to achive after I saw Piru's example).

-Edit-
If you look at my original post, I could have written:

switch(a) {


    case 1 : Do_something;
    case 2 : Do_Something_else;
    case 3 : Do_something_different;

}

I'm not sure why I chose to do it the other way... except maybe to eliminate any conditionality from the code.

[bloodline]

So I suppose my question is, How does one eliminate uncertainty from a program :-D

[bloodline]

Karlos wrote:
Jump tables can be much faster than switch/case constructs. The latter often end up like large nested if/else if, especially when the blocks of code are different sizes or if the range has gaps. The further down the switch  you go, the longer it takes.

Yup, I though I was on the right path... the idea of having to evaluate 60000 odd possible conditions made me panic... The Jumptable/function look up table is the best option!

A function lookup table can be written instead. It totally doesnt matter if the functions are different sizes or if there are holes in the range of cases - provided your overall table is big enough for every known case value.

The function lookup table effectively takes a constant time to evaluate for any case.

"Constant time to evaluate" are the magic words here :-)

I use them in quite a few places where you might think a switch/case would do (I only use the switch/case when the range is small and the code for each case is so small that physically calling the function would take longer).

Have you go any nice and simple, I mean really dumb, examples of function look up's that I can compare and contrast with Piru's? I've never seen these before and I want to get a few in to my brain :-D

[bloodline]

falemagn wrote:

 Jump tables can be much faster than switch/case constructs. The latter often end up like large nested if/else if, especially when the blocks of code are different sizes or if the range has gaps. The further down the switch you go, the longer it takes.

Decent compilers (and gcc is one such), compile switch/case statements down to a jump table for when there are no holes in the range of possibilities, or to a binary search tree in the other case (it prefers saving space, if the range is very sparse).

Well you know that I'll be using gcc (I don't think I have any choice!) :-D ;-)

Would I have to specify an optimisation flag to get it to generate the table, or is it a standard feature?

Therefore, you go from costant time to O(log n) time.

@bloodline

Using functions is perhaps cleaner, but can be overkill for the functions prologue/epilogue. If you are using gcc, you may want to use its "computed goto's" extension.

It works like this (notice the double ampersand!):

Code: [Select]


    void *jmptable[] =
    {
        &&lab1,
        &&lab2,
        &&lab3,
         ...
        &&labN
    };

    ...
    ...

    goto jmptable[foo];
    returnpoint:
    ...

    lab1:
    ...
    goto returnpoint;

    lab2:
    ...
    goto returnpoint;

    lab3:
    ...
    goto returnpoint;

    ...

    labN:
    ...
    goto returnpoint;


This is pretty much like the GOSUB statement from BASIC.

That is pretty much what I was trying to do in my original example, I rather like the simplicity of it. Cheers Fabio!

[bloodline]

falemagn wrote:

bloodline wrote:
If you look at my original post, I could have written:

switch(a) {


    case 1 : Do_something;
    case 2 : Do_Something_else;
    case 3 : Do_something_different;

}

I'm not sure why I chose to do it the other way... except maybe to eliminate any conditionality from the code.

If that's really what it would look like, save your efforts for other parts of the code Gcc will compile that down to  a jumptable.

Yeah, my code really would look like that. I was thinking about some kind of command parser, where commands could quite happily be a simple range of numbers, with no gaps.

[bloodline]

Karlos wrote:
@bloodline

Not that I can show you right now as I'm at work.

Basically the example I posted before the C++ thing is it really

typedef (*)();

So, imagine you were writing a z80 emulation...

typedef struct Z80_t {
/* register set, etc etc */
} Z80;

typedef void (*Z80InstFn)(Z80*); /* z80 instruction handler */

/* z80 instruction handling functions */
static void z80_NOP(Z80* cpu)
{
cpu->regPC++;
}

static void z80_LD_BC_NN(Z80* cpu)
{
cpu->regB = cpu->regPC[2];
cpu->regC = cpu->regPC[1];
cpu->regPC+=3;
}

/* and lots more! */

static Z80InstFn instTable[256] = {
/* all the function names (& is optional) */
&z80_NOP,
&z80_LD_BC_NN,

....all the others...

&z80_RST_38H
};

...and you might have an execute function like this...

void execute(Z80* cpu, int maxInsts)
{
while (maxInsts--) {
instTable[cpu->regPC](cpu);
}
}

That's grand! and a good example that fits in well with my thoughts.

[bloodline]

Ok, good. Now I've got one gripe sorted out... What about the adition of 5 new keywords/functions and a new datatype to standard C/C++ :-D

You're gonna love this.. :lol: I have far too much free time...

I'm having a horrid time with multithreading... mutexs and semaphores take far more work that I can be bothered with... soooooo, I want to change C/C++ slightly to make my life easier.

My new keywords/functions are:

lock()
unlock()
spawn(function pointer)
int test() (returns true or false)
void wait(flag)

My new datatype is:

flag


Today is the day of reinventing the wheel... :-)

The idea is that all global variable variables/data structures are shared between all threads. But in order to use one, you have to lock() it first (all global variables and data structures must be locked before use). lock() is a synchronous function, so if you lock a global variable which is already locked the prorgam flow will stop until it's unlocked(). You should unlock() the variable after you have used it.

The test() function will test a global variable. If the variable is already locked the function will fail (return false). If it's unlocked, it will be locked() by the function, and will have to be unlocked() for any other thread to use it.

spawn() is simple, it just spawns the function as a thread.

wait() is synchronous and will wait for a flag to be set to true, if the flag is already true it will set the flag to false and continue execution.

Ok bored now... back to my jumptable thing :-D

[bloodline]

Karlos wrote:
No likey mutex/semaphore?

Check the totally piece of p*ss multithreading example here

/self->trumpet->blow();

Yeah, I've already had a little sit down with your code, I'm still not convinced that the amount of effort I put in is worth what I'd get out! :-D

[bloodline]

Karlos wrote:
Anyway, we are getting off topic ;-)

Getting back to bloodlines case

If he is doing what I think he is doing, a manual jump table makes more sense given the number of cases he will have. It's easier to manage a large jump table than it is to manage a large switch statement...

I dunno... The switch/case structure seems quite manageable, and certainly requires less coding... Also I rather like the idea of being able to use functions rather than gotos.

[bloodline]

Karlos wrote:
Whichever route you choose, a good compiler can only manage bad code so far ;-)

:lol: Yeah, I probably shouldn't have been worring about this.

If you use a large case/switch, make sure your handling code is nicely inline and not just trampolining into functions, otherwise you have the overhead of the switch/case (regardless of how it is implemented by the compiler) and the function call overhead on top. If you do start to find you are writing more and more functions for handling the cases, then a jump table is better in the first instance.

What about some inline code... and some functions...?

As I said at the start, use a switch/case when the range is unbroken and the code required to perform the operation for each option is small compared to the overhead of calling a function. This way, as falemagan says, the compiler will be able to best optimise your code.

The Range can be unbroken, that's not a problem. Some options will be small, some will be large...

Suppose for a moment we have an event stream, some events can be handled simply by updating a variable... others would require calling several functions....

[bloodline]

Karlos wrote:
@Bloodline

Don't listen to any of us. We are just confusing the issue :-D

Even if you write the most atrocious code ever, the compiler and CPU will get you out of it ;-)

Hmmm... 2Ghz should get me out of it :lol:

[bloodline]

Karlos wrote:
@bloodline

Just scanning back over this thread and realised it looked like I was denigrating your coding ability, which I wasn't actually trying to do.

My coding ability isn't that great, so I'm not offended :-D

I was trying to point out that compilers are generally only able to optimize code for which it has no real idea what the purpose is, therefore if you choose a bad algorithm or control mechanism, all the compiler optimisation in the world won't help that much - it doesn't actually have any knowledge of what you are ultimately trying to accomplish.

There is a common trend to assume that you can approach something without much forethought and just let the compiler decide what to do. Just looking at some of the argument in this thread is interesting:

1) switch/case can be optimised by the compiler.
2) jump tables can be bad because of mis-prediction and cache misses.

Therefore one should always use the switch/case.

WooHoo! the compiler does the hardwork, so I don't have too. I'm happy about that.

And yet, one of the main optimisations employed by the compiler for switch/case is to create a jump table to allow it to evaluate the switch in constant time, which is exactly what a jump table is for :-)

So, how bad is the original jump table idea really?

Well I got thinking about the Jumptable idea, as that is how I would do it in ASM, none of this fancy conditional m'larkie... :crazy:

See my point?

It ultimately all depends on what you are planning to do with the code and what the desired runtime behaviour is, how likely repetetive calls to the same code are etc. Only you as the developer know these criteria.

I just want to be able to parse a stream of command to control some settings in real time, where each command must take the same amount of time...