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

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

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

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

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

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

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

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

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

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

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

[itix]

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

If you are updating same variable then switch/case is better... depending on code used GCC can produce code without conditional branches.

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