I’ll try modifying your test to create the configuration
Sorry for my ignorance, Vinn can you provide some instructions on how to run the test?
EDIT: Nevermind…used the Introjucer! 8)
Vinn, the reason your numbers look so good is because the connections weren’t actually being added.
BlankProcessor needs this set:
setPlayConfigDetails(2, 2, 44100,1024);
Try it again and be prepared to wait.
[quote=“Graeme”]BlankProcessor needs this set:
setPlayConfigDetails(2, 2, 44100,1024);
[/quote]
Okay! Now we are in business! Here’s my modified test app:
#include "juce.h"
class BlankProcessor : public AudioProcessor
{
public:
//==============================================================================
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 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 );
graph->addConnection( src, 0, dst, 0 );
graph->addConnection( src, 1, dst, 1 );
}
/** Make sure all connections are valid */
graph->removeIllegalConnections();
}
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 print (const String& s)
{
std::wcout << s << std::endl;
}
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 (512, 128, 1);
agt.prepareToPlay ();
}
int main (int, char**)
{
ScopedJuceInitialiser_GUI jucelib;
run (test1, "AudioGraphTest");
return 0;
}And here’s the performance summary:
[attachment=0]audiograph.png[/attachment]
AudioProcessorGraph::getConnectionBetween() is dominating the run-time!
Okay so getConnectionBetween() does a linear search through the list of connections. Obviously this does not scale. This is the member variable:
It seems that the basic algorithm of AudioProcessorGraph doesn’t need to change, because getConnectionBetween is such a large percentage of the run time. Changing it to have better run-time characteristics O (log N) or O(1) would have a huge impact on overall performance.
What we need to do is overlay a hash table on top of this thing and we should get a good speed-up.
Here is the test with an attempt to recreate the configuration in my initial examples. Try it with higher nodes per track and watch the times skyrocket.
/*
==============================================================================
This file was auto-generated by the Jucer!
It contains the basic startup code for a Juce application.
==============================================================================
*/
#include "../JuceLibraryCode/JuceHeader.h"
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 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 numNodesPerTrack) {
jassert(numNodesPerTrack >= 3);
Array<BlankProcessor*> track;
Array<BlankProcessor*> aux;
Array<BlankProcessor*> master;
for (int i = 0; i < numNodesPerTrack; i++) {
track.add(new BlankProcessor());
aux.add(new BlankProcessor());
master.add(new BlankProcessor());
}
Array< Array<BlankProcessor*> > tracks;
tracks.add(track);
tracks.add(aux);
tracks.add(master);
for (int i = 0; i < tracks.size(); i++) {
Array<BlankProcessor*> track = tracks[i];
for (int j = 0; j < track.size(); j++) {
BlankProcessor * bp = track[j];
bp->node = graph->addNode(bp);
if (j > 0) {
BlankProcessor * prevNode = track[j-1];
graph->addConnection(prevNode->node->id,0, bp->node->id, 0);
graph->addConnection(prevNode->node->id,1, bp->node->id, 1);
}
}
}
BlankProcessor * trackBF = track[numNodesPerTrack-2];
BlankProcessor * trackF = track[numNodesPerTrack-1];
BlankProcessor * auxB = aux[0];
BlankProcessor * auxF = aux[numNodesPerTrack-1];
BlankProcessor * masterB = master[0];
graph->addConnection(trackBF->node->id, 0, auxB->node->id,0);
graph->addConnection(trackBF->node->id, 1, auxB->node->id,1);
graph->addConnection(trackF->node->id, 0, masterB->node->id,0);
graph->addConnection(trackF->node->id, 1, masterB->node->id,1);
graph->addConnection(auxF->node->id, 0, masterB->node->id,0);
graph->addConnection(auxF->node->id, 1, masterB->node->id,1);
}
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 print (const String& s)
{
std::wcout << s << std::endl;
}
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(8);
agt.prepareToPlay ();
}
int main (int, char**)
{
ScopedJuceInitialiser_GUI jucelib;
run (test1, "AudioGraphTest");
return 0;
}Here’s the results from Shark when running the custom test with 8 nodes per track (24 nodes total). It’s around 25 seconds per run.
[attachment=0]shark24nodes48connections.jpg[/attachment]
Sorry for the delay! I went to see the movie “Source Code” which in my opinion was pretty good although my girl didn’t like it.
Try making this change in juce_AudioProcessorGraph.cpp. Insert this code just before AudioProcessorGraph::buildRenderingSequence, and note that it replaces some of the beginning of that function.
// for each unit32 destNodeId maintain an array of unit32
// srcNodeId that lead to destNodeId in the Connection graph
namespace {
struct ConnectionLookupTable
{
explicit ConnectionLookupTable (
OwnedArray <AudioProcessorGraph::Connection> const& connections)
{
if (connections.size () > 0)
{
const AudioProcessorGraph::Connection* c = connections.getUnchecked (0);
for (int i = 0; i < connections.size(); ++i)
{
c = connections.getUnchecked (i);
// Find or add this destNodeId
int index;
Entry* entry = findEntry (c->destNodeId, &index);
if (!entry)
{
entry = new Entry (c->destNodeId);
m_table.insert (index, entry);
}
entry->srcNodes.add (c->sourceNodeId);
// Now for each Entry that contains destNodeId, also add srcNodeId
for (int j = 0; j < m_table.size(); ++j)
{
Entry* other = m_table.getUnchecked (j);
if (other->srcNodes.contains (c->destNodeId))
other->srcNodes.add (c->sourceNodeId);
}
jassert (isAnInputTo (c->sourceNodeId, c->destNodeId));
}
}
}
bool isAnInputTo (const uint32 possibleInputId,
const uint32 possibleDestinationId)
{
Entry* entry = findEntry (possibleDestinationId);
return entry && entry->srcNodes.contains (possibleInputId);
}
private:
// Holds a list of node Ids that eventually lead to destId
struct Entry
{
explicit Entry (uint32 id) : destNodeId (id) { }
struct Compare
{
static int compareElements (Entry* first, Entry* second)
{
// The inequality is a bit of a hack
if (first->destNodeId <= second->destNodeId) return -1;
else if (first->destNodeId > second->destNodeId) return 1;
else return 0;
}
};
uint32 destNodeId;
SortedSet <uint32> srcNodes;
};
// Find the Entry if it exists, and possible insert index, for a given node Id.
Entry* findEntry (uint32 destNodeId, int* pInsertIndex = 0)
{
Entry::Compare comp;
Entry match (destNodeId);
int index = findInsertIndexInSortedArray (comp,
m_table.getRawDataPointer (),
&match,
0,
m_table.size ());
if (pInsertIndex)
*pInsertIndex = index;
Entry* entry;
if (index < m_table.size ())
{
entry = m_table.getUnchecked (index);
if (entry->destNodeId != destNodeId)
entry = 0;
}
else
{
entry = 0;
}
return entry;
}
OwnedArray <Entry> m_table;
};
}
void AudioProcessorGraph::buildRenderingSequence()
{
Array<void*> newRenderingOps;
int numRenderingBuffersNeeded = 2;
int numMidiBuffersNeeded = 1;
{
MessageManagerLock mml;
Array<void*> orderedNodes;
ConnectionLookupTable table (connections);
int i;
for (i = 0; i < nodes.size(); ++i)
{
Node* const node = nodes.getUnchecked(i);
node->prepare (getSampleRate(), getBlockSize(), this);
int j = 0;
for (; j < orderedNodes.size(); ++j)
#if 1
if (table.isAnInputTo (node->id,
((Node*) orderedNodes.getUnchecked (j))->id))
#else
if (isAnInputTo (node->id,
((Node*) orderedNodes.getUnchecked (j))->id,
nodes.size() + 1))
#endif
break;
orderedNodes.insert (j, node);
}I am not 100% sure that it functions correctly but it should be pretty close and the basic algorithm should be ok.
Jules wuddya think about this?
Hey Vinn, thanks for sharing the code. I’ve been testing it out and yeah it doesn’t seem to work quite right but I’m not aware of why at this point. I have been trying to get familiar with the AudioProcessorGraph code and will keep looking at it.
My understanding of isAnInputTo() is that it returns true if the given destNodeId can be reached from sourceNodeId in the directed graph formed by the Connections table. The original implementation is recursive.
What I did in the lookup table class is to unroll this recursion. m_table is a sorted array of Entry.
Each Entry corresponds to a unique destNodeId and contains a SortedSet of all the sourceNodeId that lead up to it via the Connection array.
Once the table is built, the implementation of isAnInputTo() is straightforward: Find the Entry corresponding to destNodeId and then check it’s SortedSet to see if the possibleInputId is contained.
The algorithm to build the table is as follows:
for each Connection do:
- Create an Entry for the destNodeId if it doesn’t already exist
- Add the sourceNodeId to the SortedSet for the Entry
- for each Entry in m_table do:
if this Entry’s SortedSet contains (destNodeId) then
add sourceNodeId to Entry’s SortedSet
A problem with Juce is that the support for intrusive sorted arrays is not so great. It was a bit of a hack for me to implement a sorted array of pointers to Entry.
One hack is the inequality of the comparison function;
if (first->destNodeId <= second->destNodeId) return -1;Originally it was ‘<’ instead of ‘<=’ but that causes it to fail to find the entry if it exists, because the Juce binary search implementation in findInsertIndexInSortedArray is biased towards higher insertion indexes when the comparison function returns zero.
There could be a problem with my implementation of findEntry() because of this.
I wish Juce had better support for sorted arrays of pointers, it would be great if the key could be separate from the data.
[quote=“TheVinn”] if (first->destNodeId <= second->destNodeId) return -1;
[/quote]
I don’t think that sorting based on node id provides any benefit as I don’t believe the node id is an indicator of where in the graph a node is.
[quote=“Graeme”][quote=“TheVinn”] if (first->destNodeId <= second->destNodeId) return -1;
[/quote]
I don’t think that sorting based on node id provides any benefit as I don’t believe the node id is an indicator of where in the graph a node is.[/quote]
The sort is used for quickly finding entries in the lookup table.
This table is only used in buildRenderingSequence(), it is created once, buildRenderingSequence() then constructs the ordered graph, and then it is disposed.
The lookup table sorts Entry by destNodeId so that they can be found quickly instead of doing a linear search.
^^ This is why Entry needs a sort.
Ok I see. thanks.
I just added some verification code and it looks like findEntry() is working fine. In fact, I don’t see a problem with this implementation, except that when there is recursion it might return true where the original returns false. But regardless, that isn’t coming up with your test case.
Are you sure it is not working as expected?
Yep, for my own app I have switched the code back and forth, original code = sound coming out, this code = no sound coming out. When testing with the Plugin Host Example it does work sometimes, but sometimes not, and at one point corrupted the sound on my laptop and I had to restart.
Yes I see, this algorithm does not work correctly, I am working on it.
Okay, try this version. Unfortunately it is not as fast as the first one I posted. But that one didn’t work, so who cares?
// for each unit32 destNodeId maintain an array of unit32
// srcNodeId that lead to destNodeId in the Connection graph
namespace {
struct ConnectionLookupTable
{
explicit ConnectionLookupTable (
OwnedArray <AudioProcessorGraph::Connection> const& connections)
{
if (connections.size () > 0)
{
const AudioProcessorGraph::Connection* c = connections.getUnchecked (0);
for (int i = 0; i < connections.size(); ++i)
{
c = connections.getUnchecked (i);
// Find or add this destNodeId
int index;
Entry* entry = findEntry (c->destNodeId, &index);
if (!entry)
{
entry = new Entry (c->destNodeId);
m_table.insert (index, entry);
}
entry->srcNodes.add (c->sourceNodeId);
}
}
}
bool isAnInputTo (const uint32 possibleInputId,
const uint32 possibleDestinationId)
{
return isAnInputToRecursive (possibleInputId, possibleDestinationId, m_table.size ());
}
private:
bool isAnInputToRecursive (const uint32 possibleInputId,
const uint32 possibleDestinationId,
int recursionCheck)
{
if (recursionCheck > 0)
{
Entry* entry = findEntry (possibleDestinationId);
if (entry)
{
SortedSet <uint32> const& srcNodes = entry->srcNodes;
if (srcNodes.contains (possibleInputId))
return true;
for (int i = 0; i < srcNodes.size (); ++i)
if (isAnInputToRecursive (possibleInputId,
srcNodes.getUnchecked (i),
recursionCheck - 1))
return true;
}
}
return false;
}
private:
// Holds a list of node Ids that eventually lead to destId
struct Entry
{
explicit Entry (uint32 id) : destNodeId (id) { }
struct Compare
{
static int compareElements (Entry* first, Entry* second)
{
// The inequality is a bit of a hack
if (first->destNodeId <= second->destNodeId) return -1;
else if (first->destNodeId > second->destNodeId) return 1;
else return 0;
}
};
uint32 destNodeId;
SortedSet <uint32> srcNodes;
};
// Find the Entry if it exists, and possible insert index, for a given node Id.
Entry* findEntry (uint32 destNodeId, int* pInsertIndex = 0)
{
Entry::Compare comp;
Entry match (destNodeId);
int index = findInsertIndexInSortedArray (comp,
m_table.getRawDataPointer (),
&match,
0,
m_table.size ());
if (pInsertIndex)
*pInsertIndex = index;
Entry* entry;
if (index < m_table.size ())
{
entry = m_table.getUnchecked (index);
if (entry->destNodeId != destNodeId)
entry = 0;
}
else
{
entry = 0;
}
return entry;
}
OwnedArray <Entry> m_table;
};
}
void AudioProcessorGraph::buildRenderingSequence()
{
Array<void*> newRenderingOps;
int numRenderingBuffersNeeded = 2;
int numMidiBuffersNeeded = 1;
{
MessageManagerLock mml;
Array<void*> orderedNodes;
ConnectionLookupTable table (connections);
int i;
for (i = 0; i < nodes.size(); ++i)
{
Node* const node = nodes.getUnchecked(i);
node->prepare (getSampleRate(), getBlockSize(), this);
int j = 0;
for (; j < orderedNodes.size(); ++j)
#if 1
if (table.isAnInputTo (node->id,
((Node*) orderedNodes.getUnchecked (j))->id))
{
jassert (isAnInputTo (node->id,
((Node*) orderedNodes.getUnchecked (j))->id,
nodes.size() + 1));
break;
}
#else
if (isAnInputTo (node->id,
((Node*) orderedNodes.getUnchecked (j))->id,
nodes.size() + 1))
break;
#endif
orderedNodes.insert (j, node);
}