How to Dig8 implements expression operations?

dreason85

Mr. colB, can you explain how your Dig8 implements expression operations?

colB

It's a big topic, here is an overview, any questions about more specific details, just ask.

===================================

Expression decoding in Digit8 is a multi part process.

The expressions are initially in text string based 'infix' format, so for example 123+45 where the operator '+' is inbetween the two operands which are numeric values represented as strings of character.

That is a complicated format for a computer to process and very inefficient, particularly with more complex expressions...

Something like:

(t/123) * (t + 50) >> (t^1234) / 72...

where to start?

First of all, the strings like (1, 2, 3) representing the number 123 and (>,>) representing the >> right shift operator need to be read, decoded and turned into single values and tokens representing operators. This is basically a state machine with a whole bunch of if/then/else statements looking for the next item in the string to see if its part of the same object or the start of a new one...
This is the tokenizer

Then the cool part happens, the now tokenized infix expression is converted to RPN format (Reverse Polish Notation). This orders the expression so that operators and operands can just be read in sequential order, operands first.

So for e.g. 23 + 52, the RPN order would be 23, 52, +.

The process would be something like:
23 is read, it is a value, so is pushed to the working stack,
then 52 is read, it is also pushed to the working stack,
then + is read, that is an operator that needs two operands, so two operands are popped from the stack, we get our 52 and our 23 back off the stack, and process them with the + operator, then push the result back onto the stack...
and that's us finished, so the value on the top of the stack is the answer.

for 23 + 52 * 7, the order would be 52, 7, *, 23, +
So first we get 52 which is a value so it is pushed to the stack,
then we get 7 which is also pushed,
then we get *, that is an operator requiring two operands, so we pop two value from the stack and apply the * operator to them, then push the result (364) to the stack
the next read gives us 23 wich is a value so we push it,
then next we get + which is an operator, requiring two operands, so we pop two values off the stack, we get 23 and 364, and apply the + operator to them then push the result
and thats us finished, so the value at the top of the stack is the answer.

Following this method, complex nested expressions can be processed very efficiently. No parenthesis are required. All processing is basically just pushing and popping to and from the working stack, and an operator dispatch to process the actual operations.

————-

Conversion from infix to RPN is done using an algorithm called the 'Shunting Yard Algorithm' invented by Edsger Dijkstra. It's a beautifully elegant process, better explained in lots of other places. Wikipedia is a good start.

The trick with digit8 is that tokenising the expression text, and converting from infix to RPN is slow and complicated, but only needs to happen once each time the user edits the expression. However, processing the RPN is fast and efficient, so we can do that at audio frequencies even with relatively large expressions.

The extras like ternary expressions, special variable parameters (t, a, b, f, p, i, v), and the pseudo array processing are just shoehorned in to the basic process without too much extra effort.

Implementation is somewhat tricky in the context of Reaktor. Particularly back when digit8 was created, there were no combined event/audio outputs, so the iteration management is a bit messy, and could probably be improved.
Also, managing the compiler load was not so easy, there were a couple of times when the thing started taking a loooong time to compile and some tricks were needed to 'help' it out.

And of course, there is the lack of a text input facility in Reaktor, so the button keyboard and screen also had to be constructed.

dreason85

My question is, what you input is an infix expression, but how do you make it a suffix expression？

dreason85

Can you explain this process in detail? Because I did find that the Reaktor operation is very complex.

colB

https://community.native-instruments.com/discussion/comment/162767#Comment_162767

Read this, it explains it better than I can

https://en.wikipedia.org/wiki/Shunting_yard_algorithm

dreason85

https://community.native-instruments.com/discussion/comment/162768#Comment_162768

I have read it and I can roughly understand the principle behind it! But my question is, wouldn't operating these in Reaktor cause a time delay? But the sound signals are real-time, how can they be synchronized?

colB

As I explained in my first post, most of the work doesn't need to happen at audio rate, only when edits are made to expressions.

Only the final part of reading and processing the RPN formatted code needs to happen at audio rate.

There are three stages, driven by four primary iterators, I've highlighted them here. I've also circled the audio rate clock driver…

The first two iterators 1, and 2 drive the tokenizer and shunting yard process (they are somewhat combined), Iterator 3 reads the RPN output and fills a stack to be used in the audio stage. iterator 4 is the only one that drives audio rate code.

The Audio rate clock generates regular events at audio rate (this was important back on the old version of Reaktor that digit8 was developed on, because of incompatibility between audio and even core cells).

Each audio rate event starts an iterator, which runs at maximum rate and is used to read operators and operands off the RPN stack, and process them to find the result of the expression for that audio tick. When the whole expression is processed and the result calculated, an event is fed back to the iterator to stop it (all four iterators work this way). This happens on every audio tick, each time, the whole RPN encoded expression is fully processed, driven by iterator 4.

If you compare simple expressions with more complex ones, you can see a significant jump in cpu required, because iterator 4 runs for longer because there is way more stack manipulation and operator dispatching to do.

The operator dispatch is probably the biggest cpu hog, because in Reaktor you can't do it in a really efficient way (like you would in C or assembly), so in digit 8 by far the most operators are binary, so they have two operands.

Here is the code that checks the type of the current operator:

Here is that 'proc binary op'

You can see that it pops two values off the working stack, processes the op and pushes the result back onto the working stack (like I described in my first post)

The nasty bit is inside that proc macro, where we work out what actual operation to apply to those two operands… here it is:

There are 18 binary operators, to work out which one, I used a tree, so that there are never more than 5 comparisons needed to work out which to use. I we just used a bunch of if/else type logic, some would be very fast, but some would take way longer to resolve, so some expressions would end up running way slower if they happened to use more of the unfavoured operators… not good.

IIRC, I built two different variations of this tree structure, and picked the one that performed better.

There are alternatives I can think of now that might be faster, but this one works and seem to run pretty well, so :)

One of the more complex expressions in the snapshots has 32 operators, the audio rate iterator runs for 65 iterations. It does that every audio tick (or every 2nd or 4th or whatever, depending on the sample rate setting on the digit8 panel). About half of those iterations use the operator tree. On average the do maybe 2 or three stack operations… Stack operations are 3 array accesses and 1 arithmetic operation. So its relatively efficient…

For a long expression, 150 routing steps for operators, maybe 350ish array accesses, and whatever supporting code like the clock driver, cost of going from primary to core per iteration, those comparisons to select operator type… stuff like that… the cpu will optimise quite well, because there is lots or repetition (the main variable 't' that is the core of bytebeat process, doesn't change value every tick, it depends on the pitch, so maybe every3 or 4 tick or more or less depending on pitch This helps cpu hardware optimisations a LOT. A lot of the code uses integers, and information like operator type is bitwise encoded so can be retrieved using a bitwise AND operation… bitwise integer stuff is usually fast, and encoding a bunch of data into a single integer is tight. Core compiler optimises the code well too, and a few variations of different parts were tested for performance during development. So on my ancient desktop, that complex expression runs at about 10% cpu (goes up to maybe 27% when the pitch is ramped up to horribly unmusical heights :), but tops out there)

When I was building this, cpu was a big worry, I fully expected it not to work with anything but the simplest expressions (or not at all), it was a pleasant surprise how efficient it turned out to be.

dreason85

I know where my problem lies. I have been fixated on the internal processing of the Core Cell, neglecting the Iteration module of the Primary Level. In fact, I need to use the Iteration module to achieve all of this. However, since the Core Cell does not have the Iteration function, this is also why there is delay problem in the Core Cell. Therefore, using the Iteration module immediately solved this problem.

dreason85

But to be honest, I really hope that the Core Cell can have the Iteration function, so that many processes can be encapsulated in the Core Cell for implementation.

colB

https://community.native-instruments.com/discussion/comment/163390#Comment_163390

This has been asked for since core was first released back in 2005. It was always planned to be implemented at some point, and the introduction of bundles and busses looked like it might be part of the same roadmap. Unfortunately, with NI under different ownership now, it seems Reaktor is on a maintenance only plan, with no chance of any significant new functionality for the foreseeable future.

So best just to get on with it and use the existing feature set. It's still very powerful ;-)