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

[Karlos]

Function lookup is great :-)

Generally, the syntax for a function pointer is ugly, but typedefs help a lot

eg

typedef (*)();

So, suppose you want a pointer to function of the signature "int func(const char* blah);"

you would use

typedef int (*MyFuncPtrType)(const char*);

and then you can do stuff like

int foo(const char* blah);
int moo(const char* blah);
int poo(const char* blah);

...

MyFuncPtr p = &foo; /* the & is optional here btw */

p("hello!");

Or create arrays of pointers of this kind,

MyFuncPtr jumpTable[] = { &foo, &moo, &poo };

and do

jumpTable[1]("Hello");

etc...

[Karlos]

@bloodline

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

[Karlos]

@bloodline

Consider

class GameMonsterAI {
public:
virtual void huntTarget(); // AI behaviours
virtual void foundTarget();
virutal void attackTarget();
//..
};

Then later

class UglyMonster : public GameMosterAI {
public:
void huntTarget(); // unique implementation for this monster
void foundTarget(); // ditto
void attackTarget(); // ditto
//...
};

class FlyingMonster : public GameMosterAI {
public:
void huntTarget(); // unique implementation for this monster
void foundTarget(); // ditto
void attackTarget(); // ditto
//...
};

...and you might have loads of different monsters types.

You don't need to know exactly what monster you have to tell it how to huntTarget(), you just need to know that it has that method. This is the root of your "polymorphic" behaviour.

Whatever real monster type you have, simply handling it as an instance of GameMonsterAI and calling the huntTarget() method will invoke the appropriate behavour for the actual monster at hand.

That's about it for virtual functions. Each class that implements a set of virtual functions generally uses a jump table internally, so they're the same thing really.

It's just a nicer syntax :-)

[Karlos]

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.

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.

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).

[Karlos]

LP wrote:
yeah.. polymorphism rules, just too bad c++ is such a killer on the 68k's

It isn't that bad. It all depends on how you design your code - C++ can be more efficient than C code even on 680x0, provided you designed it properly in the first instance (no pun intended).

[Karlos]

@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);
}
}

[Karlos]

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.

I have seen hundreds of instances to the contrary with gcc on about 4 different platforms. It depends on far too many variables outside your control wether or not a partuclar switch/case will be reduced to a jump table or not.

[Karlos]

LP wrote:
True, Karlos true, but you'll have to design it damn efficient to make it really fly.. Were IMHO, C is easier to make efective and faster.. were if you use some of the more heavy mechanisms in c++ you often enter the badlands at first.. But well any god programmer can make anything fly on asorted platforms in different languages... :-)

Steer clear of RTTI, template and STL abuse and you are fine ;-)

[Karlos]

bloodline wrote:
that fits in well with my thoughts.

I thought it might ;-)

[Karlos]

Templates are great - used properly. Used improperly (and the STL itself in places is a prime example) it's a bloatmongers nightmare...

[Karlos]

No likey mutex/semaphore?

Check the totally piece of p*ss multithreading example here

/self->trumpet->blow();

[Karlos]

Someone needs to do the AROS version of the framework core. And by that, I mean really low level, using the most direct API's possible....

If only I knew someone insanely into AROS...

-edit-

I'm still not convinced that the amount of effort I put in is worth what I'd get out!

Thanks... I think :lol:

[Karlos]

falemagn wrote:

If the compiler has the option to use a jump table and it choses not to, obviously it must have some good reasons.

Agreed, but it is not always the case that it's reasons are correct.

GCC is touted as the best code generator etc, but frankly it isn't even remotely true. It is a great compiler, with many source and RTL level optimisations, but the implementation quality of the codegenerator itself varies considerably from platform to platform. This is the trade off you pay for massive portability.

You'll find that indirect jumps often are worth, in terms of cpu cycles, as much as 2 or 3 consecutive if/else statements.

Again this totally depends on the platform.

[Karlos]

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...

[Karlos]

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

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.

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.