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

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

[Karlos]

falemagn wrote:

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.

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.

[Karlos]

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

Never mind, I think we are talking cross purposes here :-)

I am saying that if you make a large switch case, that construct itself ends up as a jump table, where you index it to reach the code address of a given case handling code block. This is similar to the function call overhead of a handmade jump table aleady.

If the code for the case is all inline once you get theree, all is good. If, on the other hand, you simply trampoline into another function, you have made 2 jumps to reach the code (the case/switch jump and then the function call it trampolined into).

Unless your function definitions are visible in the same translation unit as the case/switch construct during compilation there is no guarentee they will be inlined.

[Karlos]

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

It isn't different - but it is easier to find when looking at the code for it.

[Karlos]

@bloodline

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

My personal preference is for a handmade jumptable for this kind of thing - like the z80 example earlier.


However, as gcc will try to do that for you anyway in your switch/case, go for that. The only advice I can give is to try to inline those functions that or ensure the compiler can by making their definition visible to the switch/case.

(Actually, in the real z80 example, I went pure ASM for an emulate() core and had a literal jump table; the code was physically in the table so that every 128 bytes was a block of code to emulate an instruction with the code needed to calculate the next block to jmp to on the end of each handler, then nop padded to the next boundary.... but that is another story entirely ;-))

You will get larger code, but less jumping about within it.

[Karlos]

itix wrote:

Regarding jump tables... it seems that it does not good for branch prediction...

Erm, didn't we just establish that the compiler typically optimises large case/switch by making jump tables :-?

[Karlos]

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

[Karlos]

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

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.

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?

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.

[Karlos]

bloodline wrote:

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

That's guarenteed for a jump table and highly likely for a packed (meaning no gaps) switch/case construct.

Pick one and get on with it :-D

So, this command stream. Would it resemble 680x0 opcodes? You did say about 64K of them at some point?

[Karlos]

We were talking about constant time in the code rather than strict "fixed time". Of course nothing can ever run truly fixed time on any machine with a cache/branch predictions/etc, as you say.

However, we can say the complexity of taking a from a jump table is independent of the position in the table.

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.

[Karlos]

minatorb wrote:

You can also do it with if/else if you can base your condition on a number, Pain in the ar$e to maintain and not terribly readable though.

I think this is precisely what bloodline was trying to avoid doing. This kind of construct is really bad unless you have a small range for x and some values are statistically much more likely than others (put those first).

[Karlos]

falemagn wrote:

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.

:lol: 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 think you and I are having a communication barrier :-) I am certianly not arguing with you at all that if/else can be better than a jump table under the appropriate circumstances. This I am fully aware of, along with the factors that determine which is better for a given instance.

In this specific instance, with the assumption that a large number of case options (more than any if/else would efficiently cope with) and considering the fact that he asked how to make a handmade jump table but was unsure how, I simply answered the question.

The compiler's ability to judge the cost of if/else versus jump table (for bloodlines case) was irrelavent here because  aside from the fact it was not what he asked, a switch/case construct would almost definately generate a jump table if he were to use a large number of cases (as already assumed).

Given this it comes down to style. I personally find large switch/case constructs extremely ugly and difficult to manage compared to a jumptable / index.

With that, can we please drop the issue now? It's getting silly.

[Karlos]

falemagn wrote:

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.

Ah, that was supposed to be rhetorical :-D I wasn't actually asking a question and I never expected anybody to answer it :-)

Anyhoo, we are agreed, the compiler knows where to do if/else versus jump table for a switch/case construct :lol:

[Karlos]

@bloodline

You know, function jumpt tables are one way to implement a plug in mechansim ;-)

Unlike switch/case constructs (booo rubbish) a function table can me modified at runtime :-)

[Karlos]

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