Migrating to graph-based execution order

#1

I've been thinking about this a little more. To be honest, I don't like how it's done right now, as it is really unintuitive.

  • Depending on the patch, you can get all kinds of weird phasing issues (including the one with my reverb, that initially started this thread). The biggest problem to me is that shifting objects around without changing any of the cables can actually drastically alter the sound (which you just wouldn't expect to happen!). You might find your patch doesn't work anymore after "cleaning" it up.
  • Everytime a patch cable goes up/left it will create a 16-sample/1-block delay (z^-16). You can get quite a significant overall delay with this and there is currently no indication that this happens. Not only does it create 0,33ms delay per cable, it also eats up significant amounts of memory for larger patches (64 bytes per cable).

One possible short-term solution could be to allow users to see and manually specify the processing order. The GUI could display a number indicating the order of execution in the top right corner of each object. With a right-click, the user could move the object up/down in the processing tree. All of this could be hidden by default and enabled upon request (e.g. by adding a menu option "show processing order" in the titel menu of the window that the user can tick to enable this).

In the long term, I think it would be best to apply some graph theory to this. What we really want is to do a topological sort of the graph. This, however requires the graph to be a directed acyclic graph which is almost certainly not applying here. IMO it would be best to identify the bottlenecks in the graph (portions of the directed graph that have the least parallel edges) and insert the z^-16 delay there but I'm not entirely sure what algorithm to choose for this. In Native Instruments Reaktor, unit delays are added whenever the user adds a connection that creates feedback. The delay is indicated by a little z symbol next to the input of the node where the feedback path ends.

This could be translated to the axoloti patcher as well, but it would require to somehow convert existing patches and that leaves us with the same problem of not knowing where to add the delays.

The JUCE class juce::AudioProcessorGraph does the same thing. It builds up a ordered graph and inserts unit delays on the feedback edges. It also does latency compensation, which would be super neat as well. It defines rendering operations (clear buffer, copy buffer, delay buffer, execute node, etc.) and then iterates over the nodes in the graph and builds up a list of rendering operations that define which node to execute when, which buffers can be used multiple times and where to insert delays to compensate for processing latency of the nodes or to allow feedback. The order of processing is updated with this function, the details about the sorting are in this function.

I know, this is a lot to ask, and those are some pretty substantial changes, but the overall positive effect could be very significant.

Processing order issue?
#2

Agreed
and it's going to change , as you say it's not simple, and we also need to ensure old patches are unaffected - so it cannot be rushed in.

#3

I'm skimming the web for what might be useful for this. I found JGraphT, a Java-Graph library. I don't know if the patcher is currently using this, but it might offer some good tools for sorting, iterating and converting the graph.
I think the hardest part is identifying which edges in the graph represent a feedback path == where to insert the z^-16 delays. Here, the x,y position of the objects could indeed be a good indication of where the user thinks the feedback is.

#4

@lis0r has already kindly produced an implementation which we have merged into a branch.
you can also see some comments on the PR here

current thoughts are to use a graph, and then allow the user to 'override' execution order specifically.
(this will also allow the user to explicitly see execution order too, which helps alot)

there are quite a few 'edge cases' , and things that need to be considered.. e
.g. currently things like tables often 'imply' an order of execution requirement, but these are not coded as connections currently.
(Im also familar with Reaktor, and even that has issues, e.g. the 'mess' around initialisation)

anyway, we cannot rush into this.. the current model has its flaws, but most users know how to use it and you can patch accordingly (I have for, nearly 2 years now :wink:) ... so there we can replace this with a 'half backed' solution, or one that means users have to rewrite existing patches. it has to be done properly.

so I dont really think its how to do it, or even if/when, so much as as 'development time', johannes is already busy on things for the next release, and so I am - so this has to join the queue, of course, if other developers what to contribute that will speed things along, which is why pull requests are so welcome.

#5

Ah, I see. Good to know this is going to happen someday. I fixed my patches now by shifting the objects around. It works now, but it looks really messy, so any future improvements are very welcome. I considered actually making my own branch and trying to implement the graph sorting, etc. but while I'm fluent with C/C++, I'm not very experienced with Java so I'm probably the wrong person to tackle this.

Just to be clear: I'm really enjoying the axoloti platform, so any criticism is meant positively. I very much appreciate the time that went into making axoloti what it is and I'm hoping to be able to contribute something aswell.

#6

can you PM me, I did put in the changes you made in your last PR (i.e. the changes you made to Patch.java that were UI unrelated)... you can check if its correct, its on the experimental branch, and its now in PatchModel.java)
also Id really love to hear any ideas you have for taking this forward.
thanks again
Mark

#7

I know that this was addressed towards @lis0r, but I would really suggest taking a look at the JUCE class from my previous post. It is very readable and does exactly what we want (+latency compensation as well! which is super handy to have), only in C++. JUCE is available under the GPL, so converting the code to Java straight away should actually be possible, even from a licensing standpoint.

#8

I personally don't find those JUCE functions at all readable - hey mostly seem to be driver functions, palming off the real guts of the algorithm onto other methods and constructors. Then again, I think C++ is an abomination that should be abandoned in a ditch, doused in diesel, and set on fire, so I would say that!

It also seems over complex - axoloti buffers are a fixed size, and it's easy to locate the needs where feedback paths originate, so it should be pretty simple to insert a fixed delay. I just can't quite get my head round which part of the path the have to be placed on to make it work. Intuitively, it feels like the non-feedback path should get the delay, in order to sync up with the feedback, but I have a head full of DeviceTree details right now, and can't flush the caches to think about it properly.

I'd also worry that the memory and latency overheads might surprise the user. It's not like we have the same resources as a PC to throw at this.

Lisa

#9

The actual graph re-organization happens on the PC, not on the axoloti. And a properly organized graph with only a few z^-16 delays is actually mroe memory and CPU efficient than the current, unoptimized version. I'm not talking about latency compensation here, that would of course add additional buffers. But only, if objects actually specify a latency, so right now, it would simply create zero overhead. For some stuff, latency compensation is acutally pretty vital.

Do you think so? I'd say that is actually the main problem. Sorting a acyclic gaph of processing nodes is not a problem. The problem is to find out where in the cyclic graph the delays should be inserted in order to turn it into an acyclic graph. When you have feedback somewhere in the graph, that means there is one/more loops. Detecting the loops is easy, when you iterate over the graph and put a mark on already visited nodes. But how do you know where to actually put the delay in? Lets consider this (stupid) patch:

Audio In |---------->| Compressor   |--------------+-------->| Audio out
                 +-->| Sidechain in |              |
                 |                                 |
                 +---| EQ |<----| Echo Delay |<----+

Where would you put the z^-16 delay? I would say: preserve the direct audio path and put the delay in the feedback loop. But to an algorithm that patch is just a cyclic graph of 5 nodes connected by 5 edges and none of them has any property to it that makes the position of the z^-16 delay obvious. The delay could be added right on the compressor output - that would split the loop as well, but it would delay the audio output uneccesarily and hence it is not desireable from the users view.

My idea would be to identify loops and take the graphical direction and the length of the wires in the patcher as a guide to where to place the delay. That is a good chance of actually inserting it into the "true" feedback path.

#10

The current implementation of graph-ordered execution ordering happens PC side. It doesn't latency compensate - pretty difficult to be less resource intensive than not doing something!

The system already works out which objects need feedback, since it stores a 16 (I think) sample buffer between iterations, that gets used as input for the next block.

This means feedback paths are are inherently delayed by 16 samples. I see no way of compensating for that without putting an additional delay on the non-fed back path to synchronise them. That, or redesign the axoloti firmware from the ground up, I guess?

#11

You are referring to the current system? Yes, it does that, but it fails for the xfade axample at the beginning of this thread and it inserts delays where they aren't neccessary.

The left version creates an additional 16 sample delay between the input and the output, even though that's not neccessary. The right version does not.

Delays are only neccessary to split the cyclic processign graph into an acyclic processing graph.

#12

I'm talking about the experimental branch, with my graph-ordering patch.

#13

I'd like to move towards graph-ordering, my key concerns are:

  • Being able to migrate patches from position-based execution order to graph-based execution order without a patch-setting switch (that 'd add a parallel universe but not migrate, and is a potential source of user confusion), and without changing the behavior of old patches.
  • Being able to explicitly specify execution order. Object benchmarking via patch/cyclecounter is one example where this is useful.

I think it can be addressed by adding a "object instance reference" inlet and outlet on every object (in the title bar of the object). A connection of this type from one object to another would express fixing their execution order.
For the algorithm sorting the object order, I think we need to introduce "net class priorities":

  • highest sorting priority for the "object instance reference connections"
  • high sorting priority for the audio connections, k-rate connections
  • (perhaps in the future, low sorting priority for midi connections)

A "brute" way to migrate old patches is by adding "object instance reference connections" to every object in position order when opening (but possibly redundant connections could be removed).

Thoughts?

#14

Those "object reference connections" are IMO the best way to specify extection order and deal with references to delays, etc. The currently used text entry fields for object references would of course have to be removed. That is what reaktor does for its arrays and it is a tidy concept. More importantly, users will stumble across those connections and start wondering what they do. Effectively that will introduce them to the whole execution order topic at a point where they are ready to understand it. It saves you from over-complicating the first steps with axoloti (you don't even have to mention it). They will eventually stumble unpon the topic when they need it.

Yes, I think that is pretty much the only way to convert patches to the new system without breaking them. IMO is very important to remove redundant connections and keep them only where they actually make a difference. Otherwise, patches will be extremely messy after the conversion.

Nevertheless, there is a need to explain to users why their patches suddenly contain those magical, new connections that apparently don't do anything but are needed for a reason that most users won't be able to understand immediately. I guess that is un-avoidable. I guess what I'm trying to say is, it is important to have a well structured tutorial at hand. I would even add a little popup message to the patcher that says: Hey, your new version of the patcher intruduces a new type of object connection. Click here to open an example patch. Or: Click here for more information (link leading to a forum post, etc.)
This mesage would only appear to users upgrading their patcher. Fresh installs should not show this, as to not over complicate things at the start.

#15

Whilst it's 'neat' to represent the ordering as connections ( possibly ok internally) ,
it'll make the UI overly fussy. also it's mixing metaphors , which tends to lead to confusion.

If they are used, I think they should be on a different layer, a different view. But this breaks your screenshot ideal.

schemes used by others :
- numbers on title bar ( toggled on/off) - Reaktor
- ordering objects (trigger) - max

#16

If I undestand johannes correctly, that won't happen. The new connection will only be needed for two use cases:

  1. To "transport" references from one object to another, e.g. a delayline read object needs a reference to a delayline write object - this reference is right now defined by entering the name of the write object into the read object. In the future, the "object instance reference connection" could define this relation, where the reader reads from the writer it is patched to via its "object instance reference" terminals (the details of that should be
  2. To overwrite the execution order that would otherwise be defined by the audio and modulation connections in the processing graph.

With this in mind, most patches won't need any "object instance reference connections" at all and would look exactly like they look right now.

#17

I think I understand what the idea is, and yes the idea is these execution order wires are not really need most of the time.

But given there is little 'cable management' in Axoloti it's already an untidy mess with complex patches, adding more is not going to help this :wink:

Also as I said execution order wiring is a mixed metaphor, it's not a data wire - and besides things like trigger/order objects and the numeric numbering I think are more obvious/explicit.
(They also have an established presence in some other environments)

I've no issue with object ref wiring e.g. for tables , also midi wiring make sense , as they are linking data together
( I think things like tables should be presented as conventional inlets/outlets , so it's possible for example to have an object with 2 table outlets)

#18

Execution order number on the title bar: I think it is hard to define the renumbering behavior when coping one patch into another, and hard to keep an overview. As a read-only indicator certainly useful when implementing and debugging graph-based sorting, could be kept as a diagnostic option.

Max/pd has distinctly different semantics for audio wires and event message-wires.
The trigger approach in Max/pd for event message-wires does not adapt well to simple lfo's/envelopes. Bang~'ing messages can easily lead to unintentional event doubling.
Max/pd audio wiring is strict graph-based. I vaguely recall an example in Pd how to force an alternate execution order, I think it was for a thru-zero flanger, using dummy audio wires to/from a subpatch, with a delayread in the subpatch, not extremely elegant.

In terms of cable mess: hiding certain cable type(s) is already implemented, could hide the "object reference" cables, turn on the "show execution order index", and then the only thing missing compared to a pure "execution order index label"-based approach is a way to manipulate execution order that does not involve wires.

Sure, such a change needs to align with a major release, like "2.0".

#19

Thinking about this a little more...
If I understand johannes correctly, that new connection is supposed to serve two tasks: A) transmitting references B) Allowing to overwrite execution orders. I wonder if it is clever to use a single connection type for both, as B) imposes restrictions and odd problems for A) that can only be solved by adding additional rules (which is not ideal). Sometimes A) and B) can even be conflicting.

Lets consider a reader/writer relation between objects (like the delayline read/write objects - basically it's a supply/use relation that applies to all object references, like tables, memory, etc.). The reader reads from a writer that's patched on the same net via object instance reference connections. Lets imagine the bool connection in the following screenshots is the proposed object instance reference connection.

In this first patch, the the transmission of the reference from the writer to the reader is simple.

In the second patch, we have two readers reading from the same writer. As they are parallel, it is undefined which one is executed first. But they are always executed after the writer.

If it is important that one reader is executed before the other, we could do this: There is just one writer on the net, so both readers know where to read from.

Lets consider this patch: B) requires each object to have a object instance reference input and an object instance reference output. However, that means we can have two writers on the same net like on this patch here:

How does the reader know which writer to read from? The problem can be resolved by adding a new rule: A reader reads from the writer patched upstream. (but I think additional rules are always uncool and make things more complicated)

Now we come to the next weird case: Here, each reader will find two writers upstream. We will have modify the rule so that each reader reads from the first writer upstream. Now both readers will read from writer2.

If we want to have reader 1 reading from writer 1 and reader 2 reading from writer 2, we have to choose this topology:

Now it is undefined, if reader1 or reader2 is executed first. Reader 1 could even be executed before writer2. As we can see from the last two examples, it is not possible to have all execution orders and still correctly transmit all object references. This is a case, where A) and B) conflict each other.

Also: What would you do, if you want to have the reader executed before its corresponding writer?

I think this can only be solved by separating the reference transmission (A) and the ordering (B) into two different wires. Why would they be on the same wire after all? A) and B) are two very different things. Here's my proposal:

Order wire

Each object has an order input and an order output in its title bar. Order wires are patched bewteen those terminals to define the execution order. Upstream objects are executed first. Order wires can be split (one output can be routed to two inputs) and merged (two outputs can be patched to one single input). That way, all possible execution orders can be realized.

resource wire

A resource wire is a wire like any other (bool, srate frac, krate frac, ...). Objects can have outputs if they define a resource (e.g. a table or a memory block). Objects can have inputs to make use of a resource. Now it is possible to have a single object define or use mutiple resources.
Resource wires (or reference wires if that sounds better) can be split (one output to two inputs) but not merged. Just like all other wires we have right now.
Resource wires don't have a datatype. Internally, a resource wire could simply be the string of the C++ instance defining the resource, just like we have now for tables and delaylines.

hierarchy

The hierarchy that defines the execution order would be like this (lower index = higher priority).

  1. order wire
  2. conventional wire (bool int, frac, audio, resource, etc.)
  3. maybe midi wires?

If 1 is not present, 2 defines the order. And so on.
The final execution order is defined by this rule: An object is executed once all upstream objects are already executed.

#20

I know from a technical standpoint this topic is way out of my depth, however one of things I have found when adding and or coding objects for a patch, that you end up with a mix of objects in your patch where some that have a large scale influence on a patch, and some only a small scale influence. Yet be it all are needed. Would it not be easier to have something that is a bit like a subpatch setup in the patching screen that creates blocks around objects, all the objects in the block are executed in the current way but only within the block, then when it gets to the last object of the block, it goes to the next block that exists in the current order setup. Kind of like a patch of say 5 subpatches, each subpatch is subject to the current standard processing order, but within the subpatch, it has its own order. But instead without subpatches, but creating blocks to contain the objects. This way the blocks can contain as many or as few objects as you want. You may even want blocks in blocks etc.. I guess the idea is that there is something nice about the current setup, but can get a bit messy. !:grin: