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

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

[bloodline]

Kronos wrote:
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 ?

Real time

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.

A simple 1ms clock is what was I planning... The Audio stream would be cut up into 1/1000th of a second frames with an expiry time... if the frame reaches the play buffer after it's time limit has expired it would be dropped, this causes clicks and pops if the the machine can't process the frames in time... in which case the user would need to specify larger frames.

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

I'm struggeling with Multithreading... it just takes too long to set up. And I'm not even doign anything difficult, just using SDL's multithreading functions.

It would be nice to have certain parts of the program asynchronous... but I can work around that.

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.

Then I'll forget about JIT, it doesn't matter. I'm just doing this to improve my understanding of the problem. It's a hobby, people! :-D

[Kronos]

Since you alllrady cuted the stream into pieces, with "best used by" date, you shouldn't even have to worry about timing at all.

The question is just if the maximum time a filter needs is still in time on the specific computer in the a specific load-situation is still within limits. Thats something decided by the user and the coder of the filter. If a package is done faster, no prob....

So the question is, how many free cycles you still have after applying the effect to every sound-bit of the stream, and wether that is enough for decoding.
 
If not, you'll need pre-compiling (no decoding during run-time).

Hah, now I'm quite happy again doing the completly timing-issue free stuff I'm doing  :-D

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

[bloodline]

Kronos wrote:
Since you alllrady cuted the stream into pieces, with "best used by" date, you shouldn't even have to worry about timing at all.

The question is just if the maximum time a filter needs is still in time on the specific computer in the a specific load-situation is still within limits. Thats something decided by the user and the coder of the filter. If a package is done faster, no prob....

Each frame is on 1ms in size so the it must get fromt the start to the end of the effects chain in 1ms, or it gets dropped. I would probably add a check at every DSP, to make sure the Frame is still valid before wasting CPU time on it.

If the user specifies larger frames it has more time to pass through the effects chain... but the longer it takes to pass through the DSP.

The signal starts life with a DSP object, which either mathmatically creates the signal or reads a sample buffer, or maybe a bit of both ;-), passes through other DSP objects (which act upon the frame and then pass it on) and ends at the play buffer, from which the DACs play the sound.

The code for the DSP objects is not really time dependant, only to say that it must execute as fast as possible and behave the same each time.

My idea for 1ms frame comes from the idea that each audio signal is 16bit and sampled at 44100Hz... so each frame is about 86kb... this easily fits into a modern L2 cache and probably some L1 caches (though my Athlon64 only has a 64kb L1 data cache). Now if the processor concentrates on 1 audio stream at a time, it will spend pretty much all it's time working from the cache.

Now I need to get the DSP interpretor to fit into the L1 cache, so that Main Memory access is minimal.

So the question is, how many free cycles you still have after applying the effect to every sound-bit of the stream, and wether that is enough for decoding.

That's a good question, tests have shown that my old Athlon 600Mhz could pump a single "1ms Frames" through about 12 hardcoded Lowpass filter objects in 1ms, though trying to get that Data to the Sound card to about 50ms. Obvously a virtual DSP object would be much slower. But speed isn't an issue as I now have a much better CPU :-D

If not, you'll need pre-compiling (no decoding during run-time).

Hah, now I'm quite happy again doing the completly timing-issue free stuff I'm doing  :-D

:-D Nah, this is more fun.

[bloodline]

Karlos wrote:

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.

I must say from my point of view, watching you two argue on the same side has been an huge source of entertainment... I was going to say something but I decided to put a sock in it ;-)


WooHoo... an impressive 60 odd posts, dominated by Karlos and Bloodline before the sock showed up :-P

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

[bloodline]

Anyway, cheers for your help guys!

I've learned a lot of cool stuff.

a) How to make a Jumptable in C
b) Function pointer tables
c) And that gcc will try and get the best out of the code, I certainly feel much more comfortable using switch/case structures now :-D

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

[Kronos]

More food for thought:

I don't know much about DSPs, but....

One filter-function could easily consist out of hundred commands.
The sequence would need to be called for every word of the stream (at
the same fequence as the sampling-frequency).

Could result into 10000 and more commands to be decoded for each 10ms
part.

But since you don't plan to simulate a real DSP, you could create one
that applies commands to every sample in the 10ms-part.

Commands that has commands more sophistacted that the typical
RISC-like DSP-opcodes.

And/or make sure that the interaction between 2 opcodes is clearly
defined, allowing the translation-blocks to be just cued together,
with the right add filled in for any conditional possible (that would
pretty much be the pre-complile case).

[bloodline]

Kronos wrote:
More food for thought:

I don't know much about DSPs, but....

One filter-function could easily consist out of hundred commands.
The sequence would need to be called for every word of the stream (at
the same fequence as the sampling-frequency).

Could result into 10000 and more commands to be decoded for each 10ms
part.

But since you don't plan to simulate a real DSP, you could create one
that applies commands to every sample in the 10ms-part.

Commands that has commands more sophistacted that the typical
RISC-like DSP-opcodes.

And/or make sure that the interaction between 2 opcodes is clearly
defined, allowing the translation-blocks to be just cued together,
with the right add filled in for any conditional possible (that would
pretty much be the pre-complile case).

I though I would implement a good, but simple general purpose instruction set, and then have some "Application Specific" SIMD instructions which perform a sequence of operations suited to Audio processing (Filtering, amplifying, modulating, attenuating, mixing etc) and acting over a large area (or even the entire frame).

This way, the Audio DSP would be as fast as possible, but each object would still be able to be programmed to perform tasks I hadn't thought of.

My instruction set would be 16bit, and use an 8bit opcode (256 instructions), with 2 4bit operands (to allow 16 registers, chosen because I'm a 68k fan, the AMD64 has 16regs and that amount easilly fits into the PPC).

Also I'll have a special "immediate" intruction to allow the loading of immediate data.

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

[minatorb]

Why are you using 16 bit values for audio?  Pro audio stuff uses 32 bit floating point or even 64 bit FP these days.

As for registers remember x86 CPUs use rename reisters.  You can't access them directly but you can indirectly just allocate a load of variables in C and work on them.

You can do the same trick with the cache, you can test this by moving big chunks of data around using loads of variables - I tired this years ago on my PC and the speed difference was *amazing*.

[MskoDestny]

I don't think he ever said that the audio data itself would be 16-bit.  Just that the instruction set for his virtual DSP would use 16-bit opcodes.  Much like how the SuperH series uses 16-bit opcodes even though it can work on 32 and 64-bit floating point numbers (well certain members of the SuperH series anyway).

Of course 16-bit opcodes can be quite limiting if you have a fixed width instruction set.  There's a reason why most RISC architectures use 32-bit opcodes.

[bloodline]

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

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. The Idea of a virtual DSP sounds like more fun. Fun being the goal :-)

minatorb wrote:
Why are you using 16 bit values for audio?  Pro audio stuff uses 32 bit floating point or even 64 bit FP these days.

As for registers remember x86 CPUs use rename reisters.  You can't access them directly but you can indirectly just allocate a load of variables in C and work on them.

You can do the same trick with the cache, you can test this by moving big chunks of data around using loads of variables - I tired this years ago on my PC and the speed difference was *amazing*.

Yeah, my Edirol FA-101 actually runs at 192Khz @ 24bit, but as I'm just developing this idea I wanted to keep it simple and fast as possible, while keeping it useable. CD quality seems like a good trade off.

MskoDestny wrote:
I don't think he ever said that the audio data itself would be 16-bit.  Just that the instruction set for his virtual DSP would use 16-bit opcodes.  Much like how the SuperH series uses 16-bit opcodes even though it can work on 32 and 64-bit floating point numbers (well certain members of the SuperH series anyway).

Of course 16-bit opcodes can be quite limiting if you have a fixed width instruction set.  There's a reason why most RISC architectures use 32-bit opcodes.

Yup, while I did say that my tests were done using 16bit audio data, there is no reason why it can't be user selectable.

And you are right that I have pretty much settled on a fixed width 16bit instruction word lenght, and practally no addressing modes, everything will be "register to register". This should give me enough room for a simple general purpose set + the application specific instruction required to get maximum speed.

[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