Node Tree Development

Development
1

(@muellmusik, @simon)

So as I see it now, we have three things to do:

  • querying the server for node tree info
  • translating node messages to a better representation
  • displaying the node tree

And looking at this, there are related functionalities lurking:

  • documenting node state
  • reproducing node trees
  • optimising repeated queries

And we have found a basic issue that constrains the possibilities a little:

  • query messages are global, there is no simple way to distingush “who asked”. This is further complicated by the fact that in principle you can query different parts of the tree, but you need to have the authority over the message reception to avoid confusion (if different processes ask for different things at the same time, it is chaos). There is a way to make messages unique, but this has some overhead itself.
  • building a dictionary tree representation is a lot of object allocation overhead

We need to decide:

  • do we want the tree view to be optimized in terms of overhead or do we not want to care so much?
  • do we want to make possible already now future implementations of the “related funcctionalities” above?
  • do we want to make the queries unique (with id) and accept the overhead that this implies?
4 Likes
2

The related functionalities question is interesting. I guess there are certain classes of problems, e.g. reproducing trees, that don’t really have a standard solution. There may be some that we haven’t anticipated.

A good question is: Do we imagine common cases with many and frequent node tree queries? If so performance could be a higher priority. Currently it seems mostly useful for monitoring/debugging (imperfectly perhaps since it’s not synchronous), and probably not commonly used.

Considering some of the tangible proposals:

  • Caching the last received node state for synchronous query is possible, but I think this makes most sense when regularly querying, and perhaps should be optional. I would suggest doing this as part of a NodeTreeTracker object along the lines Julian suggested on GH. We have to consider how to deal with the case where the group being queried is freed. Is the cache set to nil to indicate this?
  • Adding a query ID to g_queryTree seems relatively low rent, however to do this without potentially breaking code, we would need to add it at the end of the g_queryTree.reply message. This is very inelegant as the tree size can vary, so you’d need to do some work just to figure out which element is the query ID.
    • That said, if we went the breakage route, we could consider adding other information? e.g. a timestamp indicating when this tree representation was accurate?

Given the above, I think I come back to the same design principle we’ve generally employed, i.e. that server cmds are low level and do minimal if any bookkeeping. This allows flexibility for alternative clients. In sclang bookkeeping gets built into abstraction classes as part of a larger if modular system that users are encouraged to buy into.

In this case I think that looks like some set of NodeTreeTracker objects. We could have a ‘singleton’ approach for each group ID. This would avoid duplicate queries. If we ensure that this approach is deployed consistently within Common it’s fine. This is in keeping with the approach taken with node/buffer/bus allocators, etc. Either you buy into the system and it’s managed for you, or you’re working on your own at OSC level, and you’re responsible.

3

Although… it occurs to me that replies already are identified by group ID. Does it matter if your reply comes from a query to the same group that was made very slightly earlier? As most queries are about knowing the state ‘now’ (for some plausible idea of now), it could be even better to get a faster reply?

4

Yes, this was also my impression – this is why I thought that a NodeTree class could cache the most recent one. Maybe it could also save a time when it has received it and then decide if it needs an update or just returns the existing one.

1 Like
5

Since you bring debugging, the old NodeWatcher from the crucial quark has some worthwhile patterns.

DebugNodeWatcher provided detailed logging of node activities (every n_go n_end n_off n_on). That could be difficult to read, but AnnotatedDebugNodeWatcher allowed appending “annotations” for nodes, which would make sense for debugging. It’s just a lovely way to add metadata.

Also, the basic tracking (BasicNodeWatcher) and full version (NodeWatcher) can hint at some questions there. It seems that the model that may be adopted is closer to BasicNodeWatcher (simple IdentitySet as representation, only handle /n_go and /n_end, has minimal state (or stateless?), it’s just a set of active nodes with no registration system.

But, from what I remember, the overhead was not so heavy if you don’t need a minimal refresh rate. I believe the quark is not functional right now. Still, from what I remember using it, we can probably optimize more aggressively since the exact query-response [EDIT: with more information about each node, as seems to be the idea here, too] was done without compromising the system and with computers from ten or more years ago.

6

Yes I was thinking of Nodewatcher. It was added to Common actually. I guess there’s a broader question of monitoring Server state that could be considered.

7

But why would this be a problem? Implementing a more straightforward state representation with a cache system eliminates the need for tree “rebuilds” (being a dictionary or not) on every update.

Besides, there are a few representations that could be used. For example, parent vector representation has “instantaneous” efficiency O(1) to find a node’s parent (not children).

Level-order representation can be used for efficient visual representation (it fits well with a GUI construction). I assume it is quick (I don’t see a reason not to be).

just an idea (and apologies because I haven’t been following the discussion from the start, I may be repeating things )

8

The server has some caching going on, but it targets control buses. The class has some caching (the “flat” representation, which is cheap) and manages targets at node tree information. Using Dictionary to test efficiency and memory with more frequent updates

(This is just a sketch for me (at least), it may be helpful to isolate it for testing ideas)

EDIT:
A version with a possible idea for optimization can be found below

NodeArrayCache {
    var <rawCache, <lastUpdate, <updateInterval;
    var server, updateFunc;
    var <>onUpdate;

    *new { |server|
        ^super.new.init(server);
    }

    init { |inServer|
        server = inServer ? Server.default;
        rawCache = nil;
        lastUpdate = 0;
        updateInterval = 1;

        updateFunc = OSCFunc({ |msg|
            rawCache = msg;
            lastUpdate = Main.elapsedTime;
            onUpdate.value(msg);
            "Cache updated at %\n".postf(lastUpdate);
        }, '/g_queryTree.reply', server.addr);
    }

    setUpdateInterval { |interval|
        updateInterval = interval;
    }

    forceUpdate { |action|
        lastUpdate = 0;
        this.update(action);
    }

    updateOnNodeChange { |node|
        if(node.isKindOf(Node)) {
            this.forceUpdate({ |cache|
                "Cache updated due to node % change\n".postf(node.nodeID);
            });
        };
    }

    watchNode { |node|
        if(node.isKindOf(Node)) {
            node.onFree({
                this.updateOnNodeChange(node);
            });
        };
    }

    update { |action|
        var now = Main.elapsedTime;

        if((now - lastUpdate) >= updateInterval) {
            server.queryAllNodes(true, { |msg|
                rawCache = msg;
                lastUpdate = now;
                onUpdate.value(msg);
                action.value(msg);
            });
        } {
            action.value(rawCache);
        };
    }

    startPeriodicUpdate { |interval|
        var routine;
        this.setUpdateInterval(interval);

        routine = Routine({
            loop {
                this.forceUpdate;
                interval.wait;
            };
        }).play;

        ^routine;
    }

    findNode { |nodeID, action|
        this.update({ |cache|
            var i = 2;
            var result, searchFunc;

            if(cache.isNil) {
                "Cache is empty".warn;
                ^action.value(nil);
            };

            searchFunc = { |numChildren|
                var found = nil;

                numChildren.do {
                    var currentID = cache[i];
                    var isGroup = cache[i + 1] >= 0;

                    if(currentID == nodeID) {
                        found = this.extractNodeInfo(i);
                        ^found;
                    };

                    if(isGroup) {
                        var children = cache[i + 1];
                        i = i + 2;
                        if(children > 0) {
                            found = searchFunc.value(children);
                            if(found.notNil) { ^found };
                        };
                    } {
                        var numControls = cache[i + 3];
                        i = i + 4 + (numControls * 2);
                    };
                };
                ^found;
            };

            result = searchFunc.value(cache[3]);
            action.value(result);
        });
    }

    extractNodeInfo { |index|

        var nodeID, typeFlag, isGroup;

        if(rawCache.isNil) { ^nil };

        nodeID = rawCache[index];
        typeFlag = rawCache[index + 1];
        isGroup = typeFlag >= 0;

        ^if(isGroup) {
            (
                \type: \group,
                \id: nodeID,
                \numChildren: typeFlag
            )
        } {
            var defName = rawCache[index + 2];
            var numControls = rawCache[index + 3];
            var controls = Dictionary.new;

            if(numControls > 0) {
                numControls.do { |i|
                    var ctlIndex = index + 4 + (i * 2);
                    controls[rawCache[ctlIndex]] = rawCache[ctlIndex + 1];
                };
            };

            (
                \type: \synth,
                \id: nodeID,
                \defName: defName,
                \controls: controls
            )
        };
    }

    getGroupChildren { |groupID, action|
        this.update({ |cache|
            var searchFunc;
            var i = 2;
            var children = List.new;

            if(cache.isNil) {
                "Cache is empty".warn;
                ^action.value([]);
            };

            searchFunc = { |numChildren|
                var found = false;

                numChildren.do {
                    var currentID = cache[i];
                    var isGroup = cache[i + 1] >= 0;

                    if(found) {
                        children.add(this.extractNodeInfo(i));
                    };

                    if(currentID == groupID) {
                        found = true;
                    };

                    if(isGroup) {
                        var numKids = cache[i + 1];
                        i = i + 2;
                        if(numKids > 0) { searchFunc.value(numKids) };
                    } {
                        var numControls = cache[i + 3];
                        i = i + 4 + (numControls * 2);
                    };
                };
            };

            searchFunc.value(cache[3]);
            action.value(children);
        });
    }

    invalidate {
        rawCache = nil;
        lastUpdate = 0;
    }

    free {
        updateFunc.free;
    }

    printCache {
        if(rawCache.notNil) {
            "Raw Cache Contents:".postln;
            rawCache.postln;
        } {
            "Cache is empty".postln;
        };
    }
}

version with some attempts at optimization

NodeArrayCache {
    var <rawCache, <lastUpdate, <updateInterval;
    var server, updateFunc;
    var <>onUpdate;
    
    var nodeCache, groupCache, pathCache;
    var nodeInfoPool; 
    
    *new { |server|
        ^super.new.init(server);
    }
    
    init { |inServer|
        server = inServer ? Server.default;

        nodeInfoPool = Array.fill(32, { Event.new });
        this.clearCaches;
        lastUpdate = 0;
        updateInterval = 1;
        
        updateFunc = OSCFunc({ |msg|
            this.processNodeTree(msg);
            onUpdate.value(msg);
            "Cache updated at %\n".postf(lastUpdate);
        }, '/g_queryTree.reply', server.addr);
    }
    
    getNodeInfo {
        ^(nodeInfoPool ?? { () })
    }
    
    recycleNodeInfo { |info|
        if(nodeInfoPool.size < 64) { 
            nodeInfoPool = nodeInfoPool.add(info.clear);
        }
    }
    
    clearCaches {
        rawCache = nil;
        nodeCache = IdentityDictionary.new;
        groupCache = IdentityDictionary.new;
        pathCache = IdentityDictionary.new;
    }
    
    processNodeTree { |msg|
        rawCache = msg;
        lastUpdate = Main.elapsedTime;
        
        nodeCache.do { |info| this.recycleNodeInfo(info) };
        
        nodeCache.clear;
        groupCache.clear;
        pathCache.clear;
        
        this.prBuildCaches(msg[3], 2, [1]);
    }
    
    prBuildCaches { |numChildren, index, path|
        var nextIndex = index;
        
        numChildren.do {
            var nodeID = rawCache[nextIndex];
            var typeFlag = rawCache[nextIndex + 1];
            var isGroup = typeFlag >= 0;
            var nodeInfo;
            
            nodeInfo = this.extractNodeInfo(nextIndex);
            nodeCache[nodeID] = nodeInfo;
            pathCache[nodeID] = path;
            
            path.last.notNil.if {
                groupCache[path.last] = groupCache[path.last] ?? { IdentitySet[] };
                groupCache[path.last].add(nodeID);
            };
            
            if(isGroup) {
                var numKids = typeFlag;
                nextIndex = nextIndex + 2;
                
                if(numKids > 0) {
                    nextIndex = this.prBuildCaches(
                        numKids,
                        nextIndex,
                        path ++ [nodeID]
                    );
                };
            } {
                var numControls = rawCache[nextIndex + 3];
                nextIndex = nextIndex + 4 + (numControls * 2);
            };
        };
        
        ^nextIndex;
    }
    
    extractNodeInfo { |index|
        var nodeID, typeFlag, isGroup;
        var info;
        
        if(rawCache.isNil) { ^nil };
        
        info = this.getNodeInfo;
        
        nodeID = rawCache[index];
        typeFlag = rawCache[index + 1];
        isGroup = typeFlag >= 0;
        
        if(isGroup) {
            info.put(\type, \group)
            .put(\id, nodeID)
            .put(\numChildren, typeFlag);
        } {
            var defName = rawCache[index + 2];
            var numControls = rawCache[index + 3];
            var controls = Dictionary.new(numControls); 
            
            if(numControls > 0) {
                numControls.do { |i|
                    var ctlIndex = index + 4 + (i * 2);
                    controls[rawCache[ctlIndex]] = rawCache[ctlIndex + 1];
                };
            };
            
            info.put(\type, \synth)
            .put(\id, nodeID)
            .put(\defName, defName)
            .put(\controls, controls);
        };
        
        ^info;
    }
    
    findNode { |nodeID, action|
        this.update({ |cache|
            action.value(nodeCache[nodeID]);
        });
    }
    
    getGroupChildren { |groupID, action|
        this.update({ |cache|
            var children = groupCache[groupID];
            action.value(
                if(children.notNil) {
                    children.asArray.collect { |id| nodeCache[id] }
                } {
                    []
                }
            );
        });
    }
    
    setUpdateInterval { |interval|
        updateInterval = interval;
    }
    
    forceUpdate { |action|
        lastUpdate = 0;
        this.update(action);
    }
    
    updateOnNodeChange { |node|
        if(node.isKindOf(Node)) {
            this.forceUpdate({ |cache|
                "Cache updated due to node % change\n".postf(node.nodeID);
            });
        };
    }
    
    watchNode { |node|
        if(node.isKindOf(Node)) {
            node.onFree({
                this.updateOnNodeChange(node);
            });
        };
    }
    
    update { |action|
        var now = Main.elapsedTime;
        
        if((now - lastUpdate) >= updateInterval) {
            server.queryAllNodes(true, { |msg|
                this.processNodeTree(msg);
                action.value(rawCache);
            });
        } {
            action.value(rawCache);
        };
    }
    
    getNodePath { |nodeID, action|
        this.update({ |cache|
            action.value(pathCache[nodeID]);
        });
    }
    
    startPeriodicUpdate { |interval|
        var routine;
        this.setUpdateInterval(interval);
        
        routine = Routine({
            loop {
                this.forceUpdate;
                interval.wait;
            };
        }).play;
        
        ^routine;
    }
    
    invalidate {
        this.clearCaches;
        lastUpdate = 0;
    }
    
    free {
        updateFunc.free;
        nodeInfoPool = nil;
    }
    
    printCache {
        if(rawCache.notNil) {
            "Raw Cache Contents:".postln;
            rawCache.postln;
        } {
            "Cache is empty".postln;
        };
    }
}

quick test

~cache = NodeArrayCache(s);

~cache.onUpdate = { |msg|
    "Cache updated with % nodes".postf(msg[3]);
};

g = Group.new;
x = Synth(\default, [\freq, 440]);
y = Synth(\default, [\freq, 880]);

~cache.findNode(x.nodeID, { |info|
    "Synth info:".postln;
    info.postln;
});

~cache.getGroupChildren(g.nodeID, { |children|
    "Group children:".postln;
    children.do(_.postln);
});

~updateRoutine = ~cache.startPeriodicUpdate(0.1);  // Test with 0.1 refresh rate

~updateRoutine.stop;

~cache.free;
9

A couple of notes -

On optimization: NodeSnapshot (NodeSnapshot.quark/NodeSnapshot.sc at master · scztt/NodeSnapshot.quark · GitHub) does basically all of this, and is implemented without any deep optimization or caching. I’ve used this for many years and do not see meaningful performance problems around parsing / processing the node tree, so this may be very low priority in terms of optimization unless you’re looking to update at much more than 1 time / second (iirc the quark runs at 2 updates / second)?

Something to keep in mind here, though: the current scsynth server implementation limits the size of the node tree dump that can be sent back, as it has to be sent in a single OSC message. This is a huge functional limitation for this - basically you stop being able to get any tree information once you graph gets to a certain size. It’s pretty easy to hit the wall on this, especially when you have synths with many voices and a lot of controls.

These two pieces of info in combination: you will reach the maximum tree size and everything will stop working BEFORE you reach a point where performance is meaningfully bad…

(I should amend: “you are LIKELY to …” - there maybe bad edge cases buried, but only based on my experience with complex graphs, I hit the message size limit long before I see performance problems.)

3 Likes
10

I tried another version with simpler direct object creation/deletion in incremental updates. It never uses /g_queryTree.reply, just /n_go and /n_end messages.
The timing of this communication is so problematic that I think it will not fit the context with rapid changes. I haven’t tested or benched it for real (and I think it’s incomplete code yet), just basic stuff.

Can this work , you think?

11

It would be worth checking exactly how responses like these are send back from the server. The danger with piecemeal updates (e.g. the /n_... messages) is that you end up with fragmented, unsynchronized state spread around. Meaning, if you don’t have a HARD guarantee that e.g. all your server state information was sent at time T, then you might end up with e.g. one bit of data that shows synth A as a part of group G1, and another bit of data where it’s a part of group G2 - you can imagine the kinds of bugs this could create…

Even if server information is sent back to the language with a hard, guaranteed timestamp - if you are receiving updates piecemeal, you would still be responsible for reconciling all these timestamps yourself on the language side, which is not so trivial to do. E.g. at time=1.0, Synth1 is in Group1 - at time=1.00001 Synth1 is in Group2. Synchronizing state is a bit complex here! At a minimum youd need to update the representation of both groups.

Ofc this doesn’t matter in all use-cases, especially for basic UI / debugging views - but it’s easy to imagine the horror-show kinda of bugs that would come up if a user was casually tracking separate parts of the graph and assuming it would “just work”, and these states were SLIGHTLY out of sync…

1 Like
12

I tried using timestamps; I knew the timing problem. I did some elementary testing (just running quasi-granular things in 3 groups). It seems it didn’t mess up at first glance, but I would need to check all messages; at least, each group stayed with the same number of “grains” and other hints that it worked.

13

Probably its useful to hold on to the actual use-cases here. For the granular example (I’m assuming you mean granular where each grain is a synth, vs using like TGrains): any “tree view” ui representation of this will be totally broken anyway, as it will just show a list of hundreds or thousands of anonymous grain synths. Displaying debug information for this kind of case would (I imagine…) just need to be a totally separate thing, and probably doesn’t easily overlap with a standard “tree view” visualization. With the NodeSnapshot quark, I have to add SynthDefs that i will play many copies of to the ignore list so they wont be displayed, else it makes the whole debugging view useless.

1 Like
14

Some automatic pattern recognition could help debug/visualization in cases like the one you mentioned.

I saw many comments here targeted at performance concerns. But, as you said, depending on the use case, there seems to be no general tool for everything.

EDIT:

Just for completeness and clarity about what changed.

Second version (not the "piece meal one, just the safe one with changes):

  • The 1st version uses recursion through the raw cache in findNode and getGroupChildren
  • New version builds structured caches upfront (\ processNodeTree and prBuildCaches) and then provides direct lookups
  • Added path-tracking with getNodePath

Different cache objects (updated in the same pass)

  • nodeCache: Stores information on nodes
  • groupCache: same on groups
  • pathCache: keep the path to each node

Event pool:

  • nodeInfoPool: a pool of reusable Event objects The user could modify the size, so it adjusts it for minimal memory usage (I remember memory was raised as an issue here) for their maximum simultaneous nodes.

QUESTION: Tested with refresh rate = 0.1s, no problems, no increment in CPU. Isn’t there a case where one would prefer 0.1 instead of 1 or 0.5s as a refresh?

1 Like
16

Maybe some automatic pattern recognition could show something like this, showing all instances as one?

Root Node
├── Group 1
│   ├── Synth 1 (freq: 440, amp: 0.5) 🔵
│   ├── Synth 2 (freq: 880, amp: 0.8) 🔵
│   └── Group 2
│       ├── Granular Synths (100 instances)
│       ├── Synth 3 (freq: 330, amp: 0.6) 🔵
│       └── Synth 4 (freq: 220, amp: 0.3) 🔵
└── Group 3

if not pattern recognition, could also be something like

    markAsGrainGroup { |groupID|
        grainGroups.add(groupID);
        grainStats[groupID] = (
        // etc
        );
    }

Annotations and validations, as well as other features in your code, could be adapted for use in the class with optimizations

18

Just a note, as far as I know, the CPU measure doesn’t directly give you indication of load in memory allocation and garbage collector work.

But good that it is not too costly.

19

Do you think the Event/object pool can make a difference in memory (in sclang)? Is it worth it?

20

Probably it would make some difference. But also, it may increase complexity, so perhaps just rebuilding not so often and on demand is a better solution.

I think we don’t have the aim to provide a manipulable representation of the present server state, but something to analyse and display what was happening in the near past. And perhaps, rebuilding a past tree again.

2 Likes
21

Yes, it follows and respects the design. If this were an essential feature, the entire project’s design would be different.

But it’s good to consider other approaches to “the big picture.”

EDIT: the ideas in the code reduce the cost (computation and memory), thus if that is more important in another situation, things like those can be used

22

But the optimizations do not prevent this. The visual display will remain the same, and there is an advantage: you can log the raw array more quickly (since the system is less expensive).

I don’t understand the point since you see the same thing in the GUI, and you will have better logging.

Keeping the code simple is good; there is just one place to look for bugs (the recursion). Instead of saying there will be no debug possibilities with those changes in the second version.