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

[falemagn]

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

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.

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

[falemagn]

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.

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

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

If the range of possibilities is very narrow, gcc is likely to emit a series of if/else stamements. If, on the other hand, the list of possibilities contains more than a certain platform-specific minimum number of items, then a jumptable will be output.

The compiler makes always the right choice for the target cpu. Bugs apart, of course.

[falemagn]

Again this totally depends on the platform.

No one said otherwise. Generally speaking, though, an indirect jump spoils branch prediction, regardless of the platform, and may cause cache misses. Depending on the target cpu, the compiler will always make the right choice.

[falemagn]

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 don't see how. Either you have to build a table with the addresses of the functions/labels, or you need to build a case/switch table. Practically the same amount of code needs to be typed in, with the advantage that, in the case of the switch/case structure, you don't risk putting an address at the wrong place.

[falemagn]

Karlos wrote:
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.

Uh, how's that different from an hand-made jumptable? At least with the switch/case statements the compiler _does_ have the possibility of inlining.

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 compiler will always optimize your code, making always the right choice. It's got more knowledge than you about the target cpu. Unless you can find a patological case, gcc produces the best possible code for switch/case statements.

[falemagn]

Try debugging a logical error in a switch case with several thousand case values - even little things like a missing break. The sheer size of the construct makes it difficult to see what you are doing.

Again, how's that different from, say, putting the function's address at the wrong place in the table?

Moreover, if you have a switch/case construct where you simply jump to functions, you don't need 'break' at all, use 'return' instead.

[falemagn]

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.

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

You don't seem to get the point... the jumptable, regardless of the fact it spoils branch prediction, is still the fastest approach from a certain number of choices on.

If you have only an handfull (processor-specific) number of choices, the compiler will emit if/else code. The compiler does that automatically, depending on the relative average costs of the jumptable vs if/else on the basis of the number of available case choices.

[falemagn]

A non-jump table based switch/case (ie those that are equivalent to nested if/else if) has a (usually linear) dependency on the position in the construct.

Any decent compiler will emit code that does a binary search over the possible choices, hence it's O(log n), which means that, in the worse case, that is a totally sparse set of choices which spans the whole int domain[1], assuming an integer is 32 bit, you get a maximum of 32 comparisons. That's of course far from being the average case. The typical scenario is 3 or 4 comparisons.

[1] That means it comprises of 2^31, that is 2Giga, choices.

[falemagn]

That is the point I was making. I had assumed that bloodline had a very large number of choices (thousands) based on what he said earlier in the thread - ie it appeared to be an emulator core, with a case per opcode style affair and also he explicitly asked about how to implement jump tables in C.

I was commening on the part where you said, more or less "so why if jumptables are that bad the compiler still builds them?". I know perfectly well that that's not what Matt asked, I've answered to his original post already, that was an answer to your post. I thought it was clear.

[falemagn]

What's wrong with writing filters in C/C++/whatever other compiled language?

If realtime usage is your goal, that is.

Of course if you only provide a limited set of things your interpreded filters can do, then you might achieve realtime capabilities anyway.

[falemagn]

I've done that, it's very fast, but not very interesting and litmits you to the algorythm you choose when you wrote the program.

Err... ever heard of the work "plugin"? :-P

[falemagn]

You honestly expect me to figure out how to implement a plugin system?!?!

Uh... you have functions, you have a functiontable, you take the address of the functions and put them in the table...

Amiga-like shared libraries offer plugin functionality for free :-)

I prefer the virtual DSP idea anyway, as it is platform independant and is not limited to this project

You may just as well compile the functions on the fly. Have them written in C/C++, invoke the compiler, load them.

Fast and portable. Yes, you need to ship with or rely on a C compiler, but so what?

The other approach would be to compile your own scripting/opcode language. Unless you want to allow for self-modifying filters (:-o), compiling them will always give better perfomances than interpreting them.

[falemagn]

Karlos wrote:
The binary script interpreter may be slower than a native mechanism, but 1000x more fun to do :-)

Well, I kind of think it distracts you from the real code, doesn't it? I mean, Matt should be concentrating on writing the "sound" part of the code, not the interpreter :-)

Anyway, just came across this SMALL language. Quite interesting...

[falemagn]

SMALL looks cool!

Indeed it does. And it gets compiled down to bytecode. It's precisely what you need, give it a look :-)