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

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

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

[bloodline]

Karlos wrote:
@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 ;-)

Hmmm... 2Ghz should get me out of it :lol:

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

[bloodline]

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

My coding ability isn't that great, so I'm not offended :-D

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.

WooHoo! the compiler does the hardwork, so I don't have too. I'm happy about that.

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?

Well I got thinking about the Jumptable idea, as that is how I would do it in ASM, none of this fancy conditional m'larkie... :crazy:

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.

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

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

[bloodline]

Karlos wrote:

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?

Actually I was thinking more about platform independant DSP processing... but there would be a similarity to 68K, yes... as in 16bit instrection word length, etc :-D

[minatorb]

Actually I was thinking more about platform independant DSP processing... but there would be a similarity to 68K, yes... as in 16bit instrection word length, etc

None of the techniques above will ensure anything runs in a fixed time - you can't know at compile time what is cached or which branches are mispredicted.

You shold however be able to figure out the worst case scenario and base your timing around that (leaving some CPU time free just in case) - that's the only way you *know* everything will run on time and I believe that's the way it's done in "hard" real time OSs.



I'm in the process of designing a modular synth which has to work in real time so I'm going to have similar problems soon...

I'll probably go for "soft" real time - let the user set the maximum number of voices.  But just to make sure I'll be doing the important processing in very simple C and using AltiVec extensively.

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

[minatorb]

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.

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.



if (x<2)
   {

   if (x == 0)
     {
     // do 0;
     }

   else
     {
     // do 1;
     }
   else

   }

else  // x is greater than 2
   {

   if (x == 2)
     {
     // do 2;
     }

   else
     {
     // do 3;
     }

   else
   }



//  Naa, stick to case statements....

Um, it's lost all the indentation.

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

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

[bloodline]

Karlos wrote:

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

Yup exactly. I just need a constant time, so that the interpretor doesn't suddenly change it's behavour, when the branch prediction kicks in, or the command stream uses a slightly different algorythm etc...

I started with the idea of a modular synth, which allowed me to have defined "modules" (actually implemented using C++ objects) which performed a particular action on an audio signal... Ocilator, filter, amplifier etc, which could then be arranged in any order to suite the users needs. While this idea is the most efficient in terms of CPU usage, it is limited in terms of usage, having to hard code the modules etc...

My idea now is to have a simple DSP interpreter which can be programmed to perform any action using a platform independant instruction set. This way the user only needs to string together a single type of DSP object to perform any given action. It also allows several operations to be performed in one step. Ultimately the DSP object should actually be a JIT compiler, but that can be though about if my idea is actually a valid one, since it's an oop design, upgrading that would not be a problem.

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

[Kronos]

Now let's muddle the topic even more.....

@Bloodline
Is this virtual DSP supposed to work on the audio-stream in real-time (while it is being played), or will it modify audio-files ?

In the 1st case you would need some sort of external/reliable clock as you never know at what clock the CPU is running, and what other SW sucks at it.

In the 2nd case timing would be pretty much irrelvant (your not planning any parallel-computing I assume).

If timing is important, you can just forget about JIT (since translation takes time and it takes it while the DSP-program is running). You might use some sort of pre-compiling, but I how doubt that you will get much speed-benefit over the func-table.