Sweet! Ok so this looks like its working and it’s definitely a major speed improvement. Thanks Vinn! I’m going to keep testing and studying it further but this definitely gets me up and moving again. Thanks so much!
Graeme
Good job guys ! Impressive example of collaboration 
Jules, any chance to have this -or something similar- implemented directly into Juce ? 
[quote=“dinaiz”]Good job guys ! Impressive example of collaboration
Jules, any chance to have this -or something similar- implemented directly into Juce ? :)[/quote]
I’m sure he’ll get around to it sooner or later but for now I suggest you create a “patch” and just re-apply it every time you pick up the latest tip.
The key is that now we know exactly what the bottleneck is (thanks to the profiler).
I know I know … I ask cause it’s not currently a problem for me but it’s gonna become one in the future, sojust want to know if I should make a patch OR just wait. Given that we are several developpers on several platforms, I’m not really into patching Juce to be honest 
And thanks to your and graeme’s efforts 
I hear you. What I do is keep Juce checked in to my local repo and then when I pull the tip, just re-apply the patches before comitting. The other developers do an SVN update to pick it up.
It’s a pain but so is waiting around to get stuff changed…
If I were you I wouldn’t bother with it until there is a performance problem, in which case you can just come to the forum and complain about it and someone will get to it.
Hi guys, and huge thanks for your efforts!
I’ll take a look through it all today, and will try to get something checked in for you to try…
TheVinn, just looking at your algorithm, I’m a bit puzzled by this:
if (first->destNodeId <= second->destNodeId) return -1;
else if (first->destNodeId > second->destNodeId) return 1;
else return 0;
…was it an accident that you wrote “<=” rather than “<”, or am I missing some subtle reason for doing it like that? (And if it’s deliberate, the “return 0” is actually unreachable code, which surely can’t be right…?)
[quote=“jules”]TheVinn, just looking at your algorithm, I’m a bit puzzled by this:
if (first->destNodeId <= second->destNodeId) return -1;
else if (first->destNodeId > second->destNodeId) return 1;
else return 0;
…was it an accident that you wrote “<=” rather than “<”, or am I missing some subtle reason for doing it like that? (And if it’s deliberate, the “return 0” is actually unreachable code, which surely can’t be right…?)[/quote]
Originally it was written ‘<’ but your binary search is biased towards high indexes when the element matches (because findInsertIndexInSortedArray uses ‘>=’) . By using ‘<=’ in the comparison function, findInsertIndexInSortedArray not only locates the insert position if the element does not exist, but also returns the existing element index if it is found. I just didn’t bother to delete the ‘else return 0’ after making the change.
Ok, gotcha. So I guess it really boils down to
first->destNodeId <= second->destNodeId ? -1 : 1;[quote=“jules”]Ok, gotcha. So I guess it really boils down to
Yeah, although it is still a hack and depends on the internal implementation of findIndexInSortedArray.
I would either change findIndexInSortedArray so it returns the lowest matching index, or add a new routine along side findIndexInSortedArray that has prescribed behavior, and then give Entry a real comparison function.
Yes, that’s what I’m doing. Ta!
Or…an OwnedSortedSet with a custom comparison function that would be pretty cool.
I’m sorry Jules but something is bothering me about this and I can’t leave it alone I think I have come up with a new technique that runs in linear time and would be orders of magnitude faster than even this change.
Ok, well fire away! Linear time seems a bit ambitious, but it might be possible to get below N^2.
Yeah I agree, it would be somewhere between N and N^2.
I took a stab at it but it didn’t work very well and fixing it would introduce complexity similar to the other implementation so I am abandoning it.
I’ve updated the test to better reflect the first example shown. You can specify how many tracks, aux tracks and how many nodes per track.
10 tracks, 4 auxs, 10 nodes per: (Totals: 150 nodes, 378 conns):
DEBUG: ~2.8 seconds
RELEASE: 282 ms
20 tracks, 4 auxs, 10 nodes per: (Totals: 250 nodes, 658 conns):
DEBUG: ~27 seconds
RELEASE: 2274 ms
/*
==============================================================================
This file was auto-generated by the Jucer!
It contains the basic startup code for a Juce application.
==============================================================================
*/
#include "../JuceLibraryCode/JuceHeader.h"
static void print (const String& s)
{
std::wcout << s << std::endl;
}
class BlankProcessor : public AudioProcessor
{
public:
AudioProcessorGraph::Node * node;
//==============================================================================
BlankProcessor() {
setPlayConfigDetails(2, 2, 44100,1024);
}
~BlankProcessor() {}
//==============================================================================
void prepareToPlay (double sampleRate, int samplesPerBlock) {}
void releaseResources() {}
void processBlock (AudioSampleBuffer& buffer, MidiBuffer& midiMessages)
{
buffer.clear();
}
//==============================================================================
AudioProcessorEditor* createEditor() { return 0; }
bool hasEditor() const { return false; }
//==============================================================================
const String getName() const { return String::empty; }
int getNumParameters() { return 0; }
float getParameter (int index) { return 0.0f; }
void setParameter (int index, float newValue) {}
const String getParameterName (int index) { return String::empty; }
const String getParameterText (int index) { return String::empty; }
const String getInputChannelName (int channelIndex) const { return String::empty; }
const String getOutputChannelName (int channelIndex) const { return String::empty; }
bool isInputChannelStereoPair (int index) const { return true; }
bool isOutputChannelStereoPair (int index) const { return true; }
bool acceptsMidi() const { return true; }
bool producesMidi() const { return true; }
//==============================================================================
int getNumPrograms() { return 1; }
int getCurrentProgram() { return 0; }
void setCurrentProgram (int index) {}
const String getProgramName (int index) { return String::empty; }
void changeProgramName (int index, const String& newName) {}
//==============================================================================
void getStateInformation (MemoryBlock& destData) {}
void setStateInformation (const void* data, int sizeInBytes) {}
};
class TestTrack {
public:
Array<BlankProcessor*> nodes;
TestTrack() {}
~TestTrack() {}
void addNode() {
nodes.add(new BlankProcessor());
}
};
class AudioGraphTest
{
public:
AudioGraphTest()
: graph( new AudioProcessorGraph )
{
graph->setPlayConfigDetails( 2,
2,
44100, 1024 );
graph->prepareToPlay( 44100, 1024 );
}
~AudioGraphTest() {}
void populateGraph( int numNodes, int numConnections, int64 seed )
{
Random rand( seed );
int src = 0, dst = 0;
/** Generate nodes */
++numNodes;
for( int i = numNodes; --i >= 1; )
{
graph->addNode( new BlankProcessor, i );
}
/** Add some connections */
for( int i = numConnections; --i >= 0; )
{
src = rand.nextInt( numNodes );
dst = rand.nextInt( numNodes );
/** Check that we don't add a connection to the same node */
while( src == dst )
dst = rand.nextInt( numNodes );
bool added = graph->addConnection( src, 0, dst, 0 );
graph->addConnection( src, 1, dst, 1 );
}
/** Make sure all connections are valid */
graph->removeIllegalConnections();
}
void populateCustomConfig(int numAudioTracks, int numAuxTracks, int numNodesPerTrack) {
jassert(numAudioTracks >= 1);
jassert(numAuxTracks >= 1);
jassert(numNodesPerTrack >= 3);
print("\nPopulate Graph with "+String(numAudioTracks)+" Tracks, "+String(numAuxTracks)+" Aux tracks, 1 Master Track. "+String(numNodesPerTrack)+" nodes per track");
Array<TestTrack*> audioTracks;
Array<TestTrack*> auxTracks;
for (int i = 0; i < numAudioTracks; i++) {
audioTracks.add(new TestTrack());
}
for (int i = 0; i < numAuxTracks; i++) {
auxTracks.add(new TestTrack());
}
TestTrack * master = new TestTrack();
for (int i = 0; i < numNodesPerTrack; i++) {
for (int j = 0; j < numAudioTracks; j++) {
TestTrack * track = audioTracks.getUnchecked(j);
track->addNode();
}
for (int j = 0; j < numAuxTracks; j++) {
TestTrack * track = auxTracks.getUnchecked(j);
track->addNode();
}
master->addNode();
}
OwnedArray<TestTrack> allTracks;
for (int i = 0; i < numAudioTracks; i++) {
allTracks.add(audioTracks[i]);
}
for (int i = 0; i < numAuxTracks; i++) {
allTracks.add(auxTracks[i]);
}
allTracks.add(master);
for (int i = 0; i < allTracks.size(); i++) {
TestTrack* track = allTracks.getUnchecked(i);
for (int j = 0; j < track->nodes.size(); j++) {
BlankProcessor * bp = track->nodes[j];
bp->node = graph->addNode(bp);
if (j > 0) {
int prevNodeIndex = j-1;
//Last 2 nodes on the track are busfader and fader
if (j == track->nodes.size()-1) {
prevNodeIndex = j-2;
}
BlankProcessor * prevNode = track->nodes[prevNodeIndex];
graph->addConnection(prevNode->node->id,0, bp->node->id, 0);
graph->addConnection(prevNode->node->id,1, bp->node->id, 1);
}
}
}
BlankProcessor * masterB = master->nodes[0];
for (int i = 0; i < audioTracks.size(); i++) {
TestTrack* track = audioTracks[i];
BlankProcessor * trackBusFader = track->nodes[numNodesPerTrack-2];
BlankProcessor * trackFader = track->nodes[numNodesPerTrack-1];
for (int j = 0; j < auxTracks.size(); j++) {
TestTrack * aux = auxTracks[j];
BlankProcessor * auxB = aux->nodes[0];
graph->addConnection(trackBusFader->node->id, 0, auxB->node->id,0);
graph->addConnection(trackBusFader->node->id, 1, auxB->node->id,1);
}
graph->addConnection(trackFader->node->id, 0, masterB->node->id,0);
graph->addConnection(trackFader->node->id, 1, masterB->node->id,1);
}
for (int i = 0; i < auxTracks.size(); i++) {
TestTrack* aux = auxTracks[i];
BlankProcessor * auxF = aux->nodes[numNodesPerTrack-1];
graph->addConnection(auxF->node->id, 0, masterB->node->id,0);
graph->addConnection(auxF->node->id, 1, masterB->node->id,1);
}
print("Total Nodes Added: "+String(graph->getNumNodes())+"\nTotal Connections: "+String(graph->getNumConnections()));
}
void reset()
{
graph->clear();
}
void prepareToPlay ()
{
graph->prepareToPlay (44100, 1024);
}
private:
ScopedPointer<AudioProcessorGraph> graph;
};
//------------------------------------------------------------------------------
template <class T>
struct Stats
{
Stats (int count, const T* data)
{
n = count;
lo = data[0];
hi = data[0];
sum = 0;
for (int i = 0; i < count; ++i)
{
T v = data[i];
lo = std::min (lo, v);
hi = std::max (lo, v);
sum += v;
}
mean = double (sum) / count;
double totvarsquared = 0;
for (int i = 0; i < count; ++i)
{
T v = data[i];
const double var = v - mean;
totvarsquared += var * var;
}
dev = sqrt (totvarsquared / (n - 1));
}
int n;
double dev;
double mean;
T lo;
T hi;
T sum;
};
//------------------------------------------------------------------------------
static void run (void (*test)(), const char* name)
{
const int ntrial = 5;
int64 trial[ntrial];
int64 total;
Time startTime = Time::getCurrentTime();
for (int i = 0; i < ntrial; ++i)
{
Time startTime = Time::getCurrentTime();
test ();
RelativeTime elapsedTime = Time::getCurrentTime() - startTime;
trial [i] = elapsedTime.inMilliseconds ();
int64 ms = elapsedTime.inMilliseconds ();
String s;
s << name << " #" << String (i+1) << " " <<
String (ms) << " ms";
print (s);
}
RelativeTime elapsedTime = Time::getCurrentTime() - startTime;
total = elapsedTime.inMilliseconds ();
Stats<int64> stats (ntrial, trial);
String s;
int64 ms = elapsedTime.inMilliseconds ();
s << name << " " <<
String (stats.sum) << " total, " <<
String (stats.mean, 0) << " avg, " <<
String (stats.dev, 3) << " dev";
print (s);
}
//------------------------------------------------------------------------------
void test1 ()
{
AudioGraphTest agt;
// agt.populateGraph (4096, 65536, 1);
//agt.populateGraph(512, 128, 1);
agt.populateCustomConfig(20,4,10);
agt.prepareToPlay ();
}
int main (int, char**)
{
ScopedJuceInitialiser_GUI jucelib;
run (test1, "AudioGraphTest");
return 0;
}Yeah the Release version takes 700ms for me with your test.
Are you saying this is still too slow?
If this is going to be improved further, it will be necessary to keep the Connection array sorted so that getConnectionBetween runs in O(log N) instead of O(N):
[attachment=0]audiograph.png[/attachment]
This change requires modifying the class declaration and can’t be done privately the way I did the first one.
TBH the best way to optimise that bit would probably be to change the algorithm used in isBufferNeededLater(), which is again pretty naive…
The improvements so far have been great, but 2 seconds is what I get, and if I bump it to 20 tracks and 8 auxs, it jumps to 4 seconds, so I’m still interested in the options. I’m on a 2010 macbook pro 2.4gh core 2 duo but I’m aiming to run on much lesser machines, so that’s my considerations. And somebody down the road may wish to run a much higher number of tracks?
I’m not at all versed in algorithm speak (I’ll work on that), but as you mention a different approach seems to be necessary. Maybe if the graph could be broken down into paths then each node could be associated to the paths in which it lies? Maybe that’s what you mean by sorting the Connections? As connections are added, paths are constructed and paths are associated with the contained nodes. A node for example might then belong to 4 distinct paths.