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

[falemagn]

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.

[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!

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

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

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

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

[LP]

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

[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 ;-)

[LP]

:lol:

containers and the dear templates you say, eh?
.. yeah, I'll think of it next time the Amiga is on for coding..  :-)

[Karlos]

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

[Cymric]

@falemagn:

Funny how we are supposed to unlearn all these dirty goto methods, only to reintroduce them via the backdoor route of the compiler... Yes, I realise what a compiler creates is not meant for mortal eyes, but still :-).

[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

[Karlos]

No likey mutex/semaphore?

Check the totally piece of p*ss multithreading example here

/self->trumpet->blow();

[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

[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: