Node Tree Development

smoge · December 14, 2024, 2:22pm

As a simple incremental enhancement, I would propose a hybrid approach based on NodeArrayCache and the classes on github ( ServerNodeTree etc). They are perfectly compatible, and it would be possible to polish a hybrid approach that would be useful for different situations.

github.com/supercollider/supercollider

Comment by smoge - ClassLib: ServerPlusGUI: plotTreeView rework

supercollider:develop ← SimonDeplat:topic/plotTree-rework

> Yes, I hope there can be some good ideas that go into a harmonized system. @pr…ko, would you want to join for review? You have already put some time into it, I am sure there are some things you notice. Also, @SimonDeplat, it would be good if you could integrate some of the ideas that @smoge posted, whatever seems simple enough as a first step. > > All in all, I would propose that we find good overall distribution of classes for the task, then make a minimal implementation that can be merged. In a second step, there can be extensions and improvements to it, as have been mentioned. @telephon thanks! I recently tested different implementations, comparing the straightforward approach to the modified version discussed in the forum (a sketch more than a final version). My results differed from some assumptions there. Notably, the changes prove most beneficial with update intervals of 0.5 seconds or longer, not necessarily for ever-lower refresh rates. It shows promise in systems with 20 or more nodes that run for extended periods. Adding a cache refresh check (using updateInterval combined with (not implemented) hash verification) would yield performance gains in some scenarios. The main advantages are that node query complexity reduces from O(n) to O(1) (direct lookup for any query), and the memory handling improves by reusing objects rather than constantly creating and freeing them. While the standard implementation remains suitable for most use cases 90% of the time, the remaining 10% would involve larger node trees (20+ nodes), unpredictable changes, and extended runtime (things that run for long) would see some benefit. The last one is because it provides better memory safety and reduces stress on garbage collection since there is less creation/freeing of objects for every change. (The standard approach recreates everything for every update, right? The downside is that a pool would create objects/ reserve max memory upfront, which is safer but overkill for small use cases.) Feel free to borrow any of those ideas. Pick, choose, and use as you see fit, or save for another time.

ServerNodeTree with NodeArrayCache:

// ServerNodeTree - Simple periodic updates
updateFunc = {
    updater = fork {
        loop {
            server.sendMsg("/g_queryTree", 0, 1);
            refreshRate.wait;
        };
    };
}

// NodeArrayCache - Cached update with interval check
update { |action|
    var now = Main.elapsedTime;
    if((now - lastUpdate) >= updateInterval) {
        server.queryAllNodes(true, { |msg|
            this.processNodeTree(msg);
            action.value(rawCache);
        });
    }
}

// ServerNodeTree - Recursive tree building
prAnalyzeNode { |msg, index, nodes, parentList|
    // Builds complete tree structure recursively
}

// NodeArrayCache - Flat processing
prBuildCaches { |numChildren, index, path|
    // Builds separate lookup tables
}

ServerNodeTree: complete tree structure
NodeArrayCache: More efficient with separate caches

ServerNodeTree: designed for traversing relationships
NodeArrayCache: Faster for direct node lookup O(1) complexity

ServerNodeTree: Complete rebuild each time for many things
NodeArrayCache: Can do partial updates.

ServerNodeTree: primarily suitable for tree operations
NodeArrayCache: individual node queries in no time

A hybrid approach might be best, taking:

ServerNodeTree’s cleaner update mechanism (traditional, one recursion takes care of it)
NodeArrayCache’s efficient caching (valid for more than one reason, optimization, and validation, as mentioned before)
Optional tree building for when needed (allow this flexibility)
Better error handling (nobody wrote that, oops)

Ok, so I will call this new class “Hybrid,” combining the best ideas so far:

// Scenario 1: Monitoring a specific synth
// Hybrid is fastest - direct cache lookup
h.getNode(1000);

// Scenario 2: Need complete tree visualization
// Hybrid builds it once and caches 
h.getNodeTree;

// Scenario 3: Watching group children 
// Hybrid has fast lookup without tree construction --  O(1), avoiding complexity O(n) or variants


//  NodeArrayCache:  rebuilds full caches
processNodeTree { |msg|
    nodeCache.do { |info| this.recycleNodeInfo(info) };
    nodeCache.clear;
    groupCache.clear;
    pathCache.clear;
    this.prBuildCaches(msg[3], 2, [1]);
}

//  ServerNodeTree:  rebuilds full tree for everything always
getNodeTree {
    if(running) {
        if(currentNodeTree.isNil) { 
            this.prFormatNodeTree;
        };
        ^currentNodeTree
    }
}

// Hybrid: Builds what you need when you need it (lazy-like)

getNode { |nodeID| ^nodeCache[nodeID] }     // Fast lookup if you just need one node O(1)

getNodeTree { // Only builds full tree if requested , avoids complexity when possible
    if(currentTree.isNil) { currentTree = this.buildTreeFromMessage }
    ^currentTree
}

–

That’s a good first step and simple

Ignoring all the big tasks relating to earlier posts on a large/complex node tree that would involve a design decision from the leadership of the project (or it will just left as is, if not considered important)