How to Dig8 implements expression operations?

Read this, it explains it better than I can

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

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.